 mersenneforum.org LL Test: Understanding the math
 Register FAQ Search Today's Posts Mark Forums Read  2007-05-10, 21:05 #1 zacariaz   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   2007-05-10, 21:56 #2 paulunderwood   Sep 2002 Database er0rr F1516 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 2007-05-10 at 21:56   2007-05-10, 23:14 #3 ATH Einyen   Dec 2003 Denmark 52·127 Posts Try: The Little Book of Bigger Primes.pdf "Section 2 IV: Lucas Sequences" page 44-62 and "Section 2 VII Mersenne Numbers" page 75-87.   2007-05-10, 23:48   #4
Jens K Andersen

Feb 2006
Denmark

23010 Posts Quote:
 Originally Posted by ATH Try: The Little Book of Bigger Primes.pdf
Is it allowed to make that freely available?   2007-05-11, 01:26 #5 dsouza123   Sep 2002 29616 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. LUCAS-LEHMER DETAILS This program uses the Lucas-Lehmer 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 (p-1) = 0. This program uses a discrete weighted transform (see Mathematics of Computation, January 1994) to square numbers in the Lucas-Lehmer sequence. The Lucas-Lehmer 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 2007-05-11 at 01:39 Reason: Small addition.   2007-05-11, 03:02   #6
zacariaz

May 2007
denmark

13 Posts Quote:
 Originally Posted by dsouza123 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.
For some reason my help file doesnt work.

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 p-1 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 2007-05-11 at 03:10   2007-05-11, 07:28 #7 ATH Einyen   Dec 2003 Denmark 52·127 Posts Here is the complete list of the 44 known mersenne primes: http://mathworld.wolfram.com/MersennePrime.html LL test for p=17: S0=4 S1=14 S2=194 S3=37634 S4=95799 (mod 131071) S5=119121 (mod 131071) S6=66179 (mod 131071) S7=53645 (mod 131071) S8=122218 (mod 131071) S9=126220 (mod 131071) S10=70490 (mod 131071) S11=69559 (mod 131071) S12=99585 (mod 131071) S13=78221 (mod 131071) S14=130559 (mod 131071) S15=0 (mod 131071) p=19: S0=4 S1=14 S2=194 S3=37634 S4=218767 (mod 524287) S5=510066 (mod 524287) S6=386344 (mod 524287) S7=323156 (mod 524287) S8=218526 (mod 524287) S9=504140 (mod 524287) S10=103469 (mod 524287) S11=417706 (mod 524287) S12=307417 (mod 524287) S13=382989 (mod 524287) S14=275842 (mod 524287) S15=85226 (mod 524287) S16=523263 (mod 524287) S17=0 (mod 524287)   2007-05-11, 10:48   #8
R.D. Silverman

Nov 2003

22×5×373 Posts Quote:
 Originally Posted by dsouza123 What part of the math in particular ? 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.
Please excuse me as I intend no flame, but this post explains (fairly well)
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.   2007-05-11, 15:16   #9
zacariaz

May 2007
denmark

11012 Posts Quote:
 Originally Posted by R.D. Silverman Please excuse me as I intend no flame, but this post explains (fairly well) 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.
Fair enough, i can understand that. But what i really want to know about the lucas lehmer test is really only why i cant get it to work with 17 and 19, does anyone have an idea?

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 P-1 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 2007-05-11 at 15:22   2007-05-11, 15:22   #10
m_f_h

Feb 2007

24·33 Posts Quote:
 Originally Posted by zacariaz what i really want to know about the lucas lehmer test is really only why i cant get it to work with 17 and 19, does anyone have an idea?
from where on differ your results w.r.t. ATH's list given below ?
can't you just print out the 15 values of s[k+1]= s[k]^2-2 mod M(17) ?   2007-05-11, 16:05   #11
ewmayer
2ω=0

Sep 2002
República de California

2×3×29×67 Posts Quote:
 Originally Posted by zacariaz But what i really want to know about the lucas lehmer test is really only why i cant get it to work with 17 and 19, does anyone have an idea?
ATH was kind enough to give you the exact per-iteration 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 single-word integers or floating doubles or even a pocket calculator, how hard can it be?   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Fred PrimeNet 3 2016-05-19 13:40 Demonslay335 YAFU 11 2016-01-08 17:52 wildrabbitt Math 1 2015-05-17 12:34 Raman Math 4 2012-05-24 05:37 science_man_88 Lounge 2 2011-08-08 01:56

All times are UTC. The time now is 02:07.

Tue Oct 19 02:07:49 UTC 2021 up 87 days, 20:36, 0 users, load averages: 1.60, 1.66, 1.69