20040122, 18:55  #1 
3202_{8} Posts 
question about the algo
I'm not the greatest mathamatitian (Ok, I'm lucky I can add 2+2). But I've been watching prime 95 working hard on my machine the last few months going thru what I believe to be n1 iterations for the possible prime n.
Now why does it have to go thru all those iterations? My thinking is a number (nonprime) can only be divisible by a number that is half itself or less. For example the number 12. It is divisible by numbers less than or equal to half of 12 in otherwords less than or equal to the number 6. 1,2,3,4 and 6. Is this true for all numbers? So to test if something is prime could we stop once we've reached the halfway point. I realize this may be obviously wrong or right to all of you geniuses out there but ... I was just thinking. Ben 
20040122, 19:07  #2 
Banned
"Luigi"
Aug 2002
Team Italia
1001011000011_{2} Posts 
The algorithm you showed is timeconsuming and not so efficient as LucasLehmer test.
If you are interested in algorithms, try this link: http://www.mersenne.org/math.htm Luigi 
20040122, 23:05  #3 
Sep 2002
2·331 Posts 
The LucasLehmer algorithm isn't trying to find factors, that is what the earlier elimination tests trial factoring and p1 factoring do.
LL works as follows (from the prime95.chm help file) For example, to prove 2^7  1 is prime: ( 2^7  1 = 128  1 = 127 ) With the exponent 7 there are 7  2 iterations. Always start with S(0) = 4, square, subtract two, mod by the mersenne number, use the remainder as the starting value for the next iteration. S (0) = 4 S (1) = 4 * 4  2 mod 127 = 14 S (2) = 14 * 14  2 mod 127 = 67 S (3) = 67 * 67  2 mod 127 = 42 S (4) = 42 * 42  2 mod 127 = 111 S (5) = 111 * 111  2 mod 127 = 0 Only if the result of the last iteration is 0 is it a mersenne prime. Using a special math technique (dwt) prime95 doesn't actually do the mods. Trial factoring is a specialized version of the algorithm you described. The mersenne numbers that are being tested are very large so instead of testing to half ( really only to the square root is sufficient ) the factors tested are numbers (maximum) that can fit in upto 72 bits, depending on the size of the mersenne exponent ( smaller exponents go to a smaller number of bits ). 72 bits can hold a 22 digit number ( factor ). Each factor ( q ) is in the form 2kp + 1, with each k a positive integer. Example for 2^17  1, if trial factoring the factors tested would be 2*1*17 + 1 = 35, 2*2*17 + 1 = 69, 2*3*17 + 1 = 103, 2*4*17 + 1 = 137 2*5*17 + 1 = 171, ... 2*10*17 + 1 = 341 any bigger would be above the integer square root of 131071 = 362 ( 2^17  1 = 131071 ) 
20040123, 12:36  #4  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
Quote:
It can be proven that if n is not a prime, then 2^{[b]n[/b]}1 is also not a prime. So when we're looking for 2^{[b]n[/b]}1 that is prime, we consider only the cases where n itself is a prime. We often write 2^{[b]n[/b]}1 as 2^{[b]p[/b]}1 to remind ourselves that we are looking only at the cases where the exponent (n or p) is a prime. The fact that there are two different primes involved  p and {we hope this is prime} 2^{[b]p[/b]}1  can sometimes be confusing. Suppose the number that Prime95 is testing is 2^{20996011}1. The exponent, 20996011, has only eight decimal digits. But the tested number, 2^{20996011}1, has over six million decimal digits. To test this number, Prime95 must perform only 20996010 iterations, not 2^{20996011}1 iterations. Quote:

