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

Hi,
This thread of discussion is very interesting, and I'm sorry to have been so busy re-installing my PC at that time.

Moloch, I've been at your place some years ago: I was not able to understand why LLT works so well, though I received a good education in Maths before I got my Engineer diploma. But I learnt nothing about Number Theory at that time (26 years ago).
The answers you got in this thread talk about "group theory", "finite fields", and many other stuff. This stuff is not useful.
I spent several years trying to understand why LLT works. It's clear now.

First, many mathematicians now have forgotten the early period when Edouard Lucas (end of XIX) discovered that one can prove a number is prime or not without searching his divisors.
At that time, there were no "group theory" and other modern Maths stuff.

Edouard Lucas, in fact, was not a "true" Mathematician: He did not provide all the proofs that were needed. If he thought that something was clear/evident, he gave some sort of proof for A ==> B but not for B ==> A, and then he said it's a theorem (A <==> B). Derrick Lehmer then gave complete proofs plus new stuff.

If you want to learn how it can be proven, read the chapter 2 of the "Little Book for Greater Primes" of Paulo Ribenboim. You can get it for free at:[URL=http://www.springeronline.com/sgw/cda/pageitems/document/cda_downloaddocument/0,11996,0-0-45-110375-0,00.pdf]Springer[/URL].
But don't believe him totally. He's wrong about the limits of several theorems he gives. They also can be used for numbers like Fermat numbers, not only for Mersenne numbers.
If you have a good library near your home, read also the book of Williams: "Edouard Lucas and Primality proving". It's a Great book, but difficult (I understand a very small part of it).
But don't read the "Hardy and Wright". It really does not help.
According to your math level, understanding the method underneaf the LLT could take months or years ... but it's worth to do it.

Reading these books, you can easily see that no "group theory" is needed.
The Mathematicians now using "group theory" for proving LLT do not know that they loose a big part of the power of Lucas/Lehmer method. On the web, many of the proofs given for the LLT are so specialized that they can ONLY be used for LLT. So they are of very little use for understanding the nice method discovered by Lucas and improved by Lehmer.

Then you could have a look at 2 tries I did for re-inventing the wheel about Fermat numbers:
[URL=http://tony.reix.free.fr/Mersenne/PrimalityTest1FermatNumbers.pdf]First Wheel[/URL]
[URL=http://tony.reix.free.fr/Mersenne/PrimalityTest2FermatNumbers.pdf]Second wheel[/URL]
So you can see that LLT method can be used for Fermat numbers. A fact that is not known by many Number Theory experts.

Though this looks very difficult, it is very simple for many people.

Many people that are giving you explanations in this thread like to talk about things they perfectly know. But they don't like exploring unclear or unproven fields, like the one I proposed in the paper:[URL=http://tony.reix.free.fr/Mersenne/PrimalityTest4FermatNumbers.pdf]A primality test for Fermat numbers[/URL]. Nobody seems to have studied my paper, though Edouard Lucas found quite the same theorem. Or maybe the paper is wrong or very bad. Is it wrong, Mister Silverman ?

Though I now understand quite well the theory underneaf the LLT, I still don't understand how it can be computed so quickly, by means of specialized FFT (Fast Fourier Transform). It's too complex for me and I never found a book (several books in fact) explaining all the steps required for understanding the technic used. Some day maybe. People in this forum provided very good explanations of general theory under FFT, but much more is needed. A book would be very useful !

I think some day I'll put on my web site all the documents I've found about Lucas work. But they are all in French, except one.
Who is interested ?

Have a good day.

Tony
Carpe Diem

[QUOTE=T.Rex]The answers you got in this thread talk about "group theory", "finite fields", and many other stuff. This stuff is not useful.[/quote]Maybe you don't have uses for them, but others do.

[quote]First, many mathematicians now have forgotten the early period when Edouard Lucas (end of XIX) discovered that one can prove a number is prime or not without searching his divisors.
At that time, there were no "group theory" and other modern Maths stuff.[/quote]Group theory was still in its early development during Lucas's lifetime. Now that there exists a more complete and systematic understanding of the properties of groups, plus many powerful theorems, than was available to Lucas, why not take advantage of that?

[quote]According to your math level, understanding the method underneaf the LLT could take months or years ... but it's worth to do it.[/quote]A couple of weeks may be all that's needed to learn enough group theory to understand Silverman's explanation. Why go the long way?

[quote]Reading these books, you can easily see that no "group theory" is needed.[/quote]Before automobiles were invented, one could easily travel 10 miles on foot or horse. Autos aren't needed for such a distance. But use of the auto may be faster and more convenient than traveling by foot or horse. :smile:

[quote]The Mathematicians now using "group theory" for proving LLT do not know that they loose a big part of the power of Lucas/Lehmer method.[/quote]Maybe what they do know is that group theory (why put it in quotes?) is a powerful mathematical tool applicable to a wide variety of mathematical problems, not just the Lucas-Lehmer test.

One might find that the proof of part of Lucas's method (by Lehmer's time, more group theory was available) actually corresponds to certain theorems of group theory, except that it's not as general.

[quote]I think some day I'll put on my web site all the documents I've found about Lucas work. But they are all in French, except one.
Who is interested ?[/QUOTE]I am. But my high-school French is so rusty I'll probably use one of those Web translators.

[QUOTE=cheesehead]Maybe you don't have uses for them, but others do.

Group theory was still in its early development during Lucas's lifetime. Now that there exists a more complete and systematic understanding of the properties of groups, plus many powerful theorems, than was available to Lucas, why not take advantage of that ?[/QUOTE] I'm not an expert. Nevertheless, I've found several recent papers on the web that are still using the theory elaborated by Lucas and Lehmer. So it seems still useful.

By the way, the Book of HC Williams about E. Lucas has only 4 or 5 pages about the thesis of D. Lehmer. I would be very pleased to be able to read it.
Does someone knows where it can be found (on the web) ?

[QUOTE]A couple of weeks may be all that's needed to learn enough group theory to understand Silverman's explanation. Why go the long way ? [/QUOTE] Because I think there are other interesting things to find with these tools. Most of people are using the new tools, so they are not aware that LLT may be used for other numbers than Mersenne numbers or N-1 numbers.

[QUOTE]Before automobiles were invented, one could easily travel 10 miles on foot or horse. Autos aren't needed for such a distance. But use of the auto may be faster and more convenient than traveling by foot or horse. :smile:
[/QUOTE]Using automobiles does not enable you to discover the wonderful world leaving in the grass. Walking does. :smile: Using different tools enables to see differents things or same things but differently.

[QUOTE]Maybe what they do know is that group theory (why put it in quotes?) is a powerful mathematical tool applicable to a wide variety of mathematical problems, not just the Lucas-Lehmer test.[/QUOTE] You're right. But, the first time I tried to understand the LLT, I read a proof provided by [url]http://www.utm.edu/research/primes[/url] , I think. It was really badly explained. Very short. Boring. But it is a general complain I have against Maths: most of the books provide the shortest possible proof, rather than explaining the long and difficult way used by the first discoverers. (I put group theory inside quotes in order to "group" the 2 words, so that it is more readable.)

[QUOTE]One might find that the proof of part of Lucas's method (by Lehmer's time, more group theory was available) actually corresponds to certain theorems of group theory, except that it's not as general.[/QUOTE] It is a question: does group theory enables to provide all the primality theorems appearing in Ribenboim's book ?

I learnt group theory at school, long time ago. And I forgot many things. I think I prefer the maths used by Lehmer and Lucas because they enable "amateurs" like me to play with.

[QUOTE]I am. But my high-school French is so rusty I'll probably use one of those Web translators.[/QUOTE]I've collected all papers I've found about Lucas' work on my WebSite: [URL=http://tony.reix.free.fr/EdouardLucas/]Edouard Lucas[/URL] . All of them were taken on official web-sites. It also contains a thesis devoted to E. Lucas work. It is all in French, and I think you cannot translate them since they are scanned images.

By the way, I've found the official web-site of Edouard Lucas: [URL=http://edouardlucas.free.fr/]Edouard Lucas Site[/URL] . It contains valuable information about Lucas. And there are a French and an English version !

Regards,
Tony

T.Rex,

I was responding to your disparagement of group theory and its use to explain L-L. I was defending group theory and its use to explain why L-L works. I was discussing why group theory was better than Lucas's work for the purpose of understanding the L-L method, not tearing down Lucas's work itself as it seemed you were treating group theory.

[QUOTE=T.Rex]Nevertheless, I've found several recent papers on the web that are still using the theory elaborated by Lucas and Lehmer. So it seems still useful.[/quote]Fine. I never said Lucas's work wasn't useful in other contexts.

[quote=cheesehead]Why go the long way ?[/quote][quote=T.Rex]Because I think there are other interesting things to find with these tools.[/quote]But I was asking about your advocating avoidance of group theory in understanding L-L, not about other contexts. So, again, why should someone go the long way [i]while learning why the L-L method works[/i]?

[quote=T.Rex]Using automobiles does not enable you to discover the wonderful world leaving in the grass. Walking does. :smile: Using different tools enables to see differents things or same things but differently.[/quote]Again, you're changing the subject, from study of the L-L method to mathematics in general. Do you question that my analogy about automobiles is valid in the context in which I intended it?

[quote=T.Rex]But it is a general complain I have against Maths: most of the books provide the shortest possible proof, rather than explaining the long and difficult way used by the first discoverers.[/quote]So, what you want is an exposition on the history of the quest for the results to be included in every math book, not just the results? Come on, be reasonable. Some books are not intended to cover math history; don't criticize them for not being in your preferred catagory. Instead, stick to the books that include math history and leave the others alone to fulfill [i]their[/i] authors' and readers' goals.