The Powder Toy

billion57

How can I test very large numbers for primality (as in >2^2000)? I am using the Fermat Primality Test, which works great, until you get to numbers hundreds of digits long.

Or is it my Python script?

def isprime(p,acc=25): #acc indicates number of trials-- default is 25, but I set it to 10 for big tests.
if p in [2,3,5,7,11,13,17,19,23,29,31]: #Doesn't catch numbers that are relatively low
return True
a,z=2,1
while a<acc:
a+=1
if pow(a,p-1,p)!=1:
return False
return True

I need a better way: The largest prime I can catch is only 200 digits long, and that's only checking numbers of the form 2^p-1, where p is a prime.

Any suggestions?

boxmein

Try looking at http://en.wikipedia.org/wiki/Adleman%E2%80%93Pomerance%E2%80%93Rumely_primality_test

A python solution is below:

def isprime(n):
  if n == 2 or n == 3: return True
  if n < 2 or n%2 == 0: return False
  if n < 9: return True
  if n%3 == 0: return False
  r = int(n**0.5)
  f = 5
  while f <= r:
    print '\t',f
    if n%f == 0: return False
    if n%(f+2) == 0: return False
    f +=6
  return True

billion57

-_-

The algorithm in the link (a link to a link to the link, really) can only be understood by math majors.

And that is trial divison.

By the way,

28141120136973731333931529758425841918186623820136007878924193493455151766822763138107 150947456332570741987893085350715373424450164188818017893905487094143918572575715657587064 784183567470706746334971880530508754168216243256805558260711106919466074608730569653608305 715902427749342268661839663091854334625145374842586559823862350460292275078014109071633484 395477810933972600969096770918439445557542211154773437602069796500670878849934780129772778 785328074322365540209315718023104299231675884324570361041108509604397690384503655140223496 253836657512071696616973527322361119268464547517017345270113791481751078208212976289467956 310989607674922504948342540733344141216278339394615392125289320107261366892936888156654916 713951747104526637091757536037741568557665153138276137272816966926335296663637872865397699 416091077771835933360026801245176334514904395983248238364572512194063914326356392256045560 423960043077993619273799005864004207630923208133922624929420763129332680338184715552558206 393088899486655702024038158563135789497797670462618453279567257672892052623117520147862478 133318340150844753867605266122173405797212374144858037253554630220095363010081458675247046 046188620390935552061953282409518951070407932848250954625301518728239971717641406633158043 090086119425783809310647489915944074763284377858488254239211706149382940294832571629792993 889406958773754489480811083452933943278084527297898341351401939124196617994887952103282381 127422187006345411497436572872328434263693488048789934719624033939678576761503716001966502 521682501177931784880120005054228213625505205092097244598958523668274778516191905032548531 150294031321789890051957511943013402772827303906836511205878950601987531218821877886570240 072917841865185899777885103067439458961086452587664156928256641744706161533051448522738845 496350592554106064584273238641095066876363144475142690949329532199242125946951576550091585 211734209232758820633276254086179630329620335725635536040560978321115475359089884338169197 476158171616066205573070003771947300134318155607501590278421649014225445712245469367932349 708949546684254364123477853761943100301390805683834207726286187226461097075065669281028000 339617043439919620020597945655277749138832377567927200655437686407921774415592782723508230 928436835343966791502296761018342437878204200872740286172126845763887336057694912241098665 925773606662414672801589886055234863458808822278555057063092763494150345476771806182963528 662630055092222543184597681941267276030474603441755810292983201712263552344396768163099191 275742063348077190218754138915808715290491878293084121334009104197563130215404784366041784 467577389986320835862079922340851626343754067711697073232139882849437791221719859536058979 022917817682865482878781804150606354600471641040954837772017374688733240685504306958262103 043163363853113840934900213323724634633739774274058966738275442031285748745819603352320056 372293195923692881713752767022604509117350695040250166677552149320736436541994884770103639 093720057578999895807757751266211130579057174494172220160705302439161167059904513042562063 182892977383030951524305497722395149648216018386288614463019360177105467775031092630309947 473976185762073734477254414271353624283608636693271576359830454479718167188016398695475251 463056555718437179168756691403207249785685867185275866024396023352835139449800643270302781 04224144971883680541689784796267391476087696392191 (or 2^11213-1) is prime. My Mersenne prime finder has been running for about 10 hours now.

Primality Testing