mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2007-03-10, 08:57   #1
kuratkull
 
kuratkull's Avatar
 
Mar 2007
Estonia

2·71 Posts
Default How it works?

Hello, I have been running the client for over a week now, and I am very interested about how this thing works.

Code:
Iteration 6350000 / 19078159
This is the exponent, right? So it tries to see if
219078159-1 is a mersenne number by doing the iterations?

What do the iterations show?

Thank you :)
kuratkull is offline   Reply With Quote
Old 2007-03-10, 12:54   #2
dsouza123
 
dsouza123's Avatar
 
Sep 2002

10100101102 Posts
Default

Each iteration is the square of the previous iteration minus 2 mod 2^P - 1.
In the example below for 2^7 - 1 there are effectively 5 full iterations,
the very first just is initialized with 4.

From the Prime95 help file:
Code:
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
Prime95 is highly optimized both mathematically and in CPU instructions,
it uses ibdwt a type of fft to do the squaring with the mod essentially free
with the math routines in optimized assembly language
using a combination of ALU, 3DNow, FPU, SSE2 instructions depending
on the instruction support of the CPU along with intricate use of the CPU caches.

Last fiddled with by dsouza123 on 2007-03-10 at 13:01
dsouza123 is offline   Reply With Quote
Old 2007-03-10, 12:57   #3
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

102538 Posts
Default

Quote:
Originally Posted by kuratkull View Post
This is the exponent, right? So it tries to see if
219078159-1 is a mersenne number by doing the iterations?
Yes.
Quote:
Originally Posted by kuratkull View Post
What do the iterations show?
They are iterations of the Lucas-Lehmer test (abbreviated to LL test or LL). Here's more info on the LL test.
Read the Wikipedia link I posted below under the "The Test" section.
Another way of saying what Wikipedia says is this:
For your exponent (19078159) there need to be 19078157 (which is p-2) iterations of squaring the last iteration's result then subtracting two, which is all done modulo 219078159-1. Iff p-2 (p is your exponent) of the sequence is 0, then the number is prime. The sequence starts with a 4 at number 0 in the sequence.

Note that all iterations need to be completed before you know anything about the number. It is not like factoring where as you're running it more and more factors are eliminated. Each iteration needs to know the iteration before it, and you need to know p-2 of the sequence before you know whether it is prime or not.

This allows a >10 million digit number (even though yours is "only" 5,743,099 digits) to be tested without having to work with any numbers larger than 2P-1 (or (2P-1)2, I'm not 100% sure which)

http://en.wikipedia.org/wiki/Lucas%E...rsenne_numbers
http://mathworld.wolfram.com/Lucas-LehmerTest.html

edit: dsouza123 refers to the first iteration as 1, not 0. This causes a discrepancy between our posts. I hope it doesn't confuse you.

Last fiddled with by Mini-Geek on 2007-03-10 at 12:58
Mini-Geek is offline   Reply With Quote
Old 2007-03-10, 15:05   #4
Unregistered
 

157C16 Posts
Default

Thanks :) I will try to understand some of these mathematical expressions as English is not my first language, but at a first glance I seemed to understand it. Thanks again.
  Reply With Quote
Old 2007-03-11, 12:52   #5
kuratkull
 
kuratkull's Avatar
 
Mar 2007
Estonia

14210 Posts
Default

Hmm, is the number 4 always the first number to try with? Could someone post the first few lines of 28-1 or something?

Thanks a lot :)
kuratkull is offline   Reply With Quote
Old 2007-03-11, 14:26   #6
Peter Nelson
 
Peter Nelson's Avatar
 
Oct 2004

232 Posts
Default

Quote:
Originally Posted by kuratkull View Post
Hmm, is the number 4 always the first number to try with? Could someone post the first few lines of 28-1 or something?

Thanks a lot :)

You can't just choose an arbitrary starting point.

But, from http://primes.utm.edu/mersenne/

"(It is also possible to start with S(1)=10 and certain other values depending on p.) "

Note that the sequence of numbers generated along the way will be different but after the final iteration, the same "Is it zero?" answer will be consistent.

If you are doing two tests, one as the original and another to verify your calculation, there may be benefit in using different architectures and different initialisation points for the tests (since the calculations are different they are less vulnerable to a mass hardware fault like the pentium FP bug) . On the other hand, it would not allow two machines to compare intermediate (say half way point) results to detect computational errors before the end.

By the way, 2^8 -1 is COMPOSITE ie NOT PRIME.

