Lucas-Lehmer test

[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

[TimSorbet]

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

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.

In what way does this not answer your questions?

[only_human]

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.

[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

[science_man_88]

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.)

[only_human]

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

[Mathsgirl]

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

[Mathsgirl]

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?

[Mathsgirl]

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!

[TimSorbet]

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.

>>> 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.

[Mathsgirl]

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