mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2007-05-10, 21:05   #1
zacariaz
 
May 2007
denmark

13 Posts
Default 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
zacariaz is offline   Reply With Quote
Old 2007-05-10, 21:56   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·773 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2007-05-10, 23:14   #3
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

52·127 Posts
Default

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.
ATH is offline   Reply With Quote
Old 2007-05-10, 23:48   #4
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

23010 Posts
Default

Quote:
Originally Posted by ATH View Post
Try:
The Little Book of Bigger Primes.pdf
Is it allowed to make that freely available?
Jens K Andersen is offline   Reply With Quote
Old 2007-05-11, 01:26   #5
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default

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.
dsouza123 is offline   Reply With Quote
Old 2007-05-11, 03:02   #6
zacariaz
 
May 2007
denmark

13 Posts
Default

Quote:
Originally Posted by dsouza123 View Post
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
zacariaz is offline   Reply With Quote
Old 2007-05-11, 07:28   #7
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

52·127 Posts
Default

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)
ATH is offline   Reply With Quote
Old 2007-05-11, 10:48   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by dsouza123 View Post
What part of the math in particular ?

<snip>

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.
R.D. Silverman is offline   Reply With Quote
Old 2007-05-11, 15:16   #9
zacariaz
 
May 2007
denmark

13 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
zacariaz is offline   Reply With Quote
Old 2007-05-11, 15:22   #10
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24·33 Posts
Default

Quote:
Originally Posted by zacariaz View Post
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) ?
m_f_h is offline   Reply With Quote
Old 2007-05-11, 16:05   #11
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2·3·29·67 Posts
Default

Quote:
Originally Posted by zacariaz View Post
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?
ewmayer is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Understanding assignment rules Fred PrimeNet 3 2016-05-19 13:40
Understanding NFS Demonslay335 YAFU 11 2016-01-08 17:52
understanding the group G in an explanation of the Lucas-Lehmer test wildrabbitt Math 1 2015-05-17 12:34
Understanding the LL proof and then more related stuff following it Raman Math 4 2012-05-24 05:37
Math IQ/ effort test science_man_88 Lounge 2 2011-08-08 01:56

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


Fri Oct 22 07:27:25 UTC 2021 up 91 days, 1:56, 1 user, load averages: 1.74, 1.51, 1.44

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.