If you work through the LL iterations yourself you will find the last number is NOT ZERO which tells you the number isn't prime.

However 2^8-1 =255. We could avoid doing the LL test if we found a small factor of it, and in fact both 3 and 5 are factors of 255 so we know it is composite without doing the LL test. Prime95 uses this principle to perform "trial factoring" first, then certain other factoring attempts before commencing on the LL test if the candidate was not successfully factored yet.

Last fiddled with by Peter Nelson on 2007-03-11 at 14:36
Peter Nelson is offline   Reply With Quote
Old 2007-03-11, 17:34   #7
kuratkull
 
kuratkull's Avatar
 
Mar 2007
Estonia

2×71 Posts
Default

Thx mate, your answer helped me to understand this(again?) ^^
kuratkull is offline   Reply With Quote
Old 2007-03-11, 18:42   #8
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

145128 Posts
Default

Quote:
Originally Posted by Peter Nelson View Post
You can't just choose an arbitrary starting point.

But, from http://primes.utm.edu/mersenne/

"(It is also possible to start with S(1)=10 and certain other values depending on p.) "

Note that the sequence of numbers generated along the way will be different but after the final iteration, the same "Is it zero?" answer will be consistent.

If you are doing two tests, one as the original and another to verify your calculation, there may be benefit in using different architectures and different initialisation points for the tests (since the calculations are different they are less vulnerable to a mass hardware fault like the pentium FP bug) . On the other hand, it would not allow two machines to compare intermediate (say half way point) results to detect computational errors before the end.
But to doublecheck a LL test with a non zero residue, different
starting values produce differing final residues, rendering the
"check" impossible. To make the calculations different, the S(1)
values are "shifted" by a random amount for each test.

David
davieddy is offline   Reply With Quote
Old 2007-03-12, 07:53   #9
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Quote:
Originally Posted by davieddy View Post
But to doublecheck a LL test with a non zero residue, different starting values produce differing final residues, rendering the "check" impossible. To make the calculations different, the S(1) values are "shifted" by a random amount for each test.
Attempted clarification (I hope):

AFAIK, GIMPS Prime95 et al. (mprime, ...) stores the final 64-bit residue only after normalizing the entire final residue by undoing the shift at the end. This makes all stored 64-bit residues comparable, while retaining the shift's advantage of causing a different computational path (i.e., bits in different positions) throughout the S(i) calculations.

Now, what I'm referring to here is starting always with the same value (i.e., 4 instead of 10) then shifting that value by the random amount before entering the first iteration (and unshifting by the same amount at the end), not starting with a 10 instead of a 4.

(Side note: 10 cannot be a result of merely shifting a 4, so I think there's no potential overlap between a 4-shifted-then-iterated-then-unshifted nonzero residue and a 10-shifted-then-iterated-then-unshifted nonzero residue. But I could be wrong.)

Last fiddled with by cheesehead on 2007-03-12 at 07:57
cheesehead is offline   Reply With Quote
Old 2007-03-12, 09:44   #10
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

That is my understanding. Can someone confirm that
the final residues when starting from 4 and 10 are unrelated
to each other? I know they are different.
BTW I have implemented the "shifting" process in BASIC and
how it works is instructive.
davieddy is offline   Reply With Quote
Old 2007-03-15, 20:15   #11
Peter Nelson
 
Peter Nelson's Avatar
 
Oct 2004

232 Posts
Default

I think you're right (and yes there can be shifting).

What I said was that once you had a test with a result "It's a prime" for a VERIFICATION test, it might be advantageous not to use the same starting point as you only need a zero endpoint as your confirmation.

If the result of the first test was "Composite" then for comparison of the final residue, the "DOUBLE CHECK for compositeness" will likely be done with the same starting point ie 4.
Peter Nelson is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
why works on m11846267 shahabmp Information & Answers 4 2016-01-27 04:20
OK now I know the proxy REALLY works Chuck GPU to 72 12 2012-08-15 13:21
Copying Latex No Longer Works? jinydu Information & Answers 2 2009-03-16 02:39
DC guide to building ecm client no longer works(my theory inside) jasong Software 16 2006-07-20 20:14
Dialup with command line version works well dsouza123 NFSNET Discussion 5 2003-10-12 03:00

All times are UTC. The time now is 10:47.

Tue May 11 10:47:04 UTC 2021 up 33 days, 5:27, 1 user, load averages: 2.23, 1.87, 1.64

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.