20141209, 22:46  #1 
Dec 2014
2^{2}·5 Posts 
LucasLehmer test
Hey all! I am doing a project for my computing module, and I am writing about Mersenne primes. I was hoping people would give me info on the lucaslehmer test! such as, why it is the reason (or part of the reason?) that the 10 largest primes found are Mersenne primes, and why they are so good for testing if a Mersenne prime is prime, etc. Thank you for all your help :D

20141209, 23:02  #2  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17×251 Posts 
Quote:


20141209, 23:11  #3 
"Gang aft agley"
Sep 2002
7252_{8} Posts 
I think this will be helpful:
Mersenne Primes: History, Theorems and Lists>The LucasLehmer Test and Recent History It has a fun history including high school students becoming record holders. Last fiddled with by only_human on 20141209 at 23:12 Reason: line break 
20141209, 23:21  #4 
Dec 2014
2^{2}·5 Posts 
Do either of you know how to code? for a maths degree you have to take a computing module, so I am very basic at coding. Do you know why this code isn't returning true for 8191?
def isPrime(p): m = 2**p  1 s = 4 print "s_0 = " + str(s) for i in range(1, p1): s = (s**2  2) % m print "s_" + str(i) + " = " + str(s) if s == 0: print "\nTherefore, " + str(p) + " is prime!" else: print "\nTherefore, " + str(p)+ " is composite!" I know that the LL test is fast for checking the primality of Mersenne numbers, and is that why the largest 10 primes are mersenne? I have pieces of information but just want to check it is all correct. Actually, all of this stuff might have been said in the other thread... oh well, just double checking 
20141209, 23:28  #5  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:
Last fiddled with by science_man_88 on 20141209 at 23:31 

20141209, 23:40  #6 
"Gang aft agley"
Sep 2002
2·1,877 Posts 

20141209, 23:41  #7 
Dec 2014
2^{2}·5 Posts 
I am using p = 8191. I got the pseudocode from Wikipedia, here it is:
Lucas–Lehmer(p) var s = 4 var M = 2p − 1 repeat p − 2 times: s = ((s × s) − 2) mod M if s = 0 return PRIME else return COMPOSITE 
20141209, 23:43  #8 
Dec 2014
2^{2}·5 Posts 
even though p obviously shouldn't be 8191 if I am checking 8191 is prime. Any ideas for a better code (and one that actually works!) for the LL test?

20141209, 23:45  #9 
Dec 2014
10100_{2} Posts 
ok! I know why I've f***ed up now, I just blindly assumed that p was the mersenne we were checking, without even checking the code properly... ok thank you!

20141209, 23:46  #10  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
10AB_{16} Posts 
Quote:
Code:
>>> isPrime(127) s_0 = 4 ... s_125 = 0 Therefore, 127 is prime! >>> isPrime(13) s_0 = 4 ... s_11 = 0 Therefore, 13 is prime! >>> isPrime(8191) s_0 = 4 s_8189 = 10383870635347353644793006673052387697290265108910826119381447643351166471208201737229987961042346986289764192792035503235388807709545870480417787597486969311006328784463244682336582252350233171042609920050464689486435026269175789251968977917221098960168806818617568513484347506904686475914540985714281398375916503761290630157789425690555326526724716787009000734715703062612862107715390796752695833318595617448036715928936180716799707369843480854160514918376002505514847572051811102134154481549866326191786330380293923463151815689012293968524639416512393580107630974662899352861343324187504030290238812136553395965946962084835508922570232234134188755667906085315893834583477703478879781962351818929454243610145884898497271198279978606545568258801178426742870958429690415267183856180818867829740302028204147485645220012193257631667681815060765769228829937646798526069286992419635582021537512536090511884215122330613300101132968906959648304520170082413315954174189714192181591813414976614198204261824198772851207329073594924633683397980081121232827336867644495869585651779557108042352688023779400838974194679219487086849219518371199851324517782458921167882235604557906117219624211338367209848503165654793066849216311008311663374145653243371626331554483461031908559179812884619146436142684307482201824039623215356351675705936210477694103579293301482036625805163319205215376622443766139780725655300003833716236113825840422498174885546263839973433792368623046405936631098842322961565320704128416449569460944454066782160207150590875611803039823400515361947719006134519190983042270598279789098872797582714805166372633025416291283108603401788667926913829934006590645880957254286604761098951169481076618485067156354478523911387595284451740361446901434825328580933547283255111822996475369622954334960571323742571681271162326122578403464599391707967996695978891257632636511778412741960514935459962417624299522871776836818146347465998720062931488485385670350833380823892238810160004191473787362013931301434997554139776714842288132945939481107506068534841529806197265133292821733548863500484152017625073790100881174384263666871274201948287906037020171017653555424342861545946924237832643019573034736319035365505548341954484291948170606235179743946932599329165893385358535794614228380261129506143264246435381617981112655466007907374018834029616294771405692015487185974713892666352860454754508707075207110788278388401287251412788688534197761314922856762430436021498487303528908692 Therefore, 8191 is composite! For future reference, your code was not formatted correctly. Use the [code] tags ("#" symbol in the advanced editor) to easily keep your code readable. Last fiddled with by MiniGeek on 20141209 at 23:47 

20141209, 23:47  #11 
Dec 2014
2^{2}·5 Posts 
butttttttttttttttttttttttttttttttttttttt... if you say for i in range(1, 100): this tells you all the numbers from 1, 100 whether they are prime or not
so if I let p = 8191, it should still tell me if it is prime or not 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Modifying the Lucas Lehmer Primality Test into a fast test of nothing  Trilo  Miscellaneous Math  25  20180311 23:20 
A second proof for the LucasLehmer Test  carpetpool  Miscellaneous Math  2  20170730 09:21 
LucasLehmer Test  storm5510  Math  22  20090924 22:32 
Lucas Lehmer test question?  BMgf  Programming  23  20031209 08:52 
about LucasLehmer test and Prime 95  Annunaki  Math  22  20030805 21:52 