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

Difference between revisions of "Rho factorization method"

From Prime-Wiki
Jump to: navigation, search
(restored)
 
(Math markup and links)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
The '''Rho factorization method''' was invented by John Pollard in 1974.
+
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.
 
The idea is to create a sequence iterating a polynomial modulo the number to be factored.
  
 
So the sequence will be:
 
So the sequence will be:
*x<sub>0</sub>
+
*<math>x_0</math>
*x<sub>1</sub> = f(x<sub>0</sub>)
+
*<math>x_1 = f(x_0)</math>
*x<sub>2</sub> = f(x<sub>1</sub>)
+
*<math>x_2 = f(x_1)</math>
 
and so on.
 
and so on.
  
In general this polynomial is a quadratic x<sub>n+1</sub> = x<sub>n</sub><sup>2</sup> + a, where a <math>\neq </math>-2.
+
In general this polynomial is a quadratic <math>x_{n+1} = x_n^2 + a</math>, where <math>a \neq -2</math>.
  
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>\sqrt N</math> different values.
+
There are <math>N</math> values <math>\!\bmod N</math>, so the sequence cannot have more than <math>N</math> distinct values. It can be shown that in average the sequence will have about <math>\sqrt{N}</math> different values.
  
When N = pq where p and q are [[coprime]] but not necessarily [[Prime number|prime]], we will see that after about <math>\sqrt p</math> elements the sequence will start repeating mod p.
+
When <math>N = pq</math> where <math>p</math> and <math>q</math> are [[coprime]] but not necessarily [[prime]], we will see that after about <math>\sqrt{p}</math> elements the sequence will start repeating <math>\!\bmod p</math>.
  
We can detect if two elements of the sequence x<sub>m</sub> and x<sub>n</sub> are congruent mod p by computing [[Greatest common divisor|gcd]](x<sub>m</sub> - x<sub>n</sub>, N) which will reveal the unknown factor p.
+
We can detect if two elements of the sequence <math>x_m</math> and <math>x_n</math> are congruent <math>\!\bmod p</math> by computing the [[greatest common divisor]] (<math>\gcd(x_m - x_n, N)</math>) which will reveal the unknown factor <math>p</math>.
  
 
So what we need is to detect the sequence repetition.
 
So what we need is to detect the sequence repetition.
  
There is a method invented by Floyd that consists in computing x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub> and so on by iterating the polynomial, and at the same time computing x<sub>2</sub>, x<sub>4</sub>, x<sub>6</sub> and so on by iterating the polynomial twice. Then we compare x<sub>n</sub> against x<sub>2n</sub> to check for a coincidence.
+
There is a method invented by Floyd that consists in computing <math>x_1</math>, <math>x_2</math>, <math>x_3</math> and so on by iterating the polynomial, and at the same time computing <math>x_2</math>, <math>x_4</math>, <math>x_6</math> and so on by iterating the polynomial twice. Then we compare <math>x_n</math> against <math>x_{2n}</math> to check for a coincidence.
  
Then we have to compute gcd(x<sub>1</sub> - x<sub>2</sub>, N), gcd(x<sub>2</sub> - x<sub>4</sub>, N), gcd(x<sub>3</sub> - x<sub>6</sub>, N), and so on until we find a proper factor of N.
+
Then we have to compute <math>\gcd(x_1 - x_2, N)</math>, <math>\gcd(x_2 - x_4, N)</math>, <math>\gcd(x_3 - x_6, N)</math>, and so on until we find a proper factor of <math>N</math>.
  
Since computing gcd are expensive, we can trade most of the gcds by multiplications. For example we can compute in batches of four elements:
+
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:
*gcd((x<sub>1</sub> - x<sub>2</sub>)(x<sub>2</sub> - x<sub>4</sub>)(x<sub>3</sub> - x<sub>6</sub>)(x<sub>4</sub> - x<sub>8</sub>), N)
+
*<math>\gcd((x_1 - x_2)(x_2 - x_4)(x_3 - x_6)(x_4 - x_8), N)</math>
*gcd((x<sub>5</sub> - x<sub>10</sub>)(x<sub>6</sub> - x<sub>12</sub>)(x<sub>7</sub> - x<sub>14</sub>)(x<sub>8</sub> - x<sub>16</sub>), N)
+
*<math>\gcd((x_5 - x_{10})(x_6 - x_{12})(x_7 - x_{14})(x_8 - x_{16}), N)</math>
 
and so on.
 
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]].
+
A method that requires less modular multiplications was invented by [[Richard Brent]] in 1980 who used it to factor the eighth [[Fermat number]].
  
 
===Example===
 
===Example===
Suppose we want to factor the number 9271 using the polynomial x<sup>2</sup>+1 and the initial point x<sub>0</sub> = 5. All multiplications are done modulo 9271.
+
Suppose we want to factor the number 9271 using the polynomial <math>x^2 + 1</math> and the initial point <math>x_0 = 5</math>. All multiplications are done modulo 9271.
  
 
Step 1:
 
Step 1:
Line 37: Line 37:
 
:<math>x_2 = x_1^2 + 1 = 677</math>
 
:<math>x_2 = x_1^2 + 1 = 677</math>
  
Step 2: <math>(x_2,\, x_4) = (677,\, 932)</math>
+
Step 2: <math>(x_2, x_4) = (677, 932)</math>
  
Step 3: <math>(x_3,\, x_6) = (4051,\, 4677)</math>
+
Step 3: <math>(x_3, x_6) = (4051, 4677)</math>
  
Step 4: <math>(x_4,\, x_8) = (932,\, 3451)</math>
+
Step 4: <math>(x_4, x_8) = (932, 3451)</math>
  
Batch gcd: <math>gcd((26-677)(677-932)(4051-4677)(932-3451),\,9271) = 1</math>. We have to continue.
+
Batch gcd: <math>\gcd((26-677)(677-932)(4051-4677)(932-3451), 9271) = 1</math>. We have to continue.
  
Step 5: <math>(x_5,\, x_{10}) = (6422,\, 6626)</math>
+
Step 5: <math>(x_5, x_{10}) = (6422, 6626)</math>
  
Step 6: <math>(x_6,\, x_{12}) = (4677,\, 5991)</math>
+
Step 6: <math>(x_6, x_{12}) = (4677, 5991)</math>
  
Step 7: <math>(x_7,\, x_{14}) = (4041,\, 3451)</math>
+
Step 7: <math>(x_7, x_{14}) = (4041, 3451)</math>
  
Step 8: <math>(x_8,\, x_{16}) = (3451,\, 6626)</math>
+
Step 8: <math>(x_8, x_{16}) = (3451, 6626)</math>
  
Batch gcd: <math>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.
+
Batch gcd: <math>\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>gcd(x_5 - x_{10},\, N) = gcd(6422-6626,\, 9271) = 1</math>
+
<math>\gcd(x_5 - x_{10}, N) = \gcd(6422-6626, 9271) = 1</math>
  
<math>gcd(x_6 - x_{12},\, N) = gcd(4677-5991,\, 9271) = 73</math>
+
<math>\gcd(x_6 - x_{12}, N) = \gcd(4677-5991, 9271) = 73</math>
  
 
So 73 is a proper factor of 9271.
 
So 73 is a proper factor of 9271.
  
 
==External links==
 
==External links==
*[https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm Wikipedia]
+
*[[Wikipedia:Pollard's rho algorithm|Wikipedia]]
 
[[Category:Factorization]]
 
[[Category:Factorization]]

Latest revision as of 22:51, 23 July 2024

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