20041127, 01:44  #1 
Mar 2004
2^{3}×3 Posts 
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 p2 iterations of "s(n) = s(n1)^2 2", and it modulo's out to exactly 0 (except for 2^21 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(n1)^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. Last fiddled with by Moloch on 20041127 at 01:56 
20041127, 02:21  #2  
"Bob Silverman"
Nov 2003
North of Boston
5^{2}·13·23 Posts 
Quote:
(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 p1: exhibit a primitive root. This works by via Lagrange's Thm. The order of an element of Z/pZ* must divide p1. Now exhibit an element whose order is p1 and we are done. To prove that an element has order p1 we must show that it does not have order (p1)/q for all primes q dividing p1. Thus, if we know all the factors of p1, we can prove p prime. Now consider the finite field GF(p^2). It has p^21 elements and a multiplicative subgroup of order p1. It also has a subgroup (known as the twisted group) whose order is p+1. The LucasLehmer test does for p+1 what exhibiting a primitive root of p does in the p1 case. It demonstrates that there is an element of the twisted group having full (i.e. maximal possible) order. Whereas for p1, we do ordinary modular multiplication/exponentiation to compute a^( (p1)/q) mod p, in the twisted group the recursion S_n = S_{n1)^2  2 effects the multiplication and exponentiation. We know p is prime when there is an element of full order. Note that the LucasLehmer 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^q1, 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. 

20041127, 03:11  #3  
Mar 2004
30_{8} Posts 
Quote:
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(n1)^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? 

20041127, 03:37  #4  
Aug 2002
140_{16} Posts 
Quote:


20041127, 06:29  #5  
Dec 2003
Hopefully Near M48
2×3×293 Posts 
Quote:
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. 

20041127, 22:10  #6  
Mar 2004
2^{3}×3 Posts 
Quote:
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 greenyellow 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 p1 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_{n1)^2  2" which will divide evenly by the subgroup "2^p 1". I understand that this is the theory behind the LucasLehmer 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:


20041127, 22:27  #7  
"Sander"
Oct 2002
52.345322,5.52471
29·41 Posts 
Quote:
Quote:


20041128, 08:52  #8  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Quote:
Unfortunately, it requires a knowledge of group theory to understand why LucasLehmer works. There is no simpler answer, really! 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:
Quote:
Quote:
Quote:
Quote:
Quote:
Quote:


20041129, 04:50  #9 
May 2003
7·13·17 Posts 
Moloch,
Here is a website going into more depth (but basically repeating what Dr. Silverman wrote): http://www.utm.edu/research/primes/n...casLehmer.html 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^21 elements. Cheers, ZetaFlux 
20041201, 21:42  #10 
"Phil"
Sep 2002
Tracktown, U.S.A.
3·373 Posts 
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.

20041202, 19:01  #11  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
Quote:
Quote:
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". 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
gpuOwL: an OpenCL program for Mersenne primality testing  preda  GpuOwl  2784  20220924 14:38 
Antipoverty drug testing vs "high" tax deduction testing  kladner  Soap Box  3  20161014 18:43 
AouessareEl HaddouchiEssaaidi "test": "if Mp has no factor, it is prime!"  wildrabbitt  Miscellaneous Math  11  20150306 08:17 
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?  nitai1999  Software  7  20040826 18:12 
Exponents to rerelease for firsttime testing: "harmful" errorcodes  GP2  Data  4  20031018 22:08 