Algoritme rho de Pollard (logaritmos discrets)

El algoritme rho de Pollard per al logaritmo discret és un algoritme publicat pel matemàtic John Pollard en 1978 que permet resoldre el problema del logaritmo discret en qualsevol grup.

L'idea per a este algoritme és similar a la que s'utilisa en un atre per a la factorización de sancers, publicat per Pollard en 1975 (algoritme rho de Pollard).

Existixen algoritmes d'orde subexponencial per al problema del logaritmo discret en ${\mathbb{Z}}_p^{*}$ (per eixemple, l'algoritme de càlcul d'índexs) i l'algoritme de Pollard no ho és, pese a lo que és útil en la pràctica per ser simple i efectiu per a grups menuts. Ademés té la ventaja de no utilisar res de l'estructura d'un grup particular.

L'algoritme

Siga $G$ un grup cíclico. L'algoritme té com a entrada dos elements $g,h\in G$ i com a eixida $x\in \mathbb{N}$ tal que $g^x=h$. Se supon conegut l'orde del grup, al que notarem n.

Es realisa una partició de G en tres subconjunts disjuntos, $G=S_1\cup S_2\cup S_3$, de manera que el neutre del grup no pertanyga a $S_2$, en $S_1,S_2,S_3$ aproximadament del mateix tamany. Es definix la successió $(x_k,a_k,b_k)$ en $G\times {\mathbb{Z}}_n\times {\mathbb{Z}}_n$ inductivamente:

$(x_0,a_0,b_0)=(e_G,0,0),(x_{k+1},a_{k+1},b_{k+1})=\{\begin{array}{cc}(h{x}_k,a_k,b_k+1)& \text{si }{x}_k\in S_1\\ (x_k^2,2a_k,2b_k)& \text{si }{x}_k\in S_2\\ (g{x}_k,a_k+1,b_k)& \text{si }{x}_k\in S_3\end{array}$

La successió està feta de forma tal que per a cada $k\in \mathbb{N}$ es té $x_k=g^{a_k}{h}^{b_k}$. L'objectiu de l'algoritme és trobar $l\ne t$ tals que $x_l=x_t$. En eixe cas tindrem $g^{a_l}{h}^{b_l}=g^{a_t}{h}^{b_t}$, d'a on $a_l-a_t=x(b_t-b_l)$ (mod n). Si $b_t-b_l$ és coprimo en n, podem d'ací deduir el valor de x.

Per a trobar $l\ne t$ tals que $x_l=x_t$ (que es denomina colisió) s'utilisa l'algoritme detector de cicles de Floyd (també conegut com l'algoritme de la llebre i la tortuga). Consistix en comparar x_i en x_2i.

Orde d'eixecució

Este és un algoritme que depenent de la "sòrt" que tingam pot demorar més o menys temps en eixecutar-se.

Hi ha dos coses que devem contar a l'hora d'estudiar el temps d'eixecució: el número de "evaluacions" (quants x_i calculem) i el de "comparacions" (quantes voltes veem si x_i=x_2i). Sempre el número d'evaluacions és el triple que el de comparacions. La memòria que utilisa l'algoritme és molt menuda, ya que solament es deuen guardar els valors de x_i i x_2i en cada pas.

Teske va realisar investigacions en les que prova empíricamente que el número esperat d'evaluacions és aproximadament $1,37\sqrt{n}$ per al cas en que el grup és ${\mathbb{Z}}_n^{*}$.