Does anyone know "why" LL testing works?
 

If I understand correctly the theory behind the LL algorithm states:
The number 2^p -1 is a mersenne prime if and only if you put it through p-2 iterations of "s(n) = s(n-1)^2 -2",
and it modulo's out to exactly 0 (except for 2^2-1 which is 4 mod 3 = 1 not 0).

My question is why does this work?

What is significant about the number series s(n) = s(n-1)^2 -2?,
and why does s(n) modulo (2^(n+2)-1) = 0 if and only if 2^(n+2) -1 is a mersenne prime?

s(0) = 4 mod 3 = 1 (M2 is prime)
s(1) = 14 mod 7 = 0 (M3 is prime)
s(2) = 194 mod 15 = 14 (M4 is not prime)
s(3) = 37634 mod 31 = 0 (M5 is prime)
s(4) = 1416317954 mod 63 = 23 (M6 is not prime)
s(5) = 2005956546822746114 mod 127 = 0 (M7 is prime)
s(6) = 4023861667741036022825635656102100994 mod 255 = 149 (M8 is not prime)
s(7) = (1.619 E73) mod 511 = 205 (M9 is not prime)
s(8) = (2.621 E146) mod 1023 = 95 (M10 is not prime)
s(9) = (6.872 E292) mod 2047 = 1736 (M11 is not prime)
s(10) = (4.723 E585) mod 4095 = 779 (M12 is not prime)
s(11) = (2.231 E1171) mod 8191 = 0 (M13 is prime)
s(12) = (4.979 E2342) mod 16383 = 4193 (M14 is not prime)
etc., etc..

It is also convenient that instead of having to deal with a 2,343 digit number as in the case of s(12),
you can modulo the number by 2^p -1 each step of the way, keeping it smaller and more manageable.

[QUOTE=Moloch]If I understand correctly the theory behind the LL algorithm states:
The number 2^p -1 is a mersenne prime if and only if you put it through p-2 iterations of "s(n) = s(n-1)^2 -2",
and it modulo's out to exactly 0 (except for 2^2-1 which is 4 mod 3 = 1 not 0).

My question is why does this work?

What is significant about the number series s(n) = s(n-1)^2 -2?,
and why does s(n) modulo (2^(n+2)-1) = 0 if and only if 2^(n+2) -1 is a mersenne prime?

s(0) = 4 mod 3 = 1 (M2 is prime)
s(1) = 14 mod 7 = 0 (M3 is prime)
s(2) = 194 mod 15 = 14 (M4 is not prime)
s(3) = 37634 mod 31 = 0 (M5 is prime)
s(4) = 1416317954 mod 63 = 23 (M6 is not prime)
s(5) = 2005956546822746114 mod 127 = 0 (M7 is prime)
s(6) = 4023861667741036022825635656102100994 mod 255 = 149 (M8 is not prime)
s(7) = (1.619 E73) mod 511 = 205 (M9 is not prime)
s(8) = (2.621 E146) mod 1023 = 95 (M10 is not prime)
s(9) = (6.872 E292) mod 2047 = 1736 (M11 is not prime)
s(10) = (4.723 E585) mod 4095 = 779 (M12 is not prime)
s(11) = (2.231 E1171) mod 8191 = 0 (M13 is prime)
s(12) = (4.979 E2342) mod 16383 = 4193 (M14 is not prime)
etc., etc..

It is also convenient that instead of having to deal with a 2,343 digit number as in the case of s(12),
you can modulo the number by 2^p -1 each step of the way, keeping it smaller and more manageable.[/QUOTE]

The test works for the following reasons.

(1) We know all of the prime factors of p+1.

There is a very old and simple way to prove p a prime if we know all of the
factors of p-1: exhibit a primitive root. This works by via Lagrange's Thm.
The order of an element of Z/pZ* must divide p-1. Now exhibit an element
whose order is p-1 and we are done. To prove that an element has order
p-1 we must show that it does not have order (p-1)/q for all primes q
dividing p-1. Thus, if we know all the factors of p-1, we can prove p prime.

Now consider the finite field GF(p^2). It has p^2-1 elements and a
multiplicative sub-group of order p-1. It also has a sub-group (known as the
twisted group) whose order is p+1. The Lucas-Lehmer test does for p+1
what exhibiting a primitive root of p does in the p-1 case. It demonstrates
that there is an element of the twisted group having full (i.e. maximal possible)
order. Whereas for p-1, we do ordinary modular multiplication/exponentiation
to compute a^( (p-1)/q) mod p, in the twisted group the recursion
S_n = S_{n-1)^2 - 2 effects the multiplication and exponentiation. We know
p is prime when there is an element of full order.

Note that the Lucas-Lehmer test can also be applied (with modifications to
the recursion) to ANY suspected prime when all the prime factors of p+1
are known. When we test p = 2^q-1, the recursion is particularly simple
because all of the prime factors of p+1 are '2'.

I hope this helps. If you want MORE details, let me know.

[QUOTE=R.D. Silverman]The test works for the following reasons.

