Finding a (large) primitive root of a 300-digit prime

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
Eebster the Great
Posts: 3405
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Finding a (large) primitive root of a 300-digit prime

Postby Eebster the Great » Sat Jan 10, 2015 7:55 pm UTC

My friend and I want to establish a shared secret with a D-H key exchange. However, it turns out that finding primitive roots of large prime numbers (doesn't have to be 300 digits necessarily, but something in that ballpark) can be very difficult. I can't even find large primes with primitive roots already published, let alone efficiently find one on my own.

I know there is no general formula for primitive roots mod p, but is there an efficient way to search for them? If not, are there sufficiently large ones already published? (Sufficiently large so that even though they might already be in log tables or whatever, no attacker could use that to find our private keys in their lifetime.)

For what it's worth, this is more about the practice of setting up the shared secret than about serious security, but that makes me want to get it right even more.

User avatar
Lopsidation
Posts: 183
Joined: Tue Oct 27, 2009 11:29 pm UTC

Re: Finding a (large) primitive root of a 300-digit prime

Postby Lopsidation » Sat Jan 10, 2015 8:59 pm UTC

Disclaimer: this works, but is probably not the fastest or standard way.

Let p be a large prime. If you know the factorization of p-1, you can easily test whether a given number r is a primitive root mod p. [Fact: r is a primitive root mod p unlesss there is a prime factor F of p-1 such that r(p-1)/F=1 (mod p).] Using this, you can just try a bunch of random numbers r until you find a primitive root.

There are known algorithms to generate a random number between 1 and N along with its factorization. You can use this algorithm to generate p-1, and keep trying until you get a p which is prime.

I tried this to generate a random ~100-digit prime. It's slow, but after a minute or two I got:
p = 7243469162906133262707138361729247674528418426076702186281286038623238274842547507072974617594640311,
p-1 factorizes as 201139*23*5*3*2 times one large prime factor, and a random primitive root is 3242736143229285405697273596419677873912657748731448981302390864459158863881443495029809033284732127.

If you want larger primes, you should optimize the "generate random factored number" step. Say, by multiplying two large primes and making that p-1.

Nyktos
Posts: 138
Joined: Mon Mar 02, 2009 4:02 pm UTC

Re: Finding a (large) primitive root of a 300-digit prime

Postby Nyktos » Sat Jan 10, 2015 11:07 pm UTC

Eebster the Great wrote:If not, are there sufficiently large ones already published? (Sufficiently large so that even though they might already be in log tables or whatever, no attacker could use that to find our private keys in their lifetime.)
Yes.

User avatar
Eebster the Great
Posts: 3405
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: Finding a (large) primitive root of a 300-digit prime

Postby Eebster the Great » Sun Jan 11, 2015 7:49 am UTC

Lopsidation wrote:Disclaimer: this works, but is probably not the fastest or standard way.
Let p be a large prime. If you know the factorization of p-1, you can easily test whether a given number r is a primitive root mod p. [Fact: r is a primitive root mod p unlesss there is a prime factor F of p-1 such that r(p-1)/F=1 (mod p).] Using this, you can just try a bunch of random numbers r until you find a primitive root.

Thanks! I managed to find that on stack exchange after posting here. It's still pretty tedious of course, but as you showed it evidently works.

There are known algorithms to generate a random number between 1 and N along with its factorization. You can use this algorithm to generate p-1, and keep trying until you get a p which is prime.

I tried this to generate a random ~100-digit prime. It's slow, but after a minute or two I got:
p = 7243469162906133262707138361729247674528418426076702186281286038623238274842547507072974617594640311,
p-1 factorizes as 201139*23*5*3*2 times one large prime factor, and a random primitive root is 3242736143229285405697273596419677873912657748731448981302390864459158863881443495029809033284732127.

Impressive.

If you want larger primes, you should optimize the "generate random factored number" step. Say, by multiplying two large primes and making that p-1.

But p should be prime, because otherwise this method doesn't work.

Nyktos wrote:
Eebster the Great wrote:If not, are there sufficiently large ones already published? (Sufficiently large so that even though they might already be in log tables or whatever, no attacker could use that to find our private keys in their lifetime.)
Yes.


Awesome, that's exactly what I was looking for. Does it matter that they all have generator 2? I assume that's just the result of the algorithm they used to find p, but does it raise any security concerns? Also, why do they all claim to be multiples of pi?


E: I'm still having problems.

For instance, if I use the 8192-bit example they gave and convert to decimal, I get this:
Spoiler:
109074813561941592945029492935978450034815512495317221177410110696615016892278563902853247384883 \
681776971216416907643296922469875267467766273999426578543723359615704597092233804069810050786103 \
304731233182398243527947570019986097161273254052879655450286791974677698375939147598714252131587 \
871957751914881183087991942693995848708754096571641916746749932615622652967520917227700137759124 \
814756378288055886108332717415401497513489312511601577631889029596069801161415772128252753946881 \
651931933333750311477719236041228172101895583437761548046847925274886732036238535559660179512280 \
675621771357981987063432156190781325515370395079527123265240489498386949217448165230380349888136 \
621050864726366837651413103110233683748899977574404673365182723939535354034841487285463971929469 \
432345018688418982254454064722698729216069318473465494190693664657613026097219328031717169641897 \
155395416144619175909371952495111670557736207348131929604120128351615426904438925772770028968411 \
946028348045230620413002491387998113590802698386820596931816781968085099864969441690795271290496 \
240493777578969891720735635522745506618381584766913553054975543981948032173292586906913614608532 \
638233462874545639807160305805163420938670870330654590319960852382451372962513665912822110096773 \
545051995240424819826281383109737426165038001727791697532413484657468130733701738083035368062321 \
633694947130619168643824930568641338023104609645095359408937554028503729247092939511402830554745 \
258496207430943815182543790297601289174935519867842060372203490031136489304649576140433393868614 \
003784803091629254327368453364003263763910077450237154247930247369838869289242094647894773380038 \
778274141778648477019010886787977899163321862864053398261932246615488301145229189025233648723608 \
665439609385389862880581317755916207636315443649447750787129411984163786770172216660983120184548 \
407807051804133686980839845462558692120130818563888808269940868653604519264956919811035365994311 \
180230063610650986502394366182943642656300791728205089442938884174888539829070774305297360535927 \
751574961973082377321589475512176146788786532770711557380426451920634921585019519536481338752681 \
174247413154980213024650634120702033579770678070540694527543880626597851620970679570257924407538 \
049023174103086261496878330620786968786810842363997198320907762475808049998827559139278726762718 \
244289280964687422826317243564236858826013916196283612148196609274532548864105423883929513899297 \
9335446110090325230955276870524611359124918392740353154294858383359

I then use the following Python code to check that [2^a (mod p)]^b (mod p) = [2^b (mod p)]^a (mod p), the shared secret, for some arbitrary integers a and b:

Code: Select all

def mod_pow(g, a, p):
   result = 1
   g = g % p
   while a > 0:
      if a % 2 == 1:
         result = (result * g) % p
      a >>= 1
      g = (g * g) % p
   return result

p = [snip]
g = 2
a = 1234567890
b = 9876543210

print(mod_pow(mod_pow(g,a,p),b,p))
print(mod_pow(mod_pow(g,b,p),a,p))

And for whatever reason, the two numbers do not match. What am I doing wrong? Is there something wrong with Python's handling of arbitrary precision ints?

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Finding a (large) primitive root of a 300-digit prime

Postby jaap » Sun Jan 11, 2015 10:03 am UTC

Eebster the Great wrote:I then use the following Python code to check that [2^a (mod p)]^b (mod p) = [2^b (mod p)]^a (mod p), the shared secret, for some arbitrary integers a and b:

Code: Select all

p = [snip]
g = 2
a = 1234567890
b = 9876543210

print(mod_pow(mod_pow(g,a,p),b,p))
print(mod_pow(mod_pow(g,b,p),a,p))

And for whatever reason, the two numbers do not match. What am I doing wrong? Is there something wrong with Python's handling of arbitrary precision ints?

I'm no Python expert, but that code seems correct to me. I calculated this in Java using BigInteger, and it gave the following results.
g^a mod p =
Spoiler:
614233908933871030206621792178351526949808282937937293148949583818431281510
198801656952114660167085666201607139767049778206361321201227981018172477925
423981836871435230579236913076671959495527260242978130034760195130643498975
982547516498028842545865191234206318382782582989353349535275875536421178970
093055426009662142695583445312189168613252287843591905738263222525130395361
478011422805290392303878030409207301393944355081727509355829295734417754266
195445728820421154087826574888491587625252660831714010162740488767121934241
075230761189013406800864980102088030093020820166175923281408109727334095175
113585135249690698939984513309731399358490365285307925327391291670444999403
473812001840727875029898654997433402223973893569195247795643076310866741740
975070621409878010111725853531274464653311098822289820989645739750901789924
375073103658423765496626222199985320055068441053062884003143954995851588946
083571297179317953352574017619889050219684036334438649836210763845669779506
674624758595283545063123582250423362021850758499092610355151762532531145899
055282261295730666158464946797693569844906549530677022567916567689956709688
235647846425641911663598169658066544682979373590282796035341826528977396368
476774607638954539600401367683084850322756518756288555801977701535754706495
225901152404066684273670940214739041707834849461187370901244266813993143587
972698111932541825170831588351978976406590472460776306756831865708484654876
963830809962765344934619629790209002226945379907616166697979867702436001056
360390395623466822932614379882986082556910997745149411284102355461536685269
215138088231203265546933827887557993987652077145506371083983356223943845635
100485935298104926844722574367373223589884572709138294450483182859302473079
807447786428368728132767419720251598689408809514529967709302599047970283842
468251025807332606340930263590227307600611219424982530394836121482937202831
429541995139412096290650386134777667360041892788137328961529782908218009134
588887985014263369510389094064993332649682981194027932154722518069292386322
627771603009110724951436340181994889826347591883806585288918133643662779403
830645671973533992386778185436564050890632627673070678306019696101608895147
955814363887200741351653546110989040003924692254972113260234489221902938255
831726814664634402635610008742265243642008897199549761586071310560783700962
028247598231676475774363644524818435546865997931785088495531064557465968483
524883312631426467140734017243375891956130529127503629213812233634

g^b mod p =
Spoiler:
140021334468807771409649086562968651361613545072009419990509147324656244356
047064096518039479393484726455160754606738679380259747983571072525419309704
167804353072601137867957206463254881425488547761787197795373785246782426881
058420493248700708331450762959695785601094487151258531134920576154158713380
871544487621479576484737181949195267880002611985130172831208862115068409811
505535597243679120411498738688076364967877651009787657221226685760005187203
086985570128717388601849666032718473834479123095387480925838958499539704871
927771900840987684931430465622514319738721805327885962624885740466980935764
139894867655001536597902227160531026158538399839108275263276876138674599688
984765698181214101690008654280903952977241742770817280045049800266396042226
193728581237151207821122217451467478136596306054359146523789095305160341143
816472473928757374788226796782969832417079108673617842297859594779315336688
980480846919011254965403948871639672379505785574774997924154926490750505840
969264819978550320147443653644806982636702055443246493517429827202644310417
864361901680535058957009739079398768181652446788890860887137501127299450831
154409509642063282538374368964605910864959522571160536613844715813192346524
213563816479770559333396730099607556627485162093064310587041293801384821422
531184237780579475329937254734340929052881688248435734178840248312858547760
314385243555552481943869672973195294412713169431715685312570885982786971047
782248499103658796008190217458672018810083128232571849968661421219271251806
946439253126616653837483834782518511855745790720224491720012079017913181034
625420619963887857259607628941612978016298896842163623548119877455336131150
560984341534715502735110188084113685669061748492808546754081045704254065381
390450705440604882609158571140665424492371272969276463158225660399868917295
822958694074425531145461422701475080753049970448242164949274194778673771572
646621971680353146488604960971743714950257338670916073523572388774592093924
008687560657050943779563038687379034968015511717621046416080672685808680333
672669850330677511849714653439611750147017117378406208861460199703938914045
857208081516311218651229209801203091096067391421731755507240423355224291520
860233893623980995298313412190989598779952274302428481378226926206280458153
018247885959935080381959760932450612930334175527381378894478319711972357372
619644789104372099053106736069721133601351803455651446125915330919334194034
282624074469774154938540344291274358761292630475497377645704033949


g^ab mod p =
Spoiler:
715197035699950609607113339826804496967096847627040598116510523687865002377
224646101785162839497941926921941382100790448691911743014073451427008423006
991753123213760931773118412338594672437012221259971530092535971055285192857
028972742682685500492792664582546010678763274147707037059079063083444504385
621932844157146136824415848596297374180875836919467334479009872932021231123
656535714076137211990498104457294732843666604403987881749470351545089363298
856329766289890343032769316585237892157762852936241504714638426372415364190
249512822125627026151996814856220815879181263921572693913457950926938255144
719911229146258150984858150096345471465900177752665667613455598304257621080
060250443822747829717144913871637091626431235219625827408990171798546837112
342238480311532847968683369463849036914803560154490832134457898322248735840
730132313885399835589283658359285863983932391074259533542043974519844075762
089594169013864077417695613086142649364611046567371760910176630124884782524
902751762984866544849833093670310589103168486379384557189503713955025351239
410482310382646673903903088698214784597904830918624552003733908705921226698
074939840928079291169594612482205799362929531025292643826805563559333358878
316598478523205490372988796541488365425355039013270534267597401196111025729
199704459085920030220034912217964564781127967505529465351826385307751008698
959726372976193185410779913107378400557650689138547121854344291011447629741
246116076471843663097805671899762053740527300947149579835673119489714977108
083475562424033727676290638894976411885952104486293435466794100540232732144
110669132373170850578900244855770760197324191000042678090147854501009431648
173718361128980674389887585946465054569144186010762158526167040451326132522
449963786340251412885176256556230754975886163944327764371789938013576091284
046566963873678459081300355134656444599120924056538445795684281640643839561
483449036540028763324708847317179756516470045110039856244940850040864876428
542505510873072734716394476082974233840120442316171059928638160509050489547
000690799955640758515540824204193717810382288442435934126578926285864317648
788675049448246628828838369509799055165768227460321477689972784892606389433
890134127786886158108474214685705374315422709960923814293830805891057340429
949495080538022257114863306444113226311865005371519864595690223176240860337
425083672610951498486020350556347394724571706641177155734858627160292722033
442534650169762738884449108589458918738343587870584001924942310409

I also confirmed that p is a prime (with extremely high probability), so your conversion is likely correct.

Nyktos
Posts: 138
Joined: Mon Mar 02, 2009 4:02 pm UTC

Re: Finding a (large) primitive root of a 300-digit prime

Postby Nyktos » Sun Jan 11, 2015 7:30 pm UTC

Using Python's built-in pow() function and reading the number in as hex directly I'm getting that it works fine.

As I far as I understand the generator being 2 doesn't matter much, and it's probably faster to implement that way. The use of pi is likely to provide a source of pseudo-randomness that can't easily be manipulated by the NSA or what have you.

User avatar
Eebster the Great
Posts: 3405
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: Finding a (large) primitive root of a 300-digit prime

Postby Eebster the Great » Mon Jan 12, 2015 1:52 am UTC

Nyktos wrote:Using Python's built-in pow() function and reading the number in as hex directly I'm getting that it works fine.

You're taking an 8192-bit exponent directly? I don't get it. Wouldn't that take forever? Anyway, I took the script straight from Wikipedia. How did you modify it to give the correct result?

As I far as I understand the generator being 2 doesn't matter much, and it's probably faster to implement that way. The use of pi is likely to provide a source of pseudo-randomness that can't easily be manipulated by the NSA or what have you.

Makes sense.

Nyktos
Posts: 138
Joined: Mon Mar 02, 2009 4:02 pm UTC

Re: Finding a (large) primitive root of a 300-digit prime

Postby Nyktos » Mon Jan 12, 2015 2:15 am UTC

Eebster the Great wrote:You're taking an 8192-bit exponent directly? I don't get it. Wouldn't that take forever? Anyway, I took the script straight from Wikipedia. How did you modify it to give the correct result?
pow() implements modular exponentiation if you pass it a third parameter.

I didn't modify your script directly, I just tried the numbers at the REPL. But this works:
Spoiler:

Code: Select all

p = int("""
      FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
      29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
      EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
      E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
      EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
      C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
      83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
      670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B
      E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9
      DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510
      15728E5A 8AAAC42D AD33170D 04507A33 A85521AB DF1CBA64
      ECFB8504 58DBEF0A 8AEA7157 5D060C7D B3970F85 A6E1E4C7
      ABF5AE8C DB0933D7 1E8C94E0 4A25619D CEE3D226 1AD2EE6B
      F12FFA06 D98A0864 D8760273 3EC86A64 521F2B18 177B200C
      BBE11757 7A615D6C 770988C0 BAD946E2 08E24FA0 74E5AB31
      43DB5BFC E0FD108E 4B82D120 A9210801 1A723C12 A787E6D7
      88719A10 BDBA5B26 99C32718 6AF4E23C 1A946834 B6150BDA
      2583E9CA 2AD44CE8 DBBBC2DB 04DE8EF9 2E8EFC14 1FBECAA6
      287C5947 4E6BC05D 99B2964F A090C3A2 233BA186 515BE7ED
      1F612970 CEE2D7AF B81BDD76 2170481C D0069127 D5B05AA9
      93B4EA98 8D8FDDC1 86FFB7DC 90A6C08F 4DF435C9 34028492
      36C3FAB4 D27C7026 C1D4DCB2 602646DE C9751E76 3DBA37BD
      F8FF9406 AD9E530E E5DB382F 413001AE B06A53ED 9027D831
      179727B0 865A8918 DA3EDBEB CF9B14ED 44CE6CBA CED4BB1B
      DB7F1447 E6CC254B 33205151 2BD7AF42 6FB8F401 378CD2BF
      5983CA01 C64B92EC F032EA15 D1721D03 F482D7CE 6E74FEF6
      D55E702F 46980C82 B5A84031 900B1C9E 59E7C97F BEC7E8F3
      23A97A7E 36CC88BE 0F1D45B7 FF585AC5 4BD407B2 2B4154AA
      CC8F6D7E BF48E1D8 14CC5ED2 0F8037E0 A79715EE F29BE328
      06A1D58B B7C5DA76 F550AA3D 8A1FBFF0 EB19CCB1 A313D55C
      DA56C9EC 2EF29632 387FE8D7 6E3C0468 043E8F66 3F4860EE
      12BF2D5B 0B7474D6 E694F91E 6DBE1159 74A3926F 12FEE5E4
      38777CB6 A932DF8C D8BEC4D0 73B931BA 3BC832B6 8D9DD300
      741FA7BF 8AFC47ED 2576F693 6BA42466 3AAB639C 5AE4F568
      3423B474 2BF1C978 238F16CB E39D652D E3FDB8BE FC848AD9
      22222E04 A4037C07 13EB57A8 1A23F0C7 3473FC64 6CEA306B
      4BCBC886 2F8385DD FA9D4B7F A2C087E8 79683303 ED5BDD3A
      062B3CF5 B3A278A6 6D2A13F8 3F44F82D DF310EE0 74AB6A36
      4597E899 A0255DC1 64F31CC5 0846851D F9AB4819 5DED7EA1
      B1D510BD 7EE74D73 FAF36BC3 1ECFA268 359046F4 EB879F92
      4009438B 481C6CD7 889A002E D5EE382B C9190DA6 FC026E47
      9558E447 5677E9AA 9E3050E2 765694DF C81F56E8 80B96E71
      60C980DD 98EDD3DF FFFFFFFF FFFFFFFF
""".replace(" ", "").replace("\n", ""), 16)

ga = pow(2, 1234567890, p)
gb = pow(2, 9876543210, p)

assert pow(ga, 9876543210, p) == pow(gb, 1234567890, p)

User avatar
Eebster the Great
Posts: 3405
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: Finding a (large) primitive root of a 300-digit prime

Postby Eebster the Great » Mon Jan 12, 2015 10:36 pm UTC

Nyktos wrote:
Eebster the Great wrote:You're taking an 8192-bit exponent directly? I don't get it. Wouldn't that take forever? Anyway, I took the script straight from Wikipedia. How did you modify it to give the correct result?
pow() implements modular exponentiation if you pass it a third parameter.

I didn't modify your script directly, I just tried the numbers at the REPL. But this works:
Spoiler:

Code: Select all

p = int("""
      FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
      29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
      EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
      E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
      EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
      C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
      83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
      670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B
      E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9
      DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510
      15728E5A 8AAAC42D AD33170D 04507A33 A85521AB DF1CBA64
      ECFB8504 58DBEF0A 8AEA7157 5D060C7D B3970F85 A6E1E4C7
      ABF5AE8C DB0933D7 1E8C94E0 4A25619D CEE3D226 1AD2EE6B
      F12FFA06 D98A0864 D8760273 3EC86A64 521F2B18 177B200C
      BBE11757 7A615D6C 770988C0 BAD946E2 08E24FA0 74E5AB31
      43DB5BFC E0FD108E 4B82D120 A9210801 1A723C12 A787E6D7
      88719A10 BDBA5B26 99C32718 6AF4E23C 1A946834 B6150BDA
      2583E9CA 2AD44CE8 DBBBC2DB 04DE8EF9 2E8EFC14 1FBECAA6
      287C5947 4E6BC05D 99B2964F A090C3A2 233BA186 515BE7ED
      1F612970 CEE2D7AF B81BDD76 2170481C D0069127 D5B05AA9
      93B4EA98 8D8FDDC1 86FFB7DC 90A6C08F 4DF435C9 34028492
      36C3FAB4 D27C7026 C1D4DCB2 602646DE C9751E76 3DBA37BD
      F8FF9406 AD9E530E E5DB382F 413001AE B06A53ED 9027D831
      179727B0 865A8918 DA3EDBEB CF9B14ED 44CE6CBA CED4BB1B
      DB7F1447 E6CC254B 33205151 2BD7AF42 6FB8F401 378CD2BF
      5983CA01 C64B92EC F032EA15 D1721D03 F482D7CE 6E74FEF6
      D55E702F 46980C82 B5A84031 900B1C9E 59E7C97F BEC7E8F3
      23A97A7E 36CC88BE 0F1D45B7 FF585AC5 4BD407B2 2B4154AA
      CC8F6D7E BF48E1D8 14CC5ED2 0F8037E0 A79715EE F29BE328
      06A1D58B B7C5DA76 F550AA3D 8A1FBFF0 EB19CCB1 A313D55C
      DA56C9EC 2EF29632 387FE8D7 6E3C0468 043E8F66 3F4860EE
      12BF2D5B 0B7474D6 E694F91E 6DBE1159 74A3926F 12FEE5E4
      38777CB6 A932DF8C D8BEC4D0 73B931BA 3BC832B6 8D9DD300
      741FA7BF 8AFC47ED 2576F693 6BA42466 3AAB639C 5AE4F568
      3423B474 2BF1C978 238F16CB E39D652D E3FDB8BE FC848AD9
      22222E04 A4037C07 13EB57A8 1A23F0C7 3473FC64 6CEA306B
      4BCBC886 2F8385DD FA9D4B7F A2C087E8 79683303 ED5BDD3A
      062B3CF5 B3A278A6 6D2A13F8 3F44F82D DF310EE0 74AB6A36
      4597E899 A0255DC1 64F31CC5 0846851D F9AB4819 5DED7EA1
      B1D510BD 7EE74D73 FAF36BC3 1ECFA268 359046F4 EB879F92
      4009438B 481C6CD7 889A002E D5EE382B C9190DA6 FC026E47
      9558E447 5677E9AA 9E3050E2 765694DF C81F56E8 80B96E71
      60C980DD 98EDD3DF FFFFFFFF FFFFFFFF
""".replace(" ", "").replace("\n", ""), 16)

ga = pow(2, 1234567890, p)
gb = pow(2, 9876543210, p)

assert pow(ga, 9876543210, p) == pow(gb, 1234567890, p)

When I run that on repl.it, I get an assertion error. i.e. ga^b != gb^a.

Nyktos
Posts: 138
Joined: Mon Mar 02, 2009 4:02 pm UTC

Re: Finding a (large) primitive root of a 300-digit prime

Postby Nyktos » Tue Jan 13, 2015 2:25 am UTC

Hmm, that's odd. My only guess is that it might be a Python 2 vs 3 error (I used the latter) but I can't find anything about the behaviour of pow() changing.

User avatar
Eebster the Great
Posts: 3405
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: Finding a (large) primitive root of a 300-digit prime

Postby Eebster the Great » Tue Jan 13, 2015 2:48 am UTC

It can't just be Pow(), since the script I used initially gave the same results with the custom modular power function. I think it's more likely a problem with handling very large integers.

User avatar
PM 2Ring
Posts: 3700
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Finding a (large) primitive root of a 300-digit prime

Postby PM 2Ring » Tue Jan 13, 2015 3:27 am UTC

Eebster the Great wrote:
Nyktos wrote:
Eebster the Great wrote:You're taking an 8192-bit exponent directly? I don't get it. Wouldn't that take forever? Anyway, I took the script straight from Wikipedia. How did you modify it to give the correct result?
pow() implements modular exponentiation if you pass it a third parameter.

I didn't modify your script directly, I just tried the numbers at the REPL. But this works:
Spoiler:

Code: Select all

p = int("""
      FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
      29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
      EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
      E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
      EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
      C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
      83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
      670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B
      E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9
      DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510
      15728E5A 8AAAC42D AD33170D 04507A33 A85521AB DF1CBA64
      ECFB8504 58DBEF0A 8AEA7157 5D060C7D B3970F85 A6E1E4C7
      ABF5AE8C DB0933D7 1E8C94E0 4A25619D CEE3D226 1AD2EE6B
      F12FFA06 D98A0864 D8760273 3EC86A64 521F2B18 177B200C
      BBE11757 7A615D6C 770988C0 BAD946E2 08E24FA0 74E5AB31
      43DB5BFC E0FD108E 4B82D120 A9210801 1A723C12 A787E6D7
      88719A10 BDBA5B26 99C32718 6AF4E23C 1A946834 B6150BDA
      2583E9CA 2AD44CE8 DBBBC2DB 04DE8EF9 2E8EFC14 1FBECAA6
      287C5947 4E6BC05D 99B2964F A090C3A2 233BA186 515BE7ED
      1F612970 CEE2D7AF B81BDD76 2170481C D0069127 D5B05AA9
      93B4EA98 8D8FDDC1 86FFB7DC 90A6C08F 4DF435C9 34028492
      36C3FAB4 D27C7026 C1D4DCB2 602646DE C9751E76 3DBA37BD
      F8FF9406 AD9E530E E5DB382F 413001AE B06A53ED 9027D831
      179727B0 865A8918 DA3EDBEB CF9B14ED 44CE6CBA CED4BB1B
      DB7F1447 E6CC254B 33205151 2BD7AF42 6FB8F401 378CD2BF
      5983CA01 C64B92EC F032EA15 D1721D03 F482D7CE 6E74FEF6
      D55E702F 46980C82 B5A84031 900B1C9E 59E7C97F BEC7E8F3
      23A97A7E 36CC88BE 0F1D45B7 FF585AC5 4BD407B2 2B4154AA
      CC8F6D7E BF48E1D8 14CC5ED2 0F8037E0 A79715EE F29BE328
      06A1D58B B7C5DA76 F550AA3D 8A1FBFF0 EB19CCB1 A313D55C
      DA56C9EC 2EF29632 387FE8D7 6E3C0468 043E8F66 3F4860EE
      12BF2D5B 0B7474D6 E694F91E 6DBE1159 74A3926F 12FEE5E4
      38777CB6 A932DF8C D8BEC4D0 73B931BA 3BC832B6 8D9DD300
      741FA7BF 8AFC47ED 2576F693 6BA42466 3AAB639C 5AE4F568
      3423B474 2BF1C978 238F16CB E39D652D E3FDB8BE FC848AD9
      22222E04 A4037C07 13EB57A8 1A23F0C7 3473FC64 6CEA306B
      4BCBC886 2F8385DD FA9D4B7F A2C087E8 79683303 ED5BDD3A
      062B3CF5 B3A278A6 6D2A13F8 3F44F82D DF310EE0 74AB6A36
      4597E899 A0255DC1 64F31CC5 0846851D F9AB4819 5DED7EA1
      B1D510BD 7EE74D73 FAF36BC3 1ECFA268 359046F4 EB879F92
      4009438B 481C6CD7 889A002E D5EE382B C9190DA6 FC026E47
      9558E447 5677E9AA 9E3050E2 765694DF C81F56E8 80B96E71
      60C980DD 98EDD3DF FFFFFFFF FFFFFFFF
""".replace(" ", "").replace("\n", ""), 16)

ga = pow(2, 1234567890, p)
gb = pow(2, 9876543210, p)

assert pow(ga, 9876543210, p) == pow(gb, 1234567890, p)

When I run that on repl.it, I get an assertion error. i.e. ga^b != gb^a.


Nyktos's code works fine for me in the interactive interpreter on Python 2.6.6

Nyktos
Posts: 138
Joined: Mon Mar 02, 2009 4:02 pm UTC

Re: Finding a (large) primitive root of a 300-digit prime

Postby Nyktos » Tue Jan 13, 2015 4:06 am UTC

Interesting. Eebster's post made me think it might be something to do with Python 2 distinguishing between int and long, but indeed it works fine on 2.7 on my machine.

User avatar
Lopsidation
Posts: 183
Joined: Tue Oct 27, 2009 11:29 pm UTC

Re: Finding a (large) primitive root of a 300-digit prime

Postby Lopsidation » Tue Jan 13, 2015 11:53 am UTC

Looks like a bug in repl.it.

User avatar
Eebster the Great
Posts: 3405
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: Finding a (large) primitive root of a 300-digit prime

Postby Eebster the Great » Wed Jan 14, 2015 2:56 am UTC

Well that explains it.

Thanks, guys.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 13 guests