Pollard's rho algorithm

The Pollard 's Rho- methods are algorithms for determining the period length of a string of numbers, which is calculated using a mathematical function. Several difficult mathematical problems such as the discrete logarithm and factorization can be calculated using these methods. An optimized variant of Pollard 's rho method was developed for the prime factorization of John M. Pollard in 1975. Such a method can also be applied for the calculation of a collision in the hash function.

In the Pollard 's rho method following partial results are calculated. At a certain point, some of these partial results only repeated. You can arrange the partial results graphically so that the shape of the letter reveals ρ ( rho ). Hence the name of the method is derived.

Operation

Wanted is a prime factor p of n In general, however, this divider must be a prime number not mandatory. The method relies on the generation of a sequence of pseudorandom numbers. Establishing the random sequence relative to a desired function can be used. It is only necessary that also follows, and this is an example, if it is represented by a polynomial with integer coefficients.

The episode starts with a substantially arbitrarily selectable start value. The other values ​​are iteratively calculated in accordance with

The function values ​​modulo p maximum of the p different values ​​0, 1, 2, ..., p - 1 Accept. If one of these values ​​then again, so repeat these values ​​modulo p. This occurs after p iterations, and the average after about latest iterations. For the same reasons you can look for some iterations expect a repeat of the values ​​modulo n. If it is already known that n has a small prime factors, is considerably smaller than can be hoped that the repetition modulo p considerably earlier than the repetition using modulo n.

With such a calculated sequence of numbers with a finite number of possible function values ​​are initially in a previous period some values

Accepted. Once a value occurs repeatedly, the values ​​then repeat cyclically

This behavior of the sequence gave the method its name, as you can imagine the period as a circle, which leads into the sequence members start out as a stem in the circle. Graphically, it looks like the Greek letter ρ.

If two values ​​x and y modulo p of the result have the same value, therefore applies to the xy mod p, it follows that gcd (x - y, n ) is a multiple of p, and often a proper divisors of n

However, it is very time-consuming to compare all numerical values ​​in this manner. An optimized variant of Pollard 's rho method therefore calculated to determine the period length of two sequences. one consequence of

And the second sequence

By this trick the comparison of very many function values ​​can be avoided. It now does not need to be calculated for all pairs of the greatest common divisor gcd. It is sufficient in each case to compute the gcd gcd respectively.

Since p, as a sought- divisor of n is unknown, can be calculated first the remainder of the division by p is not. Therefore, it is not requested, the equality of two values ​​x and y, but also the gcd ( x - y, n) is calculated. If the values ​​are different x and y only by a multiple of p, is the value of gcd ( x - y, n ) is a multiple of the desired divider p of n integer multiples of are both integer multiples of p and therefore need at the calculation will not be considered. Consequently, it is sufficient to calculate function values ​​modulo n.

To calculate the numerical sequence is a function of the form f (x) = x2 const can be used. This choice can only be a part of, about half of the values ​​0 to p - 1 occur in the rest of education, whereby the earlier spread of this repetition is slightly favored.

Formal definition

Is the number of a prime factor p is to be calculated. Denote a sequence of pseudo-random numbers, such as

If there is a real prime factor p, then applies

Algorithm

Input: n is the number to be factored and f ( x) is the pseudo-random function modulo n Output: a non-trivial factor of n or an error message

Note: This algorithm provides for all n, the only by 1 and itself are divisible, returns an error message. However, can be returned to the other n is an error message. In this case, one selects a different function f (x) and tries again.

If the result is a number, so this really is also a divisor and thus a correct result, this generally does not necessarily have to be a prime number.

For f one chooses a polynomial with integer coefficients a. A common function f ( x) for this algorithm has the following form:

Estimate of the duration

The sequences of numbers mod p and mod p can be regarded as pseudo - random sequences. If a numerical value recurs, repeat inevitably the following values. It may be accepted up to p values ​​( in square f as above: up to values). Is the expectation value for the length of a cycle. The fact that as p calculations are required far less, is sometimes called the birthday paradox.

The worst case occurs when n is a product of two primes of equal length. The algorithm terminates then after O ( n1 / 4 polylog ( n ) ) steps with probability. The method is well suited to factor numbers with several smaller factors. The algorithm can factorize a number with twice as many points as the trial division at the same time ( with high probability). The algorithm operates exponentially in the length of the input and is therefore slower than the square asymptotically screen and the number field sieve.

Numerical example

Example 1

Are looking for the factors of the number n = 703 We use the function f (x ) = x2 mod n 23 and the initial value x0 = 431:

Thus, the prime factorization of 703 = 19:37 is found.

Example 2

This example shows that the factor found does not necessarily have to be a prime number. The factor found here is 209 = 11.19.

Factorizations

Be factored. denotes a ( primary ) number with 62 points, was proved by the later, that it is a prime number with her.

Implementations

655326
de