Lucas-Lehmer Test

storm5510 · 2009-09-17, 19:19

On the GIMPS site, there is an example of the LL test. The value tested is 2⁷ - 1. 127.

Why does this example only work with 127?

TimSorbet · 2009-09-17, 19:45

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, 2^P-1 is prime if and only if S_p-2 is zero in this sequence: S₀ = 4, S_N = (S_N-1² - 2) mod (2^P-1). For example, to prove 2⁷ - 1 is prime:

Code:

        S₀ = 4
        S₁ = (4 * 4 - 2) mod 127 = 14
        S₂ = (14 * 14 - 2) mod 127 = 67
        S₃ = (67 * 67 - 2) mod 127 = 42
        S₄ = (42 * 42 - 2) mod 127 = 111
        S₅ = (111 * 111 - 2) mod 127 = 0

Here's a modification of it for p=5 (2^p-1=31):

Code:

        S₀ = 4
        S₁ = (4 * 4 - 2) mod 31 = 14
        S₂ = (14 * 14 - 2) mod 31 = 8
        S₃ = (8 * 8 - 2) mod 31 = 0

S_p-2=S₃=0, hence 2^p-1=31 is prime.

Or have I got your confusion all wrong?

storm5510 · 2009-09-17, 23:00

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?

fivemack · 2009-09-17, 23:17

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.

R.D. Silverman · 2009-09-17, 23:17

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?)

storm5510 · 2009-09-17, 23:54

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...

R.D. Silverman · 2009-09-18, 00:18

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.

TimSorbet · 2009-09-18, 02:20

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 S_p-2 and inaccurately report the number as prime. If the number is prime, it works just fine.

storm5510 · 2009-09-18, 03:24

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.

2^P - 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:

Ignore Silverman, please.

Gladly...

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...

flouran · 2009-09-18, 04:11

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.

storm5510 · 2009-09-18, 06:49

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?

2009-09-17, 19:19	#1
storm5510 Random Account Aug 2009 Not U. + S.A. 2·5·277 Posts	Lucas-Lehmer Test On the GIMPS site, there is an example of the LL test. The value tested is 2⁷ - 1. 127. Why does this example only work with 127?

2009-09-17, 23:17	#4
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2×7×461 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 65536655366553665536 is not equal to zero. Last fiddled with by fivemack on 2009-09-17 at 23:21*

2009-09-18, 02:20	#8
TimSorbet Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 11×389 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 S_p-2 and inaccurately report the number as prime. If the number is prime, it works just fine. Last fiddled with by TimSorbet on 2009-09-18 at 02:24

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	Mathsgirl	Information & Answers	23	2014-12-10 16:25
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

2009-09-17, 23:54	#6
storm5510 Random Account Aug 2009 Not U. + S.A. 2·5·277 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, 06:49	#11
storm5510 Random Account Aug 2009 Not U. + S.A. 2×5×277 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?