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

 2014-12-09, 23:49 #12 Mathsgirl     Dec 2014 22·5 Posts but it also said 11 wasn't prime, so just forget about all these posts... just ignore me
 2014-12-09, 23:52 #13 Mathsgirl     Dec 2014 22·5 Posts @minigeek! thank you, my computer science friend sent me this code (passing the blame on her) and she commented it wrong, which is why I was getting confused. thank you
2014-12-09, 23:59   #14
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

Quote:
 Originally Posted by Mini-Geek 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.

I think I see something else that makes me think the pseudocode goes from S(0) to S(p-2) and mathgirls code goes from s(0) to s(p-1) ?

2014-12-10, 00:02   #15
only_human

"Gang aft agley"
Sep 2002

2·1,877 Posts

There's nothing wrong with thrashing around a bit when learning coding (or even much, much later sometimes)
Here are the intermediate values when checking if 27 - 1 is prime, using the LL test:
http://www.mersenne.org/various/math.php#lucas-lehmer
Quote:
 S0 = 4 S1 = (4 * 4 - 2) mod 127 = 14 S2 = (14 * 14 - 2) mod 127 = 67 S3 = (67 * 67 - 2) mod 127 = 42 S4 = (42 * 42 - 2) mod 127 = 111 S5 = (111 * 111 - 2) mod 127 = 0

Last fiddled with by only_human on 2014-12-10 at 00:25 Reason: I messed up too. not 7. 127

 2014-12-10, 00:50 #16 Mathsgirl     Dec 2014 22×5 Posts I will look into how to write a better one tomorrow then, I really I hope I can get it all done by thrusday! in python, if you put the range(1, n) it actually goes, from 1 to (n-1). So I think my code goes from 1 to p-1 so that means it will actually go to 1 to p-2. Thanks for all your help guys (though correct me if I'm wrong!)
 2014-12-10, 00:51 #17 only_human     "Gang aft agley" Sep 2002 2·1,877 Posts So a confusing element here is that Mersenne primes in the form 2p - 1 must have a prime exponent otherwise the number is composite, but that p is not the prime being tested. The number being tested for primality is 2p - 1. Even on this forum we mess around with terminology and might talk about a Mersenne prime sometimes referring to the exponent, sometimes the entire number, and sometimes referring to the ordinal number from a list of known Mersenne primes. Last fiddled with by only_human on 2014-12-10 at 00:55
2014-12-10, 03:28   #18
TheMawn

May 2013
East. Always East.

11×157 Posts

The first issue I can see is you're confusing P with MP = 2P - 1. You're trying to prove the primality of MP, not P.

For example, if you run P = 8191, you're testing the primality of M8191 = 28191 - 1 =~ 5.454 x 102465, but your output is commenting on the primality of 8191 which is wrong.

The second issue is you're going from i = 1 to i = P - 1, which is one too many. You want P - 2 iterations, not P - 1.

With the above example, you're using 8089 iterations to check that 2465-digit number. You don't run MP - 2 iterations, You run P - 2 iterations.

Quote:
 Originally Posted by only_human Even on this forum we mess around with terminology and might talk about a Mersenne prime sometimes referring to the exponent, sometimes the entire number, and sometimes referring to the ordinal number from a list of known Mersenne primes.
Yes. It takes a bit of experience on this forum to figure out the context of what we mean.

Saying M57,885,161 is shorthand for saying M57,885,161 because we're too lazy to put the subscript tags every time we refer to a number.

It gets confusing because M57,885,161 = M48, currently, because we also use that notation to refer to the Mersenne Primes by rank, where M48 is the 48th Mersenne Prime currently known.

Eventually, M127 is going to mean two different things unless we specify: either M127 (= 2127 - 1) or the 127th Mersenne Prime. For now, that's not an issue.

More confusing yet is the fact that we'll sometimes skip the M bit and just say something like: "I'm going to do ECM on the 300,000 to 400,000 range" which could be referring to the exponents or to the number itself, although we exceedingly rarely refer to Mersenne Numbers by their actual numbers because even the "tiny" ones are too big.

