Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3).
Navigation
Topics Help • Register • News • History • How to • Sequences statistics • Template prototypes

Rho factorization method

From Prime-Wiki
Revision as of 13:14, 24 January 2019 by Karbon (talk | contribs) (restored)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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:

  • x0
  • x1 = f(x0)
  • x2 = f(x1)

and so on.

In general this polynomial is a quadratic xn+1 = xn2 + 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 xm and xn are congruent mod p by computing gcd(xm - xn, 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 x1, x2, x3 and so on by iterating the polynomial, and at the same time computing x2, x4, x6 and so on by iterating the polynomial twice. Then we compare xn against x2n to check for a coincidence.

Then we have to compute gcd(x1 - x2, N), gcd(x2 - x4, N), gcd(x3 - x6, 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((x1 - x2)(x2 - x4)(x3 - x6)(x4 - x8), N)
  • gcd((x5 - x10)(x6 - x12)(x7 - x14)(x8 - x16), 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 x2+1 and the initial point x0 = 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