Pollard's p − 1 algorithm

The Pollard p- 1 method is a method of factorization of composite numbers. It was described in 1974 by John M. Pollard.

Mathematical Foundations

The p -1 factorization of Pollard is based on Fermat's little theorem. Let p be a prime number, and a is a number which is not divided by p, then

Similarly then for any multiple m of p -1. This means that on -1 is a multiple of p. Now, if N is a number to be factored with ( unknown ) prime factor p, p divides this to, as it divides the two numbers, of which the gcd was formed. Most of this is a proper divisor gcd of N. The following section describes a method of how to find a matching number m.

The first stage of the procedure

Let now given a natural number N to be factored. In particular, N is a composite number. One chooses a number a which is relatively prime to N. Based on a heuristic is determined by another number B, which is assumed that for every prime divisor p of N the number p -1 is B- smooth potency. That is, for each prime divisor q ' of p -1:

Eq, the number (p-1 ) is the exponent of the Q- P-1. It indicates how many times the number q in the prime factorization of p-1 occurs. Substituting in the inequality, the number p-1 by an arbitrary potency B- smooth number m, the inequality remains true. Working according to the q- exponent provides:

Are B and q are chosen to fix, so this formula to a sharp upper limit for the q- exponent. If this is greater than the right side of the inequality, so m is not more potency B- smooth. It is now

This is the greatest q- exponent, which a B- smooth number potency may have m. You create a list next F, in which the prime q occurs exactly fq times. The primes in the list, ..., qR numbered with q1, q2, q3, where R is the number of list elements of F. The product of all numbers in F is denoted by M. By construction, M is B- potency smooth. It is even the greatest potency B- smooth number.

N has at least one prime divisor p of p -1 B- potency smooth, then M is a multiple of this number p -1. Therefore, it is (see previous paragraph) a proper divisor of N, or equal to N. In general, a smaller sufficient power of a as the Mth from to get a divider. The practical approach is therefore the following: One calculates iteratively

Here, the appearing powers are replaced by their residues modulo N in each step. After a certain number of steps, e.g. 20, to check whether it has already found a divider. That is, one considers. If this gcd greater than 1, then one has a divider determined, and aborts the process; is the gcd equal to 1, one proceeds in steps of 20, until one has a divider found or reached.

A total of three cases can occur at the end:

The second phase of the process

The method fails in the first phase, the cause is often that which applies to the prime factors p of N that. Where u B- smooth or even B- potency smooth, and l is a prime number that is greater than B. In other words, p-1 is smooth because of a single prime factor not B ( potency ).

Therefore, one selects a second barrier B1 to "capture " the factor L. B1 should be chosen substantially larger than B, but not greater than B2. Often one chooses B1 in the range of B4 / 3

Analogous to the first phase created at the list of primes F1 lying between B and B1. This one stores the first of these numbers as l1, and contributes to the list the differences between adjacent primes one. The number of elements of F1 is S. Note: For B1 < 20 million each of these differences is less than or equal to 200 means, there are few, and only small differences is on.

As a starting value for the second phase, the number aR, which was calculated at the end of the first phase serves. As further preparation is calculated for each difference d in F1, the number

On the one hand only a few jd will need to be calculated, on the other hand, only a small power is needed. As you start in Phase 1 now again an iteration. It is possible to replace the time-consuming exponentiation by multiplication.

It should ie the difference between the (i-1 ) th and the i- th prime in F1. Again, replacing the numbers in each step by its residues modulo N.

Other than in phase 1, it is not sufficient to form after a fixed number of steps to. Instead, you have the numbers aR i-1 accumulate, that is, by forming the product of all these numbers. This can be done in the course of the above iteration by z1 = aR 1-1, and zi = zi -1 * ( aR i-1) sets. By accumulating is achieved, that the prime factors p can be found by N, which is more than a prime factor of p- 1 is greater than b.

After a fixed number of steps, for example every 20, again, is formed. Recovery can occur at the end of the three cases that could occur at the end of Phase 1. The method fails, it may be the barriers B and B1 enlarge and start the procedure again. It is better, however, to use a different method in this case.

The heuristic of the largest prime divisor

A natural number m has an average prime divisors. This statement can be formulated precisely and prove it. It does so as if the number of prime divisors of m exactly this value, that is, one assumes that

Now let q is the largest prime divisor of m. Then:

Solving this equation for q yields:

Where e is Euler's number. This is a heuristic justification that the largest prime factor of m is approximately equal m0.632. This fact is used to determine a value for the search bound B of the above process.

Apply to the method

N is now a composite integer to which one wishes to use the p-1 method. Since it is composed, it has a prime divisor p ≤. After the heuristic applies to the largest prime factor q of p -1

So we choose B ≥ N0, 316, it is expected that p-1 is B- smooth. The B- potency smoothness can now be achieved like this: Suppose p-1 is B- smooth. Then for all prime divisors q of p -1:

As in the description of the first phase ( see above ), we obtain from this for a B- potency smooth number m:

The number fq is here the same as that calculated in the 1st phase.

This means that for this choice of B is necessary to replace the values ​​of FQ * fq by the slightly larger values ​​of 1.6 to achieve the B power smoothness of the P-1.

In practice, one sets a value for B, and vice versa includes, for what values ​​of N this bound is sufficient. The following applies:

Complexity of the procedure

From the estimation of B ≥ N0, 316 results in a complexity of the process of:

The effort is exponential in the length of the input.

Applications

The Pollard p- 1 method is used, among others, GIMPS ( Great Internet Mersenne Prime Search ) to factor numbers of the form, thus reducing the number of necessary for the search for Mersenne primes time-consuming Lucas -Lehmer test.