Content deleted Content added
No edit summary |
|||
Line 5:
== Core ideas ==
The algorithm is used to factorize a number <math>n = pq</math>, where <math>p</math> is a non-trivial factor. A [[polynomial]] modulo <math>n</math>, called <math>g(x)</math> (e.g., <math>g(x) = (x^2 + 1) \bmod n</math>), is used to generate a [[pseudorandom sequence]]. It is important to note that <math>g(x)</math> must be a polynomial. A starting value, say 2, is chosen, and the sequence continues as <math>x_1 = g(2)</math>, <math>x_2 = g(g(2))</math>, <math>x_3 = g(g(g(2)))</math>, etc. The sequence is related to another sequence <math>\{x_k \bmod p\}</math>. Since <math>p</math> is not known beforehand, this sequence cannot be explicitly computed in the algorithm. Yet
Because the number of possible values for these sequences is finite, both the <math>\{x_k\}</math> sequence, which is mod <math>n</math>, and <math>\{x_k \bmod p\}</math> sequence will eventually repeat, even though these values are unknown. If the sequences were to behave like random numbers, the [[birthday paradox]] implies that the number of <math>x_k</math> before a repetition occurs would be expected to be <math>O(\sqrt N)</math>, where <math>N</math> is the number of possible values. So the sequence <math>\{x_k \bmod p\}</math> will likely repeat much earlier than the sequence <math>\{x_k\}</math>. When one has found a <math>k_1,k_2</math> such that <math>x_{k_1}\neq x_{k_2}</math> but <math>x_{k_1}\equiv x_{k_2}\bmod p</math>, the number <math>|x_{k_1}-x_{k_2}|</math> is a multiple of <math>p</math>, so <math>p</math> has been found.
| |||