(1) We know all of the prime factors of p+1.

There is a very old and simple way to prove p a prime if we know all of the
factors of p-1: exhibit a primitive root. This works by via Lagrange's Thm.
The order of an element of Z/pZ* must divide p-1. Now exhibit an element
whose order is p-1 and we are done. To prove that an element has order
p-1 we must show that it does not have order (p-1)/q for all primes q
dividing p-1. Thus, if we know all the factors of p-1, we can prove p prime.

Now consider the finite field GF(p^2). It has p^2-1 elements and a
multiplicative sub-group of order p-1. It also has a sub-group (known as the
twisted group) whose order is p+1. The Lucas-Lehmer test does for p+1
what exhibiting a primitive root of p does in the p-1 case. It demonstrates
that there is an element of the twisted group having full (i.e. maximal possible)
order. Whereas for p-1, we do ordinary modular multiplication/exponentiation
to compute a^( (p-1)/q) mod p, in the twisted group the recursion
S_n = S_{n-1)^2 - 2 effects the multiplication and exponentiation. We know
p is prime when there is an element of full order.

Note that the Lucas-Lehmer test can also be applied (with modifications to
the recursion) to ANY suspected prime when all the prime factors of p+1
are known. When we test p = 2^q-1, the recursion is particularly simple
because all of the prime factors of p+1 are '2'.

I hope this helps. If you want MORE details, let me know.[/QUOTE]

What the hell does that have to do with my question?

What does knowing the prime factors of p+1 have to do with the lucas lehmer algorithm? I fail to see the correlation..

How does s(n) = s(n-1)^2 -2 have anything to do with p+1, lagrange's theorem, or finite/twisted groups/fields?!?

I understand that every mersenne prime is a power of 2 minus 1.. that is the f**king definition of a mersenne prime!!!


Now, can someone with a little more expertise please answer my question?

[QUOTE]Now, can someone with a little more expertise please answer my question?[/QUOTE]

::Snort::

[QUOTE=Moloch]What the hell does that have to do with my question?

What does knowing the prime factors of p+1 have to do with the lucas lehmer algorithm? I fail to see the correlation..

How does s(n) = s(n-1)^2 -2 have anything to do with p+1, lagrange's theorem, or finite/twisted groups/fields?!?

I understand that every mersenne prime is a power of 2 minus 1.. that is the ------- definition of a mersenne prime!!!


Now, can someone with a little more expertise please answer my question?[/QUOTE]

:surprised [Hides behind a corner] :surprised

If I understand correctly, R.D. Silverman specializes in the study of factoring, and his knowledge about primes is certainly much more than mine.

I just interpret his post as saying that the proof of the LL test is well beyond anything I learned in high school, and leave it at that (until I either take some university courses on this or get a large chunk of free time to learn this all).

Please don't start any flaming. These types of flame wars are known to be very unpleasant. I'm not trying to offend anyone; I'm just trying to defuse any tension.

[QUOTE=jinydu]:surprised [Hides behind a corner] :surprised

If I understand correctly, R.D. Silverman specializes in the study of factoring, and his knowledge about primes is certainly much more than mine.

I just interpret his post as saying that the proof of the LL test is well beyond anything I learned in high school, and leave it at that (until I either take some university courses on this or get a large chunk of free time to learn this all).

Please don't start any flaming. These types of flame wars are known to be very unpleasant. I'm not trying to offend anyone; I'm just trying to defuse any tension.[/QUOTE]

I dont mean to start a flame war or anything, I was just hoping for a better explaination of what I was asking.

If I were to ask you what color is the grass that grows on the ground, would you say,

A) Most of the color reflected from grass would fall somewhere along the visible spectrum of light.
B) It depends on the species of grass, the latitude and altitude of the location, and the season of year.
C) Everyone knows that grass is green.
D) Since the process of photosynthesis absorbs most of the excess energy of a photon, moving it towards a state of equilibrium, and the state of equilibrium of a photon lies between the green and yellow range of the visible spectrum of light, your answer is a green-yellow color.


While all of these answers are theoretically correct with the exception of C (since it is highly improbable that "everyone" knows grass is green), answer A is a bit too general, answer B doesnt even answer the question, and answer D is purely theoretical.


I dont claim that I'm a master of number theory. If I was I wouldnt be on here asking questions. I really didnt expect my first reply to be from someone who only made an account on here 3 days ago. I'm not saying that account length = credability, but I assumed someone who specializes in factoring and primes might have been a member of the forum for a bit longer. Not to mention how am I supposed to know he actually is R. D. Silverman? After all, my real name isnt Moloch, and I doubt ColdFury's real name is ColdFury, nor jinydu's jinydu.


After reading Silverman's reply I can see that it makes sense in a way, but doesnt appear to answer my question(s).

In his first paragraph, how does knowing the prime roots of p-1 help us if we dont know what they are? Or is there some easy way to find the prime roots of 2^p -2? If not I dont see how this can be applied in the case of mersenne primes.

