mersenneforum.org How it works?
 Register FAQ Search Today's Posts Mark Forums Read

 2007-03-10, 08:57 #1 kuratkull     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 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 :)
 2007-03-10, 12:54 #2 dsouza123     Sep 2002 10100101102 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 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
2007-03-10, 12:57   #3
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

102538 Posts

Quote:
 Originally Posted by kuratkull 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 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

 2007-03-10, 15:05 #4 Unregistered   157C16 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.
 2007-03-11, 12:52 #5 kuratkull     Mar 2007 Estonia 14210 Posts 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 :)
2007-03-11, 14:26   #6
Peter Nelson

Oct 2004

232 Posts

Quote:
 Originally Posted by kuratkull 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

 2007-03-11, 17:34 #7 kuratkull     Mar 2007 Estonia 2×71 Posts Thx mate, your answer helped me to understand this(again?) ^^
2007-03-11, 18:42   #8
davieddy

"Lucan"
Dec 2006
England

145128 Posts

Quote:
 Originally Posted by Peter Nelson 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

2007-03-12, 07:53   #9

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts

Quote:
 Originally Posted by davieddy 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

 2007-03-12, 09:44 #10 davieddy     "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.
 2007-03-15, 20:15 #11 Peter Nelson     Oct 2004 232 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post shahabmp Information & Answers 4 2016-01-27 04:20 Chuck GPU to 72 12 2012-08-15 13:21 jinydu Information & Answers 2 2009-03-16 02:39 jasong Software 16 2006-07-20 20:14 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