Algoritme rho de Pollard

El algoritme rho de Pollard és un algoritme especialisat de factorización d'número entero. Va ser inventat per John Pollard en 1975. És especialment efectiu a l'hora de factorizar número compuesto que tinguen factors menuts.

Idees principals

L'algoritme rho es basa en l'algoritme de la llebre i la tortuga i en l'observació de que (com ocorre en el problema del natalici) dos números x i i són congruents mòdul p en provabilitat 0,5 despuix d'haver-se elegit aleatoriamente $1,177\sqrt{p}$ números. Si p és factor de n, el número que es vol factorizar, llavors $1<\mathrm{mcd}(|x-y|,n)\le n$, ya que p dividix tant a $|x-y|$ com a n.

L'algoritme rho ampra puix una funció mòdul n a modo de generador d'una seqüència pseudoaleatoria. Fa funcionar una de les seqüències el doble de ràpit que l'atra, és dir, per cada iteración d'una de les còpies de la seqüència, l'atra fa dos iteraciones. Siga x l'estat actual d'una seqüència i i l'estat actual de l'atra. En cada pas es pren el màxim comú divisor (MCD) de |x − i| i n. Si este MCD aplega a ser n, llavors finalisa l'algoritme en el resultat de fracàs, ya que açò significa que x = i i, per l'algoritme de la llebre i la tortuga, la seqüència ya ha completat el seu cicle i seguir més allà només conseguiria repetir treball ya realisat.

L'algoritme

Entrades: n, el número que es desija factorizar; i f(x), una funció pseudoaleatoria mòdul n

Eixides: un factor no trivial de n, o be un fracàs. (un factor trivial de n és n mateix o 1)

1. x ← 2, i ← 2; d ← 1
2. Mentres d = 1:
   1. x ← f(x)
   2. i ← f(f(i))
   3. d ← MCD(|x − i|, n)
3. Si d = n, torna fracàs.
4. De lo contrari, torna d.

Note's que este algoritme acabarà en fracàs per a tot n primer, pero també pot fallar per a un n compost. En eixe cas, es canvia la funció f(x) i s'intenta de nou.

Referències

• J.M. Pollard. "A Mont Carlo method for factorization", BIT Numerical Mathematics 15(3), 1975, pp. 331-334.
• Richard P. Brent. An Improved Monte Carlo Factorization Algorithm, BIT 20, 1980, pp.176-184, https://web.archive.org/web/20090924082516/http://wwwmaths.anu.edu.au/brent/pd/rpb051i.pdf
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Segona edició. MIT Press i McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.9: Integer factorization, pp.896–901 (esta secció només versa sobre l'algoritme rho de Pollard).