20070510, 21:05  #1 
May 2007
denmark
13 Posts 
LL Test: Understanding the math
For some time, years actually, i have been trying to understand the math behind the prime95 software. Now, i am a Reasonable intelligent fellow with a great interest in math, allthough my (knowledge in that area is somewhat limited), and my english is not that bad, but no matter how many times i read the math section on the mersenne.org homepage, it just doesnt make sence to me, well some of it does, but not the important stuff.
I have tryed finding other sources with explanations to the math, but i havent succeded. So here i go: Does anyone know about sources which is understandable by people like me, or whould anyone care to take the time to explain? Regards 
20070510, 21:56  #2 
Sep 2002
Database er0rr
F15_{16} Posts 
I recently came across
http://www.math.umn.edu/~garrett/m/n...cas_lehmer.pdf on the first pages of web search for "lucas Lehmer". It seemed quite good. Last fiddled with by paulunderwood on 20070510 at 21:56 
20070510, 23:14  #3 
Einyen
Dec 2003
Denmark
5^{2}·127 Posts 
Try:
The Little Book of Bigger Primes.pdf "Section 2 IV: Lucas Sequences" page 4462 and "Section 2 VII Mersenne Numbers" page 7587. 
20070510, 23:48  #4 
Feb 2006
Denmark
230_{10} Posts 

20070511, 01:26  #5 
Sep 2002
296_{16} Posts 
What part of the math in particular ?
The Lucas Lehmer algorithm or the trial factoring algorithm ? The specific math optimization used by Prime95 to do the LL (Irrational Base Discrete Weighted Transform (a type of FFT)) or just the math to do it using an unoptimized algorithm. From the Prime95 help file, the unoptimized algorithm. LUCASLEHMER DETAILS This program uses the LucasLehmer primality test to see if 2^P  1 is prime. The Lucas sequence is defined as: S (1) = 4 S (n+1) = (S (n)^2  2) mod (2^P  1) 2^P  1 is prime if and only if S (p1) = 0. This program uses a discrete weighted transform (see Mathematics of Computation, January 1994) to square numbers in the LucasLehmer sequence. The LucasLehmer primality test is remarkably simple. For example, to prove 2^7  1 is prime: S (1) = 4 S (2) = (4 * 4 – 2) mod 127 = 14 S (3) = (14 * 14 – 2) mod 127 = 67 S (4) = (67 * 67 – 2) mod 127 = 42 S (5) = (42 * 42 – 2) mod 127 = 111 S (6) = (111 * 111 – 2) mod 127 = 0  2^P means 2 to the Pth power. 2^7  1 = 128  1 = 127 Each step except for the initialization step S(1) = 4 takes the value of the previous step, squares it, subtracts 2, then mods it by the mersenne number. Mod means get the remainder after dividing by the (mersenne) number. Example: On step S(4) , 67*67  2 = 4489  2 = 4487 4487 / 127 = 35 remainder 42, so 42 is used for the next step. Using the mersenne example 2^7  1, 127, it requires 7  1 = 6 steps, including the first step S(1) = 4. Last fiddled with by dsouza123 on 20070511 at 01:39 Reason: Small addition. 
20070511, 03:02  #6  
May 2007
denmark
13 Posts 
Quote:
Well, the i actually intend to use it in some programing, however will ofcourse have to understand the math before starting to optimize. An now i atleast know how to use the lucas lehmer test, thanks to you, really helpfull. A question or two: 1. i have writen a little program just to do some testing, and i have run some different exponent, but two of the exponents 17 and 19 gives me trouble, and if i am not mistaken, they are primes and result in primes, or maybe im wrong? the same goes for 2, but that makes sence. 31 works by the way. 2. well, i forgot the other question.... Maybe you could allso explain something about the p1 trial factoring? im not even sure what it does and not at all how it works. thaks again. Regards Last fiddled with by zacariaz on 20070511 at 03:10 

20070511, 07:28  #7 
Einyen
Dec 2003
Denmark
5^{2}·127 Posts 
Here is the complete list of the 44 known mersenne primes: http://mathworld.wolfram.com/MersennePrime.html
LL test for p=17: S_{0}=4 S_{1}=14 S_{2}=194 S_{3}=37634 S_{4}=95799 (mod 131071) S_{5}=119121 (mod 131071) S_{6}=66179 (mod 131071) S_{7}=53645 (mod 131071) S_{8}=122218 (mod 131071) S_{9}=126220 (mod 131071) S_{10}=70490 (mod 131071) S_{11}=69559 (mod 131071) S_{12}=99585 (mod 131071) S_{13}=78221 (mod 131071) S_{14}=130559 (mod 131071) S_{15}=0 (mod 131071) p=19: S_{0}=4 S_{1}=14 S_{2}=194 S_{3}=37634 S_{4}=218767 (mod 524287) S_{5}=510066 (mod 524287) S_{6}=386344 (mod 524287) S_{7}=323156 (mod 524287) S_{8}=218526 (mod 524287) S_{9}=504140 (mod 524287) S_{10}=103469 (mod 524287) S_{11}=417706 (mod 524287) S_{12}=307417 (mod 524287) S_{13}=382989 (mod 524287) S_{14}=275842 (mod 524287) S_{15}=85226 (mod 524287) S_{16}=523263 (mod 524287) S_{17}=0 (mod 524287) 
20070511, 10:48  #8  
Nov 2003
2^{2}×5×373 Posts 
Quote:
how to do the arithmetic that is involved in the algorithm. It does NOTHING toward explaining the mathematics of the algorithm or why it works. The bottom line is that one can not understand the math behind the algorithm without knowing something about finite fields and group theory. The last time that I explained why the algorithm works I got royally flamed for my effort, so I will not do it again. 

20070511, 15:16  #9  
May 2007
denmark
1101_{2} Posts 
Quote:
Just to make it clear, i know understand how to use the lucas lehmer test, next step will be for me to figure out how to use it with very big number plus optimising it and that is nothing you need to help with, allthough help would be welcome. Still though i would like some input on the P1 test. About knowledge i might not have enough, but im definently not stupid, i love math and an example on that is that in 8. grade or so, whitout any great knowledge in math i came up with the formula: http://zacariaz.urbanblog.dk/files/2006/11/eqn7407.jpg My mathteacher was very impressed allthough i was of course not the first. Regards Last fiddled with by zacariaz on 20070511 at 15:22 

20070511, 15:22  #10  
Feb 2007
2^{4}·3^{3} Posts 
Quote:
can't you just print out the 15 values of s[k+1]= s[k]^22 mod M(17) ? 

20070511, 16:05  #11 
∂^{2}ω=0
Sep 2002
República de California
2×3×29×67 Posts 
ATH was kind enough to give you the exact periteration residues for the LL test of these two exponents  it's up to you to debug your own program. Given that numbers this small can be tested using just singleword integers or floating doubles or even a pocket calculator, how hard can it be?

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Understanding assignment rules  Fred  PrimeNet  3  20160519 13:40 
Understanding NFS  Demonslay335  YAFU  11  20160108 17:52 
understanding the group G in an explanation of the LucasLehmer test  wildrabbitt  Math  1  20150517 12:34 
Understanding the LL proof and then more related stuff following it  Raman  Math  4  20120524 05:37 
Math IQ/ effort test  science_man_88  Lounge  2  20110808 01:56 