2.4.1 Pollard's Rho-Factoring-Algorithm

Pollard's rho factoring algotrithm is a special-purpose algorithm for finding small non-trivial factors of an integer. Have a look at following proposition:

Let f: S→S be a random function, where |S| = n. Let further be x₀ ∈ S, at random. Consider the sequence x₀, x₁, x₂, ... defined by x_i+1 = f(x_i ). Since S is finite, the sequence must eventually cycle and be composed of a tail.

For finding out the length of the cycle, following algorithm is suitable (Floyd's cycle-finding algorithm):

In this method one starts with the pair (x₁ , x₂ ) and iteratively computes (x_i , x_2i ) from the previous pair (x_i-1 , x_2i-2 ) until a duplicate x_m = x_2m appears for some m. ⇒ If the tail of the sequence has length λ and the cycle has length μ, so the first time when x_m = x_2m is when m = μ (1 + ⌊λ / μ ⌋ ).

Now Floyd's algorithm is utilized by Pollard's rho algorithm to find such a duplicate in the sequence of integers y₀, y₁, y₂, ..., y_i ∈ Z ∀ i. That sequence is defined by: y₀ = 2, y_i+1 = f(y_i ) = (y_i² + 1) mod p, i ≥ 0. Now Floyd's algorithm is used to find y_m and y_2m with y_m ≡ y_2m (mod p). Since p devides n, but is unknown, this is done by computing the terms y_i mod n and testing whether is gcd(y_m - y_2m , n ) > 1. If such an m is found and if gcd(y_m - y_2m , n ) < n, then a non-trivial factor of n is obtained (=n occurs with low probability).

Example:

Let be n = 221. We start with:

y₀ = 2
y₁ = f(y₀ ) = ((y₀ )² + 1) mod n = 5, y₂ = f( f( y₀ )) = 26, d = gcd(y₁ - y₂ , n ) = gcd ( 21, 221 ) = 1,
y₂ = 26, y₄ = 197, d = gcd ( 26 - 197, 221 ) = 1,
y₃ = 26² + 1 mod 221 = 14, y₆ = 104, d = gcd ( 90, 221 ) = 1,
y₄ = 197, y₈ = 145, d = 13,
So 13 is a non-trivial factor of 221 and the other non-trivial factor is 221 / 13 = 17.

If the algorithm terminates with failure, you can try again with a different function f having another integer coefficient for example f = x² + c , c ≠ 0, -2
But consider that this algoithm is meant for composite integers which are not prime powers.

Applet Rho-Factorization:

Quellcode:
RhoFacSF.java - Applet surface class
RhoFac.java - Algorithm class

2.4.2 (p-1)-Faktoring