Rho factorization method

The Rho factorization method was invented by John Pollard in 1974.

The idea is to create a sequence iterating a polynomial modulo the number to be factored.

So the sequence will be:

• [math]\displaystyle{ x_0 }[/math]
• [math]\displaystyle{ x_1 = f(x_0) }[/math]
• [math]\displaystyle{ x_2 = f(x_1) }[/math]

and so on.

In general this polynomial is a quadratic [math]\displaystyle{ x_{n+1} = x_n^2 + a }[/math], where [math]\displaystyle{ a \neq -2 }[/math].

There are [math]\displaystyle{ N }[/math] values [math]\displaystyle{ \!\bmod N }[/math], so the sequence cannot have more than [math]\displaystyle{ N }[/math] distinct values. It can be shown that in average the sequence will have about [math]\displaystyle{ \sqrt{N} }[/math] different values.

When [math]\displaystyle{ N = pq }[/math] where [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math] are coprime but not necessarily prime, we will see that after about [math]\displaystyle{ \sqrt{p} }[/math] elements the sequence will start repeating [math]\displaystyle{ \!\bmod p }[/math].

We can detect if two elements of the sequence [math]\displaystyle{ x_m }[/math] and [math]\displaystyle{ x_n }[/math] are congruent [math]\displaystyle{ \!\bmod p }[/math] by computing the greatest common divisor ([math]\displaystyle{ \gcd(x_m - x_n, N) }[/math]) which will reveal the unknown factor [math]\displaystyle{ p }[/math].

So what we need is to detect the sequence repetition.

There is a method invented by Floyd that consists in computing [math]\displaystyle{ x_1 }[/math], [math]\displaystyle{ x_2 }[/math], [math]\displaystyle{ x_3 }[/math] and so on by iterating the polynomial, and at the same time computing [math]\displaystyle{ x_2 }[/math], [math]\displaystyle{ x_4 }[/math], [math]\displaystyle{ x_6 }[/math] and so on by iterating the polynomial twice. Then we compare [math]\displaystyle{ x_n }[/math] against [math]\displaystyle{ x_{2n} }[/math] to check for a coincidence.

Then we have to compute [math]\displaystyle{ \gcd(x_1 - x_2, N) }[/math], [math]\displaystyle{ \gcd(x_2 - x_4, N) }[/math], [math]\displaystyle{ \gcd(x_3 - x_6, N) }[/math], and so on until we find a proper factor of [math]\displaystyle{ N }[/math].

Since computing GCD's are expensive, we can trade most of the GCD's by multiplications. For example we can compute in batches of four elements:

• [math]\displaystyle{ \gcd((x_1 - x_2)(x_2 - x_4)(x_3 - x_6)(x_4 - x_8), N) }[/math]
• [math]\displaystyle{ \gcd((x_5 - x_{10})(x_6 - x_{12})(x_7 - x_{14})(x_8 - x_{16}), N) }[/math]

and so on.

A method that requires less modular multiplications was invented by Richard Brent in 1980 who used it to factor the eighth Fermat number.

Example

Suppose we want to factor the number 9271 using the polynomial [math]\displaystyle{ x^2 + 1 }[/math] and the initial point [math]\displaystyle{ x_0 = 5 }[/math]. All multiplications are done modulo 9271.

Step 1:

[math]\displaystyle{ x_1 = x_0^2 + 1 = 26 }[/math]

[math]\displaystyle{ x_2 = x_1^2 + 1 = 677 }[/math]

Step 2: [math]\displaystyle{ (x_2, x_4) = (677, 932) }[/math]

Step 3: [math]\displaystyle{ (x_3, x_6) = (4051, 4677) }[/math]

Step 4: [math]\displaystyle{ (x_4, x_8) = (932, 3451) }[/math]

Batch gcd: [math]\displaystyle{ \gcd((26-677)(677-932)(4051-4677)(932-3451), 9271) = 1 }[/math]. We have to continue.

Step 5: [math]\displaystyle{ (x_5, x_{10}) = (6422, 6626) }[/math]

Step 6: [math]\displaystyle{ (x_6, x_{12}) = (4677, 5991) }[/math]

Step 7: [math]\displaystyle{ (x_7, x_{14}) = (4041, 3451) }[/math]

Step 8: [math]\displaystyle{ (x_8, x_{16}) = (3451, 6626) }[/math]

Batch gcd: [math]\displaystyle{ \gcd((6422-6626)(4677-5991)(4041-3451)(3451-6626), 9271) = 9271 }[/math]. Since we found the original number we have to perform the GCD for every member in this batch.

[math]\displaystyle{ \gcd(x_5 - x_{10}, N) = \gcd(6422-6626, 9271) = 1 }[/math]

[math]\displaystyle{ \gcd(x_6 - x_{12}, N) = \gcd(4677-5991, 9271) = 73 }[/math]

So 73 is a proper factor of 9271.

External links

• Wikipedia