20070310, 08:57  #1 
Mar 2007
Estonia
2·71 Posts 
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 2^{19078159}1 is a mersenne number by doing the iterations? What do the iterations show? Thank you :) 
20070310, 12:54  #2 
Sep 2002
1010010110_{2} Posts 
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 LucasLehmer primality test to see if 2^P1 is prime. The Lucas sequence is defined as: S (1) = 4 S (n+1) = (S (n)^2  2) mod (2^P1) 2^P1 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 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 20070310 at 13:01 
20070310, 12:57  #3  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
10253_{8} Posts 
Quote:
They are iterations of the LucasLehmer 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 p2) iterations of squaring the last iteration's result then subtracting two, which is all done modulo 2^{19078159}1. Iff p2 (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 p2 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 2^{P}1 (or (2^{P}1)^{2}, I'm not 100% sure which) http://en.wikipedia.org/wiki/Lucas%E...rsenne_numbers http://mathworld.wolfram.com/LucasLehmerTest.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 MiniGeek on 20070310 at 12:58 

20070310, 15:05  #4 
157C_{16} Posts 
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.

20070311, 12:52  #5 
Mar 2007
Estonia
142_{10} Posts 
Hmm, is the number 4 always the first number to try with? Could someone post the first few lines of 2^{8}1 or something?
Thanks a lot :) 
20070311, 14:26  #6  
Oct 2004
23^{2} Posts 
Quote:
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^81 =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 20070311 at 14:36 

20070311, 17:34  #7 
Mar 2007
Estonia
2×71 Posts 
Thx mate, your answer helped me to understand this(again?) ^^

20070311, 18:42  #8  
"Lucan"
Dec 2006
England
14512_{8} Posts 
Quote:
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 

20070312, 07:53  #9  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Quote:
AFAIK, GIMPS Prime95 et al. (mprime, ...) stores the final 64bit residue only after normalizing the entire final residue by undoing the shift at the end. This makes all stored 64bit 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 4shiftedtheniteratedthenunshifted nonzero residue and a 10shiftedtheniteratedthenunshifted nonzero residue. But I could be wrong.) Last fiddled with by cheesehead on 20070312 at 07:57 

20070312, 09:44  #10 
"Lucan"
Dec 2006
England
2·3·13·83 Posts 
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. 
20070315, 20:15  #11 
Oct 2004
23^{2} Posts 
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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
why works on m11846267  shahabmp  Information & Answers  4  20160127 04:20 
OK now I know the proxy REALLY works  Chuck  GPU to 72  12  20120815 13:21 
Copying Latex No Longer Works?  jinydu  Information & Answers  2  20090316 02:39 
DC guide to building ecm client no longer works(my theory inside)  jasong  Software  16  20060720 20:14 
Dialup with command line version works well  dsouza123  NFSNET Discussion  5  20031012 03:00 