mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2014-12-09, 22:46   #1
Mathsgirl
 
Mathsgirl's Avatar
 
Dec 2014

22·5 Posts
Unhappy 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
Mathsgirl is offline   Reply With Quote
Old 2014-12-09, 23:02   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

Quote:
Originally Posted by Mathsgirl View Post
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 View Post
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?
Mini-Geek is offline   Reply With Quote
Old 2014-12-09, 23:11   #3
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2·1,877 Posts
Default

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
only_human is offline   Reply With Quote
Old 2014-12-09, 23:21   #4
Mathsgirl
 
Mathsgirl's Avatar
 
Dec 2014

2010 Posts
Default

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
Mathsgirl is offline   Reply With Quote
Old 2014-12-09, 23:28   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by Mathsgirl View Post
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
science_man_88 is offline   Reply With Quote
Old 2014-12-09, 23:40   #6
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2·1,877 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
only_human is offline   Reply With Quote
Old 2014-12-09, 23:41   #7
Mathsgirl
 
Mathsgirl's Avatar
 
Dec 2014

22×5 Posts
Unhappy

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 is offline   Reply With Quote
Old 2014-12-09, 23:43   #8
Mathsgirl
 
Mathsgirl's Avatar
 
Dec 2014

22×5 Posts
Default

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 is offline   Reply With Quote
Old 2014-12-09, 23:45   #9
Mathsgirl
 
Mathsgirl's Avatar
 
Dec 2014

22×5 Posts
Default

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!
Mathsgirl is offline   Reply With Quote
Old 2014-12-09, 23:46   #10
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

Quote:
Originally Posted by Mathsgirl View Post
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
Mini-Geek is offline   Reply With Quote
Old 2014-12-09, 23:47   #11
Mathsgirl
 
Mathsgirl's Avatar
 
Dec 2014

1416 Posts
Default

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
Mathsgirl is offline   Reply With Quote
Reply

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 2018-03-11 23:20
A second proof for the Lucas-Lehmer Test carpetpool Miscellaneous Math 2 2017-07-30 09:21
Lucas-Lehmer Test storm5510 Math 22 2009-09-24 22:32
Lucas Lehmer test question? BMgf Programming 23 2003-12-09 08:52
about Lucas-Lehmer test and Prime 95 Annunaki Math 22 2003-08-05 21:52

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

Sun Aug 9 12:11:00 UTC 2020 up 23 days, 7:57, 2 users, load averages: 2.26, 1.94, 1.82

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.