20090917, 19:19  #1 
Random Account
Aug 2009
Not U. + S.A.
2326_{10} Posts 
LucasLehmer Test
On the GIMPS site, there is an example of the LL test. The value tested is 2^{7}  1. 127.
Why does this example only work with 127? 
20090917, 19:45  #2  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
2·3·23·31 Posts 
How exactly are you modifying it that the example fails to work for other numbers?
http://www.mersenne.org/various/math.php Quote:
Code:
S_{0} = 4 S_{1} = (4 * 4  2) mod 31 = 14 S_{2} = (14 * 14  2) mod 31 = 8 S_{3} = (8 * 8  2) mod 31 = 0 Or have I got your confusion all wrong? 

20090917, 23:00  #3  
Random Account
Aug 2009
Not U. + S.A.
2×1,163 Posts 
What I experimented with is below:
Code:
S = 4 N = 257 Do S = ((S * S)  2) Mod N Loop While S <> 0 Quote:


20090917, 23:17  #4 
(loop (#_fork))
Feb 2006
Cambridge, England
2·7·461 Posts 
257 is not a number of the form 2^p1, and the LucasLehmer test is only defined for numbers of that form. N=2^2571 would work, though be sure that you're using a language (eg Python) where arithmetic on large numbers is defined correctly  check that 65536*65536*65536*65536 is not equal to zero.
Last fiddled with by fivemack on 20090917 at 23:21 
20090917, 23:17  #5  
"Bob Silverman"
Nov 2003
North of Boston
5^{2}×13×23 Posts 
Quote:
Mersenne numbers are 2^p1 for p prime. As for explaining why S=10 works as the starting value in addition to S=4, I can only say that you lack the math to understand an explanation. (Do you know what the twisted group of GF(p^2) is? Do you even know what a group or finite field is?) 

20090917, 23:54  #6 
Random Account
Aug 2009
Not U. + S.A.
916_{16} Posts 
I ask a question and this is the kind of reply I get! I should have known better. I'll never ask anything here again...

20090918, 00:18  #7  
"Bob Silverman"
Nov 2003
North of Boston
7475_{10} Posts 
Quote:
be assumed that the person asking the question knows WHAT a Mersenne prime is. 

20090918, 02:20  #8 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
1000010110110_{2} Posts 
Ignore Silverman, please. I don't understand why 10 works as a starting number as well as 4, but it really doesn't matter here. And yes, you should have noticed that N=257 is invalid for the LL test, but it's a simple mistake. Silverman overreacted, and if you stop asking questions, you'll be overreacting too.
There are two major problems with your code: 1. N is 257, which is not of the form 2^p1. It is prime and could be used for p, but not for 2^p1. (e.g. you could use P=257 and N=2^P1, then run the loop 2572 times, with each step being mod N) 2. You're not stopping at the right spot. If the number is composite, you'll eventually either enter into an endless loop and run the number forever, or reach 0 at an index besides S_{p2} and inaccurately report the number as prime. If the number is prime, it works just fine. Last fiddled with by MiniGeek on 20090918 at 02:24 
20090918, 03:24  #9  
Random Account
Aug 2009
Not U. + S.A.
2×1,163 Posts 
Quote:
3, 7, 15, 31, 63, 127, 255 .... 2097151, 4194303, so forth, and so on, what not, and what have you. Quote:
My mistake was forgetting to remove 257. I was experimenting to see what happened by stepping through the code with "strange" numbers. I watched it repeat with the same values several times and realized it had to stop sometime. I am not trying to reinvent the wheel, just learn a thing, or two. When the day comes that this is not possible, then it will be the day I get a rope... Last fiddled with by storm5510 on 20090918 at 03:58 

20090918, 04:11  #10 
Dec 2008
1101000001_{2} Posts 
Silverman, you are a nitwit. When someone asks for help and IF YOU CAN HELP THEM, then offer suggestions. If you cannot help them (be it due to yours or their mathematical inability), then just do not respond. Simple as that.

20090918, 06:49  #11 
Random Account
Aug 2009
Not U. + S.A.
4426_{8} Posts 
Be it stupid, or not, here's what I am looking for:
I have an application which I can punch a number into. The purpose is to see if it is a prime number. It doesn't matter what type. The conventional way is to iterate all the way up to the square root of said number in steps of two, starting at three, while skipping multiples of five. This can be time consuming if a very large number is entered. Is there a more timeefficient method? 
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  20180311 23:20 
A second proof for the LucasLehmer Test  carpetpool  Miscellaneous Math  2  20170730 09:21 
LucasLehmer test  Mathsgirl  Information & Answers  23  20141210 16:25 
Lucas Lehmer test question?  BMgf  Programming  23  20031209 08:52 
about LucasLehmer test and Prime 95  Annunaki  Math  22  20030805 21:52 