P-1 factoring in prime95

[nucleon]

Guys,

I'm reading the math behind prime95 (i.e http://www.mersenne.org/math.htm)

And I'm having trouble understanding the P-1 factoring section. The P-1 link (http://www2.netdoor.com/~acurry/mersenne/archive1/0303.html) is now dead.

Espically I don't understand why do GCD (x-1, (2^P) - 1), where x = 3 ^(E*2*P), P is the P from (2^P) - 1, E is the product of all primes less than B1, and B1 is a suitable bound.

If anyone could point me to a url that explains to a bit more depth, I'd be appreciative. I know what the GCD algorithim is.

The questions in my head are - what range factors specifically does this check? Isn't 'x' from above extremely large to be any use in the GCD? Isn't x very time consuming to calculate?

Out of curiousity does anyone know the computational compexity on GCD(x,y)? For example is it proportional to greater of (log x, log y)?

Any ideas to the above appreciated.

-- Craig

[apocalypse]

To understand the P-1 algorithm, you first need Fermat's Little Theorem: if P is prime, a^(P-1) = 1 (mod P) if gcd(a, P) = 1.

To rewrite, a^(P-1) - 1 = c*P = 0 (mod P)
Hence a^(P-1) - 1 = c*P (mod k*P), let k*P = N, the number we want to factor.

Since we don't know P in advance, we only need a little more arithmetic to show:

a^(m*(P-1)) - 1 = d*P (mod N), let m*(P-1) = E, our product of small primes

So if P-1 divides the product of small primes in the exponent on the left side of the congruence, we will find it when we run GCD(a^(E) - 1, N)

For GIMPS, we use 2*p*E, because it is proven that all factors of Mp are of the form 2kp + 1.

To answer your specific questions:

1) P-1 does not so much test a "range" of factors as a set of factors with a certain quality. In this case, the quality is that the P-1 is the product of "small" numbers. Some of these primes can be very large, much larger than could be found through trial factoring.

2) The value 'x' does not have to be large because it can (and should) be computed modulo the number we are testing (2^p - 1)

3) The time required to compute 'x' depends on the bounds chosen. Multiplying a few thousand numbers together (modulo 2^p -1) is not nearly as time consuming as running a LL-test.

4) The Euclidean Algorithm requires O(lg(x) + lg(y)) steps because one the numbers is reduced by at least half in every iteration. If x and y are the same order of magnitude, the step can be run in O(lg(x) + lg(y)). Otherwise we need to do an integer division step which is more time consuming (O((lg n)^2)?)

For more information, the best general (short) introduction to computational factoring which I have found is "A Survey of Modern Integer Factorization Algorithms" by Montgomery (1994). It has a section on the P-1 algorithm.

[nucleon]

Thanks, still going through it. Still don't understand how (2^P) - 1 fits into what you've said for P - 1 factoring. But thanks for the answers. I'll sleep on it for a while :)

How do I read .psl files from the link you posted?

-- Craig

[apocalypse]

I am using capital P to denote the factor and lowercase p to denote the Mersenne exponent. 2^p - 1 is simply the N we are trying to factor.

To wit: P = 2*k*p + 1

The file is actually a postscript file (should be .ps) If you do not have a postscript reader already, try downloading Ghostscript and GSview. I don't have links handy right now, but you should be able to find them with your favorite search engine.

[cheesehead]

Originally Posted by nucleon

Still don't understand how (2^P) - 1 fits into what you've said for P - 1 factoring.

Originally Posted by apocalypse

I am using capital P to denote the factor and lowercase p to denote the Mersenne exponent. 2^p - 1 is simply the N we are trying to factor.

To wit: P = 2*k*p + 1

Every explanation of the P-1 method to a newbie ought to start with something like "The 'P' in P-1 is not the same as the 'p' in 2^p - 1."

[nucleon]

apoc - thanks.

Ghostview works fine. I'm still reading it at the moment, but my head is starting to hurt :)

Might have a break for a while and get back to it.

-- Craig