> load "tut9data.txt"; Loading "L:\win\Magma\MATH2068\tut9data.txt" > p:=2^32+15; > IsPrime(p); true > Factorization(p-1); [ <2, 1>, <3, 2>, <5, 1>, <131, 1>, <364289, 1> ] > F:=FiniteField(p); > r:=PrimitiveElement(F); > r; 3 > for i:=1 to 20 do for> time Log(r,Random(F)); for> end for; 4220166409 Time: 0.000 271018217 Time: 0.000 1541595435 Time: 0.000 664826203 Time: 0.000 3551011118 Time: 0.000 4040117645 Time: 0.000 1836643601 Time: 0.000 3877472393 Time: 0.000 2598663552 Time: 0.000 3161665059 Time: 0.000 3176198361 Time: 0.000 1672253398 Time: 0.000 3296644192 Time: 0.000 3534866401 Time: 0.000 3842352456 Time: 0.000 561784376 Time: 0.000 2286040566 Time: 0.000 1812632987 Time: 0.000 3879745500 Time: 0.000 1218991790 Time: 0.000 > /* > Magma found all of these extremely quickly! > */ > p:=2^32+61; > IsPrime(p); true > Factorization(p-1); [ <2, 2>, <1073741839, 1> ] > F:=FiniteField(p); > r:=PrimitiveElement(F); > r; 2 > for i:=1 to 20 do for> time Log(r,Random(F)); for> end for; 2936017701 Time: 0.063 817813393 Time: 0.047 1550484183 Time: 0.078 3053289656 Time: 0.047 2798488146 Time: 0.031 1510865571 Time: 0.031 2757742116 Time: 0.063 231024277 Time: 0.047 421846878 Time: 0.047 1540096000 Time: 0.047 3786909686 Time: 0.031 3203081869 Time: 0.063 368239995 Time: 0.047 1543669255 Time: 0.047 1542707642 Time: 0.047 2874609879 Time: 0.063 2874829697 Time: 0.031 3704721269 Time: 0.063 1601645414 Time: 0.047 2607436484 Time: 0.063 > /* > Certainly they were slower. > In this case the largest prime factor of p-1 is about 10^9. In the > previous example it was merely 3.6*10^5. The larger the largest > prime factor of p-1 is, the harder the discrete logarithm computations > become. > */ > timelog(50); 13.4039365802874417634915365164 0.031 > timelog(50); 5.34664246188778651707091146269 0.000 > timelog(50); 7.39396924676593008799422405425 0.000 > timelog(50); 9.27942837992272527785307930022 0.016 > timelog(50); 7.82886408230001037456804794362 0.015 > timelog(50); 5.51727544848736521754553113048 0.016 > timelog(50); 9.17756497265070814007838980283 0.000 > timelog(50); 7.35573051101974617951481467611 0.000 > timelog(50); 12.0802328089017361988369084466 0.015 > timelog(60); 8.04945493768499999888932873446 0.016 > timelog(60); 10.6826887631002625233362396560 0.015 > timelog(60); 16.1260304567434399994148118139 0.047 > timelog(60); 13.7588453692294966636172303274 0.062 > timelog(70); 14.9674620307896477590212474192 0.500 > timelog(70); 8.21962562799934003865559141735 0.016 > timelog(70); 22.7541621872466066092686859353 0.125 > timelog(70); 15.2906975641446475960279277438 0.110 > timelog(70); 19.9230014245011322594395249687 0.110 > timelog(70); 10.5894255620222930269119157959 0.078 > timelog(70); 13.4460654697342169088408076219 0.125 > timelog(80); 14.9876389762213651870945139041 0.203 > timelog(80); 14.3612978077020323541123214784 0.219 > timelog(80); 21.0113641694369224687993164924 0.250 > timelog(80); 13.7404181566080784584374185604 0.234 > timelog(90); 18.6743941432783020225681865173 0.375 > timelog(90); 18.9096160200479912737912662057 0.531 > timelog(90); 24.9888942648095413452387287114 0.484 > timelog(90); 19.7486528152914586130008150182 0.406 > timelog(90); 30.7224665758912606706363673056 0.422 > timelog(90); 13.9791641597609163088360571328 0.562 > timelog(90); 14.0599516998066849806656101833 0.468 > timelog(100); 17.8298162199805459266597338926 1.359 > timelog(100); 30.8787390662614359022880516587 5.000 > timelog(100); 13.6738723624020053283542534046 0.813 > timelog(100); 22.9952659705554931078836665423 0.985 > timelog(100); 19.7003597850920559002363062460 1.031 > timelog(110); 18.3061069610993992518158646721 1.297 > timelog(110); 22.8361108285224758871566711146 2.282 > timelog(110); 30.0533285078330254150755603742 1.906 > timelog(110); 24.6937142967259800236357018030 2.141 > timelog(120); 28.4605652384600604443412173956 63.234 > /* > Some are harder than others! > */ > timelog(120); 21.1139263335717756747489921927 3.219 > timelog(120); 39.1484630952325790605339869336 4.016 > timelog(120); 32.9897837904139562261307689639 62.203 > /* > Another hard one! > > Turning now to Question 2, observe that if you increase the number > of bits by 10 at each step, you will need 56 steps to get from 100 > bits to 660 bits. If the time doubles with each step, then it gets > doubled 56 times, which means that the overall effect of 56 steps > is to multiply the time by 2^56. > So the answer is 2^56 seconds. > */ > 2^56; 72057594037927936 > /* > Let me convert this to a real number > */ > 2.0^56; 72057594037927936.0000000000000 > /* > How many days are there in this many seconds? > */ > s:=2.0^56; > days:=s/(60*60*24); > days; 833999930994.536296296296296296 > /* > mmm ... quite a few .. > */ > centuries:=days/36500; > centuries; 22849313.1779325012683916793506 > /* > OK, I won't bother testing it. > */ > p:=NextPrime(Random(10^199,10^200):Proof:=false); > p; 59273969457811989717847025558565082497677675089179961815498796346075971728535471994650517\ 36540253682466677579485819716901573015874648089807606912566631570884233282151677158084257\ 8972144418982218534659 > b:=2; > m:=Random(p-1); > GCD(m,p-1); 1 > k:=Modexp(b,m,p); > b; 2 > k; 49117370039420739724769266078524783933391734014569512035943395607341451973579103892433395\ 48303247436426570703832548932303852878463333013012450818101456079168846516364951479538046\ 3715609379562783100848 > xx:=NaiveEncoding("People who > like this sort of thing will find this the sort of thing they like"); > xx; [ 180201211212208201132219204211110208205207201132216204205215132215211214216132211202132\ 21620420521020313221920520820813220220521020013221620420521513221620420113221521121421613\ 2211202132216204205210, 203132216204201221132208205207201 ] > i:=Random(p-1); > sf:=Modexp(k,i,p); > ct:=; > ct; <1400452254589780062599457057406276586155434744936343060080197400390925732107922753386827\ 83843239054891924437615466379161505527206944334584821969818871662429510427324388669632301\ 65511319947566090206176, [ 54625674739348830493832382720293659107178816091961027731676877\ 85930860839598243068459995795317384761112742110799925814645162116786392990670866757442317\ 333203842233151141510694967286544823319378989367, 48960835889130087630786383306977973551644728928312673760665668567017806694366769288583910\ 01804786238149807060310839119330511717098585366180045087366235834422800557961000466059528\ 1123070256801710133834 ]> > ct[1]; 14004522545897800625994570574062765861554347449363430600801974003909257321079227533868278\ 38432390548919244376154663791615055272069443345848219698188716624295104273243886696323016\ 5511319947566090206176 > ct[2]; [ 546256747393488304938323827202936591071788160919610277316768778593086083959824306845999\ 57953173847611127421107999258146451621167863929906708667574423173332038422331511415106949\ 67286544823319378989367, 4896083588913008763078638330697797355164472892831267376066566856\ 70178066943667692885839100180478623814980706031083911933051171709858536618004508736623583\ 44228005579610004660595281123070256801710133834 ] > isf:=Modexp(ct[1],-m,p); > isf; 31574501513570847665532242655014714709131267893909147984414452336292111196538233477366226\ 01283930345701536791689661281057301789153187248266902023293432732408914293655614062744227\ 3420886697329959820375 > sf; 41731370589219027217204569937108374245038722023290763291143387883692023991424370535805740\ 04808285282080841620862909035071542003474283731706387993128964221905974114989346873914894\ 7230566900874210696890 > sf*isf mod p; 1 > pt:=[isf*u mod p : u in ct[2]]; > pt eq xx; true > NaiveDecoding(pt); People who like this sort of thing will find this the sort of thing they like > xx:=NaiveEncoding(camel); > i:=Random(p-1); > sf:=Modexp(k,i,p); > ct:=; > ct[1]; 42675620504520465904875200299631330881454159759874518718089908360874310492715616817491785\ 98825436790675244328170529823080222398499558380411397946994731981718585883612375975631465\ 8029559118236797583846 > ct[2]; [ 349238660636840675124476411331441100913699558669331422202940695091841668810225476326438\ 32880067837833023050535783527496892029544838648046266153750521532352279581678943726662452\ 19203780324227747131622, 9685038419430953218355353910658747920878278201781593957499609753\ 26007453435534750319985289311788156842268460964226022598338746352783582062940285546463770\ 7149371737593330664857881821810203986315036893, 29769412033146019245582939771765168353066546231701793148537222392584993167561975442579666\ 72257186659718959697200972512066364394680031154464937353083556586646845315696871747254996\ 2760728405265120214130, 28935527992151020878203250748062085329760526488972922951754123574\ 14401850291535015597739618003781960298003771540095745755137399915755296433389735904603674\ 568677316462988485543161656928576278473031894, 36479082120695691870521266633619126724714915742132713178309775261837135535127451352945562\ 16064810220768119209026679599614625449575135417100756292492490761950898498977800105633885\ 4747878855938472085029, 57056082081886734881368376644801100393158874584311051105312892546\ 16787177171903074081286944729040983905038370242738333001596688490705311481410041343456451\ 8792355822428278788984762639254165434292134589, 56399450281597225145339039658906817965291570326975850752422575658813169813853187592205790\ 08565142013812653026660334460959424789723198689196362373149744022716985178837975514914725\ 5147197553714234690256, 16406457377971489840958448879658013781664854339562448197368598729\ 45382512040462631629556878121980557654788944537153801669013407060648728519682660926656352\ 9813221229559981059709224197631818544793053790, 13560916013605039028210074888201469327311696713051084198495878537185060115582515753837831\ 41218613807134733948186171427809905629225687771497626151835799042905395957130300207179396\ 786534921278430877045, 390795350290847424440715651119531487310116390936027046299444779922\ 04872130277426686984912815177016448601040296437200228543344037174298640892962536126452957\ 047626883236513396708935952899024873539491437, 12334709864992946406124901486217780109779734621599940180614172531240549090754194823247546\ 63617447614782195652004846328140537211432528343523680433753126791233440033814823360720254\ 9338379590847611287138, 24738007530036213564632575089554907795421561293311510795898133747\ 33698766807742376230233397740129081762770003650868256714813622754116056319064684141187807\ 9207852445625790151577388112450180790674291377, 11127310614412050551400049875713641510199894916324592943393820098398222452166670558865928\ 65370470173387002255921372600198112532904630013213403496545435354376072312319157125160603\ 5607967182420088567292, 17106114780329340010055817289311523455319021068963746101299342628\ 88769242600086767744497237859771148141177017360401676056055017184258451091553688670751329\ 5302619497803819014301523165360312948871450653, 37821522578138468360743424609255961726312902260010014985081420238496552186956587000376022\ 00209887711352084290771835416352930816076050997914315753897431563464877361841788345197808\ 7863430248534461717124, 57941979940350069917837794245643350930744814606221489033366263825\ 37686921898472491080965047365205918415078342173779686954764264765432663538866601788877714\ 9644351856882788276148956386631707088164931182, 68093679957997948449047481256285506965362338005714790753861859245196256275222600210227859\ 04232863434550129602482776062069738779314616458279454334806094326232849267444677920830006\ 521208361432496592761, 282778985752346253645239297907460513334508601094863656937277670181\ 38400134514860419772897654777935029652919906030056014619409761943811258752550434895870633\ 075084442132478942692076086862504907562272864, 41459863536685595222178676869185723487593139260871252072875531392023520536229916772233528\ 16493516414181223365881527582286456701544206160826429427734885049607031886770736615255903\ 4605071274734468438340, 35815195586753097434555525642464374303527282714147850670988776682\ 00960372580451844276213902540419960175941076625070416886829691282758903549060598655386078\ 2676849465867946874214472287123812002210108209, 21699696334075340512345080766621742409475936502655501668180877747507147919934179881504181\ 99299969880321835810030494344766367267706023832432431969829969473603385381474875047292523\ 5185300093208259241197, 37830596909170929816379649064776149030816727075717403548442854238\ 95645964620140680784783376915962377633211947635326976332164267101211697511745370537445198\ 2248029117997332948367955067263500007865567844, 30387670879852498845375252061640126480932843650268678666890049173235006680164393655292624\ 64771229387690855523114657523668200712673557769616236463611639737260160676840600354880010\ 147793431003494485554, 452460982460569449315540265226802159524929035018468443811047446140\ 98766854145557388776700353015690933991744114026049244258716139092293362087278553625033047\ 343566143959432023373832590060583875491515742, 12179022690114909462574715577808909336336270160685701224227275051734431666006976242882984\ 68954251775393766597310443051732010679437151468740930254532058553224889502609361080584165\ 4991590836794135487135, 35066862533924483571959413485190547221216138572594079969366360272\ 40763807471393383233618560200793166773603802927026407210882022924930422699160372811558415\ 9025854607062158409834090937025961433134968770, 45232742678112849926468678300466130448166512850743025755099263630199063379700118573232698\ 65981672163057444406598451296636682204847365031398487393202536894416527394140913624424132\ 2187474935146100737587, 35505167148860132038912751017591895315307890656796614043133084146\ 83038414639525503777578527882810162208753639876715925054307766708232102730047487340054272\ 7597730610638053753851449914036441863001044799, 34381831011059587580157570481538327211072637625221954046673225387985895765420633645914344\ 98952665320641594272217528359551370262840435129303688391285048814319699988140975387871526\ 1729734406553411099457, 55722659012296727537739769885567962129318763035868613839522256100\ 84714031971967728613484591225353887719281039885905289955970782711740866541591257943463719\ 4401371351269267585525665731125684317646136390, 50160241409114868979465582479764511089244792206200290804137100115615816212445127050810448\ 97256204151285820433267409464367046796119778825510020014344251657041361693326634553636778\ 8360125734777949872854, 41932985693632916121975179272906009835255979478600679507207548189\ 34593564546952515396603107526950837562645704405585593162163913611522980654194776842439892\ 7242771836318406356982975098202901197710099125, 52112739832430962387519418349177752641304290652734439842636665557133660681519848606325612\ 70399254922468286771198001780443632093962961204728202310293770255468425354112301178256002\ 6138669695173757205954, 25204209360549234344981245313189667900681568991863552880890856898\ 06191712032229482365733219501910810215195784080603082695871887580336995147666219395237597\ 50725457140897882720236304146402695789716844, 41082109145102067143681173173392555757691959225567471507998612655829045497796328162672535\ 85478087935306917236236986437532396309431629367684687504393570680303957354948533234898207\ 2122250240678127974014, 34904430670054221232664463241848842542249128364100658118724027022\ 47011840324376087260883212135593520216755618778048835341250235149012957865707469359018207\ 6537706407970596528091346615652563104566718599, 71969904479856542790884693577397521837496174415860822206391099292892405183341513067341121\ 40132453199537366508266569565218833038766727505810467168825342279413958899609928741850259\ 152270115448884706042, 349652401369085014433943274920293167003516342185139416630598044199\ 89068947025287088756149858411232975512035420691471334515720548889779145751080434467795496\ 195863343082797358842096255300276920169640514, 23605616736280694603812965385048817536958563770861338027151090083516960483168322246497623\ 23846814014225867129378037258478655218173703849326847186893672846573968248077706902932804\ 4020454731137374198543, 19623171085969311385749027796036762357729234118614847046317949997\ 50092726588248994587623808762542895609174609847781938067770682274743083675889768434671674\ 8398949883915939327685803639857038352664901727, 40295746719863167468607516096236270494874014124537607662587409019578603444172680421704201\ 54900719893883748864885032549105165021024389658561445767933037995549750784174941834828199\ 0557814977900150186878, 55175999999871561103591475172855648854821189173596899963545183298\ 52586750490332401584052052956512702473818322580223034708770745476510656078433603691766169\ 4979052171664024629750133883359370946441775552, 19660558537798103526402579215402653346470958378147359011925771764948650958656707305974988\ 23208420056614371549892667150477990297802891459517566742248930786890522921548524941103644\ 7358807786269091166330, 52851296036893490588227793173320460496486616005339654971513375310\ 12496316999375706024569932902393811995627122258113998692757931492164048244834601338101076\ 715910965829190241472379844923245638148721472, 44710549606093152116462769122673238073783454638052972957146061640741259639302171650794059\ 81257154025266885514061645503288632291358112020378558058804855627475517322681888568993052\ 5178774578908081005977, 21715892157713278450487066672754569893652393273343584089618071583\ 92289011509089030949634277936958654571022474319625282561975101767657998755289978670170061\ 3721652620881073237189181141483950896893056403, 51901300416348318697248529384566691462223152094408548300859508529211832589225201718905646\ 06595721679246387805362716215024520733700540296611368120613374810642601873658942740073612\ 3043791982336093334687, 32719703281587190833863130300339754049508439524387400742488829767\ 45811377383349514399454392110161398729149579583094497122123346584559358564779182062445389\ 8693061571703646773566445720108505052840155612, 42227436388493580569512380263233204666416492112125935426650659933843119180053917051232550\ 45353201083067046087528824263165530484243705692785982001851490777717301404292867185759066\ 7084835040809089702885, 15268350237176271942746424164488154228512876397939835438227760281\ 96520554920779822898707194181333199486646181560503129928996705385094333356677813169000947\ 732891884540722953032579897551198797853871928, 91436739300449668395408631636579626976083016333599679973541463322104330375427264998038385\ 92933792891363609076270036765571192196767267024592574361208525553622733305964850071775744\ 408506187666911259445, 308682557140491836673199168862195771662004157318660385844542698062\ 99386575455394511519869526102995097955498781044078355861875691608280638820048375170481428\ 147685836108508081882071880459833353385851465, 35788876927576939235879659973439199262768463285983519862227203396251613971096782194240651\ 28288771904855663811543687618931249728394552635462888446843094268081371288895505812439713\ 5129337777305618406134, 40650975964616846586282413981095595169702241790522165871512797940\ 08528466592514366635669162376529649134422783308897657757653110253584931012522875333633865\ 3737675946200106779792432197341147862853587109, 21121459438375126119700534103430147866924645886745166113390062830709048693040831300228887\ 02697919743761310263066721687711279078245415128857719970835796535061842353526607359365102\ 747276992177602421568, 165974754302139131925145168991883559265579480607445559879519713617\ 32562917633345835857281597696186433910428624700207984937156362195919043635413196298162786\ 69293766623906058271918724740257640389931064, 54091889950559580194937687841541942810344549978086583228449622236913387773307450263965677\ 09554319054989051881808833445128938223909789490579765339942033651995163115980569641993804\ 205056299628848479034, 125428475070441664574242265050819573942699841219663869465283411504\ 49584540043793445680595249189677233302431295140041486234328293846858156504681921226080875\ 249687871409218506637288269556334767274228352, 51579086354796956250410239870067883636468071628519188110961884849166750485006162752100698\ 17367973017062716020302153772613016645036232726822307077810915572593223814647128686419067\ 9968397395795407932257, 91489752127109159359444529158504864863421241547810028330509126814\ 41628880307019944878976683176413528154042015880521603948247819857867088831488843148785973\ 016958974162507074180729437946285020017645796, 49234640512288318654176911449504887107087311807317233704848835614913268061469181327006408\ 28634934988555321945847089095241642935524042557717597156933346026601173797348609648114144\ 0621980849996219868579, 49994735046743222760844937123939067865553575323308918408829498284\ 60806822993075143118821249417260062009883860356662681700964236392384734743804564993490205\ 0370838692788364294566337651943265366489479592, 48634744723056242210815386979269307590793683041181643385080083142769245147624018029423130\ 31100599172193891534508290925256718010722668927513913185580317210027287647527243262923300\ 1432919558130587649230, 40783264977689612233804136435748675246436871939309151171414449141\ 78268428055671878851227233678667624767109653879074453475109165333081936988320424403804771\ 3920121361022855692550538045357916132997877353, 36891460132149026763989092590863519096230490909880188170846192446391065083755715888840368\ 48221152834343297356707573207416698437881929369834474583494020067710076721099944851996508\ 9291152660301208902121, 22404050704212253500890940294647768619197933218883652337674353719\ 94385950262967446961941288738691200886036487860034371036284862603652908314659051153846399\ 0161463326245666403138010164301189584672297589, 39351781661288044659941372259393544949596264286676495802684603809767365191029732328756294\ 88888069830015449604790865649355741484026398675326594065712651271716231709304433537161881\ 266759259917243405338, 514648756008773428819804295028335990111338670893035327468874380708\ 69227211821356068851651342595406861603860804175989925470425619947885097885672690124413932\ 907382924025904950893936089193760738058986132, 44776717348722402557549648506329302644024310504880865481129794384143421196213046506840924\ 06119534031413832429357521793396402404527742520478868226266675456076940212583625489077519\ 3092821248154926111253, 47266154750554541067882829646654415660408319892378738475567009849\ 92333741383911885462037185730179700017351313286389750569869024826459680066498839891087440\ 2632160741784320290346106170509741707640136615 ] > /* > OK, that's the enciphered message someone has sent me. I can use my > private key m and ct[1] to discover the scrambling factor: > */ > Modexp(ct[1],m,p); 56935928484689371595142597338660306449348703632345087993423634776475577364941357700044375\ 80988098158995718826917218840665338158420341892151586430040449198162900341137673759532011\ 5800948497734092214687 > /* > This should be the same as sf: > */ > sf; 56935928484689371595142597338660306449348703632345087993423634776475577364941357700044375\ 80988098158995718826917218840665338158420341892151586430040449198162900341137673759532011\ 5800948497734092214687 > /* > It is the same. > Now for the inverse of sf: > */ > isf:=Modexp(ct[1],-m,p); > NaiveDecoding([isf*u mod p : u in ct[2]]); HOW THE CAMEL GOT HIS HUMP by Rudyard Kipling Now this is the next tale, and it tells how the Camel got his big hump. In the beginning of years, when the world was so new and all, and the Animals were just beginning to work for Man, there was a Camel, and he lived in the middle of a Howling Desert because he did not want to work; and besides, he was a Howler himself. So he ate sticks and thorns and tamarisks and milkweed and prickles, most 'scruciating idle; and when anybody spoke to him he said 'Humph!' Just 'Humph!' and no more. Presently the Horse came to him on Monday morning, with a saddle on his back and a bit in his mouth, and said, 'Camel, O Camel, come out and trot like the rest of us.' 'Humph!' said the Camel; and the Horse went away and told the Man. Presently the Dog came to him, with a stick in his mouth, and said, 'Camel, O Camel, come and fetch and carry like the rest of us.' 'Humph!' said the Camel; and the Dog went away and told the Man. Presently the Ox came to him, with the yoke on his neck and said, 'Camel, O Camel, come and plough like the rest of us.' 'Humph!' said the Camel; and the Ox went away and told the Man. At the end of the day the Man called the Horse and the Dog and the Ox together, and said, 'Three, O Three, I'm very sorry for you (with the world so new-and-all); but that Humph-thing in the Desert can't work, or he would have been here by now, so I am going to leave him alone, and you must work double-time to make up for it.' That made the Three very angry (with the world so new-and-all), and they held a palaver, and an indaba, and a punchayet, and a pow-wow on the edge of the Desert; and the Camel came chewing on milkweed most 'scruciating idle, and laughed at them. Then he said 'Humph!' and went away again. Presently there came along the Djinn in charge of All Deserts, rolling in a cloud of dust (Djinns always travel that way because it is Magic), and he stopped to palaver and pow-pow with the Three. 'Djinn of All Deserts,' said the Horse, 'is it right for any one to be idle, with the world so new- and-all?' 'Certainly not,' said the Djinn. 'Well,' said the Horse, 'there's a thing in the middle of your Howling Desert (and he's a Howler himself) with a long neck and long legs, and he hasn't done a stroke of work since Monday morning. He won't trot.' 'Whew!' said the Djinn, whistling, 'that's my Camel, for all the gold in Arabia! What does he say about it?' 'He says "Humph!"' said the Dog; 'and he won't fetch and carry.' 'Does he say anything else?' 'Only "Humph!"; and he won't plough,' said the Ox. 'Very good,' said the Djinn. 'I'll humph him if you will kindly wait a minute.' The Djinn rolled himself up in his dust-cloak, and took a bearing across the desert, and found the Camel most 'scruciatingly idle, looking at his own reflection in a pool of water. 'My long and bubbling friend,' said the Djinn, 'what's this I hear of your doing no work, with the world so new-and-all?' 'Humph!' said the Camel. The Djinn sat down, with his chin in his hand, and began to think a Great Magic, while the Camel looked at his own reflection in the pool of water. 'You've given the Three extra work ever since Monday morning, all on account of your 'scruciating idleness,' said the Djinn; and he went on thinking Magics, with his chin in his hand. 'Humph!' said the Camel. 'I shouldn't say that again if I were you,' said the Djinn; 'you might say it once too often. Bubbles, I want you to work.' And the Camel said 'Humph!' again; but no sooner had he said it than he saw his back, that he was so proud of, puffing up and puffing up into a great big lolloping humph. 'Do you see that?' said the Djinn. 'That's your very own humph that you've brought upon your very own self by not working. To-day is Thursday, and you've done no work since Monday, when the work began. Now you are going to work.' 'How can I,' said the Camel, 'with this humph on my back?' 'That's made a-purpose,' said the Djinn, 'all because you missed those three days. You will be able to work now for three days without eating, because you can live on your humph; and don't you ever say I never did anything for you. Come out of the Desert and go to the Three, and behave. Humph yourself!' And the Camel humphed himself, humph and all, and went away to join the Three. And from that day to this the Camel always wears a humph (we call it 'hump' now, not to hurt his feelings); but he has never yet caught up with the three days that he missed at the beginning of the world, and he has never yet learned how to behave. > CodeToString(65); A > StringToCode("A"); 65 > StringToCode("B"); 66 > StringToCode("C"); 67 > StringToCode("Z"); 90 > StringToCode("a"); 97 > StringToCode("b"); 98 > StringToCode("z"); 122 > StringToCode("1"); 49 > StringToCode("0"); 48 > StringToCode("9"); 57 > StringToCode("!"); 33 > StringToCode("?"); 63 > StringToCode(" "); 32 > NaiveEncoding("A"); [ 165 ] > NaiveEncoding("AB"); [ 165166 ] > NaiveEncoding("ABCDEFG"); [ 165166167168169170171 ] > NaiveEncoding("ABCDEFGHIJKLMNOPQRSTUVWXYZ abcdefghijklmnopqrstuvwxyz 1234567890-+=?"); [ 165166167168169170171172173174175176177178179180181182183184185186187188189190132197198\ 19920020120220320420520620720820921021121221321421521621721821922022122213214915015115215\ 3154155156157148145143, 161163 ] > /* > The function adds 100 to the code numbers of all the characters in the string > and then concatenates these numbers to make a Very Big Number. But it doesn't > tolerate numbers of more than 198 digits: when it gets to 198 digits it > stops that number and starts on a new one. So NaiveEncoding returns a > sequence of numbers, where all but the last term of the sequence have 198 > digits, and the last term has at most 198 digits. > */ > p:=RandomPrime(50); > a:=Random(p-1); > IsPrimitive(a,p); false > a:=Random(p-1); > IsPrimitive(a,p); true > a:=Random(p-1); > IsPrimitive(a,p); false > a:=Random(p-1); > IsPrimitive(a,p); false > a:=Random(p-1); > IsPrimitive(a,p); true > a:=Random(p-1); > IsPrimitive(a,p); false > a:=Random(p-1); > IsPrimitive(a,p); true > /* > It is usually the case that quite a high proportion of the nonzero > residues are primitive roots; so with just a few random selections > you are likely to get one. > */ > EulerPhi(p-1)/(p-1); 3032712201480/9114676075919 > /* > I'll convert that to a real number: > */ > RealField()!EulerPhi(p-1)/(p-1); 0.332728467388153729694698637155 > /* > So in this case about one third of the residues are primitive roots. > Of course a different prime will give a different answer. > */ > p:=RandomPrime(50); > RealField()!EulerPhi(p-1)/(p-1); 0.478258144433330588106525125377 > a:=Random(p-1); > IsPrimitive(a,p); true > p:=RandomPrime(50); > RealField()!EulerPhi(p-1)/(p-1); 0.472427338896609326749342018755 > p:=RandomPrime(50); > RealField()!EulerPhi(p-1)/(p-1); 0.331864904548195491062592198750 > p:=RandomPrime(50); > RealField()!EulerPhi(p-1)/(p-1); 0.250975812819018640209956666810 > a:=Random(p-1); > IsPrimitive(a,p); true > a:=Random(p-1); > IsPrimitive(a,p); false > a:=Random(p-1); > IsPrimitive(a,p); false > a:=Random(p-1); > IsPrimitive(a,p); false > a:=Random(p-1); > IsPrimitive(a,p); false > a:=Random(p-1); > IsPrimitive(a,p); false > a:=Random(p-1); > IsPrimitive(a,p); false > a:=Random(p-1); > IsPrimitive(a,p); false > a:=Random(p-1); > IsPrimitive(a,p); false > a:=Random(p-1); > IsPrimitive(a,p); true > p:= RandomPrime(150); > time PrimitiveRoot(p); 2 Time: 0.250 > p:= RandomPrime(150); > time PrimitiveRoot(p); 14 Time: 0.047 > p:= RandomPrime(160); > time PrimitiveRoot(p); 2 Time: 0.250 > p:= RandomPrime(160); > time PrimitiveRoot(p); 2 Time: 0.109 > p:= RandomPrime(160); > time PrimitiveRoot(p); 2 Time: 0.797 > p:= RandomPrime(170); > time PrimitiveRoot(p); 2 Time: 0.078 > p:= RandomPrime(180); > time PrimitiveRoot(p); 2 Time: 0.406 > p:= RandomPrime(190); > time PrimitiveRoot(p); 3 Time: 0.203 > p:= RandomPrime(200); > time PrimitiveRoot(p); 5 Time: 1.891 > p:= RandomPrime(210); > time PrimitiveRoot(p); 6 Time: 1.172 > p:= RandomPrime(220); > time PrimitiveRoot(p); 5 Time: 3.484 > p:= RandomPrime(230); > time PrimitiveRoot(p); 2 Time: 0.188 > p:= RandomPrime(240); > time PrimitiveRoot(p); 2 Time: 0.438 > p:= RandomPrime(250); > time PrimitiveRoot(p); 5 Time: 1.969 > p:= RandomPrime(260); > time PrimitiveRoot(p); 2 Time: 74.172 > /* > The number b is a primitive root mod p if the order of b mod p is p-1. > The order of an arbitrary nonzero residue will be some divisor of p-1. > To check that the order of b is not some proper divisor of p-1 you > have to know what the proper divisors of p-1 are. In other words, to > prove that b is a primitive root you first have to know the factorization > of p-1, and this could be difficult. In the worst case, (p-1)/2 might > be the product of two distinct primes, and hence difficult to factorize. > I'll bet that is what happened for the 260 bit prime magma chosen above. > */ > Factorization(p-1); [ <2, 1>, <3, 1>, <12503, 1>, <54437, 1>, <766357, 1>, <2268096095311822759383193, 1>, <96444658608103782227588847997629705613, 1> ] > /* > No! More than two odd prime factors. But the factorization took a long time. > If (p-1)/2 had been the product of two large primes the calculations would > have taken even longer. > */ > NNN; 1234008580359152001404256714207198420062013131783042059832932824169051 > PHI; 1234008580359152001404256714206129903746706756074544959994994312268104 > s:=NNN-PHI+1; > /* > Now I have to solve the quadratic x^2 -s*x + NNN = 0. > The discriminant s^2 - 4*NNN had better be a perfect square. > */ > x, E:= IsSquare(s^2-4*NNN); > s; 1068516315306375708497099837938511900948 > x; true > E; 1068516312996614848478647992307985657850 > /* > The roots are (s+E)/2 and (s-E)/2 (by the quadratic formula). > */ > (s+E)/2; 1068516314151495278487873915123248779399 > ppp:=(s+E)/2; > qqq:=(s-E)/2; > Parent(ppp); Rational Field > IsPrime(ppp); false > /* > A rational number cannot be a prime, according to magma. I have to > persuade magma that ppp is really an integer. > */ > ppp:=Integers()!ppp; > ppp; 1068516314151495278487873915123248779399 > /* > It looks the same as before, but ... > */ > Parent(ppp); Integer Ring > IsPrime(ppp); true > qqq; 1154880430009225922815263121549 > /* > But it is a rational number, according to magma. > Let me get the same thing as an integer. > */ > qqq:=(s-E) div 2; > qqq; 1154880430009225922815263121549 > Parent(qqq); Integer Ring > IsPrime(qqq); true > /* > Anyway, the crucial question is whether or not ppp*qqq equals the number NNN > that we were given. > */ > ppp*qqq; 1234008580359152001404256714207198420062013131783042059832932824169051 > NNN; 1234008580359152001404256714207198420062013131783042059832932824169051 > ppp*qqq eq NNN; true > exit; Total time: 319.484 seconds, Total memory usage: 237.56MB