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 n-1 iterations for the possible prime n.

Now why does it have to go thru all those iterations? My thinking is a number (non-prime) 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

[ET_]

The algorithm you showed is time-consuming and not so efficient as Lucas-Lehmer test.

If you are interested in algorithms, try this link:

http://www.mersenne.org/math.htm

Luigi

[dsouza123]

The Lucas-Lehmer algorithm isn't trying to find factors, that is what the earlier elimination tests trial factoring and p-1 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 )

[cheesehead]

Originally Posted by benmichaelx

I've been watching prime 95 working hard on my machine the last few months going thru what I believe to be n-1 iterations for the possible prime n.

The numbers Prime95 tests are of the form 2^[b]n[/b]-1 -- that is, 2 raised to the power of n, minus 1. For example, 2⁵ - 1 = (2 x 2 x 2 x 2 x 2) - 1 = 31.

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.

Now why does it have to go thru all those iterations?

Well, 20996011 iterations is a lot, but it's far, far less than 2^20996011-1 iterations. 20996011 iterations takes several weeks. 2^20996011-1 iterations would take much, much longer than the age of the universe!