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:

• x₀
• x₁ = f(x₀)
• x₂ = f(x₁)

and so on.

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

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

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

We can detect if two elements of the sequence x_m and x_n are congruent mod p by computing gcd(x_m - x_n, N) which will reveal the unknown factor p.

So what we need is to detect the sequence repetition.

There is a method invented by Floyd that consists in computing x₁, x₂, x₃ and so on by iterating the polynomial, and at the same time computing x₂, x₄, x₆ and so on by iterating the polynomial twice. Then we compare x_n against x_2n to check for a coincidence.

Then we have to compute gcd(x₁ - x₂, N), gcd(x₂ - x₄, N), gcd(x₃ - x₆, N), and so on until we find a proper factor of N.

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

• gcd((x₁ - x₂)(x₂ - x₄)(x₃ - x₆)(x₄ - x₈), N)
• gcd((x₅ - x₁₀)(x₆ - x₁₂)(x₇ - x₁₄)(x₈ - x₁₆), N)

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 x²+1 and the initial point x₀ = 5. 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