mersenneforum.org Lucas-Lehmer test
 Register FAQ Search Today's Posts Mark Forums Read

 2014-12-09, 22:46 #1 Mathsgirl     Dec 2014 22·5 Posts Lucas-Lehmer 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 lucas-lehmer 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
2014-12-09, 23:02   #2
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

102668 Posts

Quote:
 Originally Posted by Mathsgirl 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 lucas-lehmer 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
Quote:
 Originally Posted by R.D. Silverman Interest in Mersenne primes arises because of their connection to the LL test. It is the fastest known test (and there are some reasons for believing it is the fastest any test can be) for finding primes.

 2014-12-09, 23:11 #3 only_human     "Gang aft agley" Sep 2002 2×1,877 Posts I think this will be helpful: Mersenne Primes: History, Theorems and Lists->The Lucas-Lehmer Test and Recent History It has a fun history including high school students becoming record holders. Last fiddled with by only_human on 2014-12-09 at 23:12 Reason: line break
 2014-12-09, 23:21 #4 Mathsgirl     Dec 2014 22·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, p-1): 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
2014-12-09, 23:28   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by Mathsgirl 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, p-1): 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
are you using p=8191 or m=8191 ? that would potentially explain it for me ( but I suck at programming in most peoples eyes.)

Last fiddled with by science_man_88 on 2014-12-09 at 23:31

2014-12-09, 23:40   #6
only_human

"Gang aft agley"
Sep 2002

1110101010102 Posts

Quote:
 Originally Posted by science_man_88 are you using p=8191 or m=8191 ? that would potentially explain it for me ( but I suck at programming in most peoples eyes.)
I believe she is looking at p=13, m=8191

 2014-12-09, 23:41 #7 Mathsgirl     Dec 2014 2010 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
 2014-12-09, 23:43 #8 Mathsgirl     Dec 2014 22×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?
 2014-12-09, 23:45 #9 Mathsgirl     Dec 2014 22×5 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!
2014-12-09, 23:46   #10
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

2×3×23×31 Posts

Quote:
 Originally Posted by Mathsgirl 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?
Because 2^8191-1 is composite? It appears to work correctly, e.g.
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!
(it's actually checking 2^p-1, not p, for primality; the "Therefore, 8191 is composite/prime!" message is incorrect)

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 Mini-Geek on 2014-12-09 at 23:47

 2014-12-09, 23:47 #11 Mathsgirl     Dec 2014 22·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

 Similar Threads Thread Thread Starter Forum Replies Last Post Trilo Miscellaneous Math 25 2018-03-11 23:20 carpetpool Miscellaneous Math 2 2017-07-30 09:21 storm5510 Math 22 2009-09-24 22:32 BMgf Programming 23 2003-12-09 08:52 Annunaki Math 22 2003-08-05 21:52

All times are UTC. The time now is 11:01.

Wed Jul 6 11:01:51 UTC 2022 up 83 days, 9:03, 0 users, load averages: 1.25, 1.19, 1.17