mersenneforum.org  

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

Reply
 
Thread Tools
Old 2014-12-09, 23:49   #12
Mathsgirl
 
Mathsgirl's Avatar
 
Dec 2014

22·5 Posts
Angry

but it also said 11 wasn't prime, so just forget about all these posts... just ignore me
Mathsgirl is offline   Reply With Quote
Old 2014-12-09, 23:52   #13
Mathsgirl
 
Mathsgirl's Avatar
 
Dec 2014

22·5 Posts
Default

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

2·3·23·61 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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) ?
science_man_88 is offline   Reply With Quote
Old 2014-12-10, 00:02   #15
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2·1,877 Posts
Default

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
only_human is offline   Reply With Quote
Old 2014-12-10, 00:50   #16
Mathsgirl
 
Mathsgirl's Avatar
 
Dec 2014

22×5 Posts
Default

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!)
Mathsgirl is offline   Reply With Quote
Old 2014-12-10, 00:51   #17
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2·1,877 Posts
Default

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
only_human is offline   Reply With Quote
Old 2014-12-10, 03:28   #18
TheMawn
 
TheMawn's Avatar
 
May 2013
East. Always East.

11×157 Posts
Default

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 View Post
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.
TheMawn is offline   Reply With Quote
Old 2014-12-10, 06:50   #19
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2·1,877 Posts
Default

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
only_human is offline   Reply With Quote
Old 2014-12-10, 07:48   #20
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

Quote:
Originally Posted by only_human View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2014-12-10, 09:31   #21
Mathsgirl
 
Mathsgirl's Avatar
 
Dec 2014

22×5 Posts
Talking

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
Mathsgirl is offline   Reply With Quote
Old 2014-12-10, 14:06   #22
eumayer
 
eumayer's Avatar
 
Dec 2014
Sydney, Australia

2 Posts
Default

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 !
eumayer 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 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