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

 2009-09-17, 19:19 #1 storm5510 Random Account     Aug 2009 3×661 Posts Lucas-Lehmer Test On the GIMPS site, there is an example of the LL test. The value tested is 27 - 1. 127. Why does this example only work with 127?
2009-09-17, 19:45   #2
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

3×1,423 Posts

How exactly are you modifying it that the example fails to work for other numbers?

http://www.mersenne.org/various/math.php
Quote:
 The Lucas-Lehmer primality test is remarkably simple. It states that for P > 2, 2P-1 is prime if and only if Sp-2 is zero in this sequence: S0 = 4, SN = (SN-12 - 2) mod (2P-1). For example, to prove 27 - 1 is prime: Code:  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
Here's a modification of it for p=5 (2p-1=31):
Code:
        S0 = 4
S1 = (4 * 4 - 2) mod 31 = 14
S2 = (14 * 14 - 2) mod 31 = 8
S3 = (8 * 8 - 2) mod 31 = 0
Sp-2=S3=0, hence 2p-1=31 is prime.

Or have I got your confusion all wrong?

2009-09-17, 23:00   #3
storm5510
Random Account

Aug 2009

111101111112 Posts

What I experimented with is below:

Code:
S = 4
N = 257

Do
S = ((S * S) - 2) Mod N
Loop While S <> 0
This seems to work for only certain powers of 2. Perhaps that is the point. The value "N" above is not.

Quote:
 (It is also possible to start with S(1)=10 and certain other values depending on p.)
This could have been explained a bit more?

 2009-09-17, 23:17 #4 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 3·19·113 Posts 257 is not a number of the form 2^p-1, and the Lucas-Lehmer test is only defined for numbers of that form. N=2^257-1 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 2009-09-17 at 23:21
2009-09-17, 23:17   #5
R.D. Silverman

Nov 2003

746010 Posts

Quote:
 Originally Posted by storm5510 What I experimented with is below: Code: S = 4 N = 257 Do S = ((S * S) - 2) Mod N Loop While S <> 0 This seems to work for only certain powers of 2. Perhaps that is the point. The value "N" above is not. This could have been explained a bit more?
Huh? 257 is not a Mersenne number. It is 2^8 + 1!!!!! Duh!!!!
Mersenne numbers are 2^p-1 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?)

 2009-09-17, 23:54 #6 storm5510 Random Account     Aug 2009 3·661 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...
2009-09-18, 00:18   #7
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 Originally Posted by storm5510 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...
When one asks about a primality test for Mersenne primes, it should
be assumed that the person asking the question knows WHAT
a Mersenne prime is.

 2009-09-18, 02:20 #8 Mini-Geek Account Deleted     "Tim Sorbera" Aug 2006 San Antonio, TX USA 10AD16 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^p-1. It is prime and could be used for p, but not for 2^p-1. (e.g. you could use P=257 and N=2^P-1, then run the loop 257-2 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 Sp-2 and inaccurately report the number as prime. If the number is prime, it works just fine. Last fiddled with by Mini-Geek on 2009-09-18 at 02:24
2009-09-18, 03:24   #9
storm5510
Random Account

Aug 2009

3×661 Posts

Quote:
 Originally Posted by R.D. Silverman When one asks about a primality test for Mersenne primes, it should be assumed that the person asking the question knows WHAT a Mersenne prime is.
2P - 1, where P is any even number. Subtract 1 and it becomes odd, then an exponent of 2.

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 re-invent 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 2009-09-18 at 03:58

2009-09-18, 04:11   #10
flouran

Dec 2008

72×17 Posts

Quote:
 Originally Posted by R.D. Silverman 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?)
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.

 2009-09-18, 06:49 #11 storm5510 Random Account     Aug 2009 3×661 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 time-efficient method?

 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 Mathsgirl Information & Answers 23 2014-12-10 16:25 BMgf Programming 23 2003-12-09 08:52 Annunaki Math 22 2003-08-05 21:52

All times are UTC. The time now is 04:36.

Thu Oct 28 04:36:58 UTC 2021 up 96 days, 23:05, 0 users, load averages: 1.64, 1.84, 2.09