The worst part is when we refer to 100-million digit Mersennes and talk about the 100M range. I always make sure to say the 100M digits range, but some people don't, or they forget. So 100M could mean 100-million digit mersennes OR the M100,000,000 range.

Yup. Confusing.

Last fiddled with by TheMawn on 2014-12-10 at 03:47 Reason: Looks like we're okay now.

2014-12-10, 06:50   #19
only_human

"Gang aft agley"
Sep 2002

2·1,877 Posts

As for complexity, continuing on from what TheMawn about the LL test here, each inner loop of the algorithm needs a squaring, a subtraction and (effectively benefits from) a mod operation.
This link points to Wikipedia's LL Test Time complexity

Because Mersenne numbers are one less than a power of two, calculating within the modulus of a Mersenne number can be quite cheap computationally. Setting that aside for now, the big part of the inner loop complexity is the squaring operation.

I'm not conversant in what is being done here. Fast multiplication for large numbers use FFTs or similar to do convolutions for multiplication. I believe in particular the IBDWT avoids needing zero padding and perhaps the mod operation ends up being essentially free too. I am absolutely ignorant in this area so will stop there.

Going slightly off-topic to mention something to forum members:
Just to show that reviewing what we think we know is nice, I was was unaware of this on that Wikipedia page linked to above:
Quote:
 Currently the most efficient known multiplication algorithm, Fürer's algorithm, needs p log p 2[I]O[/I](log [SUP]* [I]p[/I])[/SUP] time to multiply two p-bit numbers.
I'd never heard of this algorithm. On Wikipedia's Fürer's algorithm page is a linked reference to a recent paper that might be of some interest to some of the smartest people here because one possible optimization depends on the distribution of Mersenne prime numbers: Even faster integer multiplication
Quote:
 Assuming standard conjectures about the distribution of Mersenne primes, we give yet another algorithm that achieves K = 4.

Last fiddled with by only_human on 2014-12-10 at 06:53

2014-12-10, 07:48   #20
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by only_human Just to show that reviewing what we think we know is nice, I was was unaware of this on that Wikipedia page linked to above: I'd never heard of this algorithm. On Wikipedia's Fürer's algorithm page is a linked reference to a recent paper that might be of some interest to some of the smartest people here because one possible optimization depends on the distribution of Mersenne prime numbers: Even faster integer multiplication
Yeah, I mentioned this on the other thread.

Fürer's algorithm is actually really nice because it takes an existing algorithm and improves it slightly, but also making it easier (IMO) to understand.

 2014-12-10, 09:31 #21 Mathsgirl     Dec 2014 22×5 Posts so my code to find mersenne primes (not this code I am showing you now!) finds the M_p and the corresponding p and returns a separate list of both. If I were to iterate through the list of p and use the LL test on them and instead make it return 2**p - 1. then it will work. and what's soo cool about it is that my code can only return 8 mersenne primes, where as this one can return moreee because it is only finding the correct p, which is a lot smaller than m so my computer can handle it.! if that is all correct! that is awesome
 2014-12-10, 14:06 #22 eumayer     Dec 2014 Sydney, Australia 2 Posts Code: and what's soo cool about it is that my code can only return 8 mersenne primes, where as this one can return moreee because it is only finding the correct p, which is a lot smaller than m so my computer can handle it.! if that is all correct! that is awesome Mathgirl makes me confused Which 8 Mersenne primes can your computer return only? The first 8 ones? 22-1, 23-1, 25-1, 27-1, 213-1, 217-1, 219-1, 231-1 ????? If you really find the code to calculate the correct p for new-record Mersenne primes, then you just made GIMPS redundant But I am pretty much sure u didn´t !

 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 01:03.

Tue Feb 7 01:03:43 UTC 2023 up 172 days, 22:32, 1 user, load averages: 0.80, 1.07, 1.08