The second paragraph although informative appears to be too general of an answer. I dont know a lot about number theory but after reading it a few times I understand what he means. If I understand correctly, he is saying that sometimes there will be an element of the twisted group "S_n = S_{n-1)^2 - 2" which will divide evenly by the subgroup "2^p -1". I understand that this is the theory behind the Lucas-Lehmer algorithm. But that doesnt have anything to do with "why it works," "what is significant about the twisted group," or "why does the twisted group divide evenly by 2^p -1 if and only if 2^p -1 is prime."


[QUOTE=R. D. Silverman]I hope this helps. If you want MORE details, let me know.[/QUOTE]

This makes me feel like I'm wasting his time asking such trivial questions, and also puts an end to the possibility of anyone else posting a more elaborate reply unless I first post one stating that my question was not answered. (hence the reply).

[QUOTE]I dont mean to start a flame war or anything, I was just hoping for a better explaination of what I was asking.[/QUOTE]

Than next time mind your language.

[QUOTE]This makes me feel like I'm wasting his time asking such trivial questions[/QUOTE]

Actually, he put a thumbs up on your question.

[QUOTE=Moloch]I dont mean to start a flame war or anything, I was just hoping for a better explaination of what I was asking.[/quote]Silverman gave a great explanation, if you know some group theory.

Unfortunately, it requires a knowledge of group theory to understand why Lucas-Lehmer works. [i]There is no simpler answer, really![/i] Any attempt to answer on a more elementary level would have to include an introductory course on group theory. Sorry, but that's the way it is.

[quote]If I were to ask you what color is the grass that grows on the ground, would you say,[/quote]But for a fair comparison, the analogous question would have to be: Why is grass green? (After all, you asked [b]why[/b] L-L works!) Then the answer would eventually have to explain the physics of light, the physiology of color perception, and the nature of chlorophyll. Unless you're willing to accept just, "Grass is green because it's green."

[quote]While all of these answers are theoretically correct with the exception of C (since it is highly improbable that "everyone" knows grass is green), answer A is a bit too general, answer B doesnt even answer the question, and answer D is purely theoretical.[/quote]It's just too bad that there isn't a simple answer like C to your question.

[quote]I really didnt expect my first reply to be from someone who only made an account on here 3 days ago.[/quote]Mr. Silverman [u]has[/u] been a long-time contributor. Do a search on "Silverman". I don't know why he chose to, or had to, establish a new account -- maybe some technical screwup somewhere.

[quote]Not to mention how am I supposed to know he actually is R. D. Silverman?[/quote]Do a Google search on R. D. Silverman. (not that this answers your question about confirming ID ...)

[quote]In his first paragraph, how does knowing the prime roots of p-1 help us if we dont know what they are? Or is there some easy way to find the prime roots of 2^p -2? If not I dont see how this can be applied in the case of mersenne primes.[/quote]... but if you knew group theory, it would make sense.

[quote]This makes me feel like I'm wasting his time asking such trivial questions,[/quote]No, you're not wasting his time. It's just that you didn't realize that your question had no simpler answer. No one knows that until they ask, so your question is okay.

[quote]and also puts an end to the possibility of anyone else posting a more elaborate reply unless I first post one stating that my question was not answered. (hence the reply).[/QUOTE]Okay, so now someone can direct you to where you can learn a bit of group theory.

Moloch,

Here is a website going into more depth (but basically repeating what Dr. Silverman wrote): [url]http://www.utm.edu/research/primes/notes/proofs/LucasLehmer.html[/url]

There seems to be a small error in his explanation. The finite field, F(p^2), has p^2 elements, and it's unit *group*, GF(p^2), has p^2-1 elements.

Cheers,
Zeta-Flux

I found an "elementary" proof of Lucas' test for primality of Mersenne numbers in the classic book "An Introduction to the Theory of Numbers" by Hardy and Wright. I only have access to the 4th edition, but in section 15.5 it is proven that the test works if you start with S(0)=3 (instead of S(0)=4) for those exponents which leave a remainder of 3 upon division by 4. The proof uses properties of the field obtained from the rational numbers by throwing in the squareroot of 5, and takes about a page and a half. Then the authors say that by using the squareroot of 3 instead of 5, it can be proven that the test works with S(0)=4 for all exponents, but the proof is longer. Unfortunately, although the proof is "elementary", it doesn't seem to give one much insight into why it works, and I think that if you are really interested in that question, a study of Lucas sequences and group theory would be the place to start.

[QUOTE=philmoore]The proof uses properties of the field obtained from the rational numbers by throwing in the squareroot of 5,[/quote]So, since the properties of a (mathematical) field are part of group theory, once again we see that the proof requires some knowledge of group theory.

[quote] the squareroot of 3 instead of 5, it can be proven that the test works with S(0)=4 for all exponents, but the proof is longer. Unfortunately, although the proof is "elementary",[/quote]That depends on whether one considers group theory to be "elementary". Most professional mathematicians would, because group theory is so fundamental to so much of mathematics that any math major is taught group theory fairly early in college.

But to someone who is ignorant of group theory, a proof that assumes one knows the properties of a field probably does not appear "elementary".