Algoritme rho de Pollard (logaritmes discrets)

L'algoritme rho de Pollard per al logaritme discret és un algoritme publicat pel matemàtic John Pollard en 1978[1] que permet resoldre el problema del logaritme discret en qualsevol grup.

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

Existixen algoritmes d'orde subexponencial per al problema del logaritme discret en ℤ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.[2]

L'algoritme

Siga G un grup cíclico. L'algoritme té com a entrada dos elements g,h∈G i com a eixida x∈ℕ tal que gx=h. Se supon conegut l'orde del grup, al que notarem n.

Es realisa una partició de G en tres subconjunts disjunts, G=S1∪S2∪S3, de manera que el neutre del grup no pertanyga a S2, en S1,S2,S3 aproximadament del mateix tamany. Es definix la successió (xk,ak,bk) en G×ℤn×ℤn inductivamente:

(x0,a0,b0)=(eG,0,0),    (xk+1,ak+1,bk+1)={(hxk,ak,bk+1)si xk∈S1(xk2,2ak,2bk)si xk∈S2(gxk,ak+1,bk)si xk∈S3

La successió està feta de forma tal que per a cada k∈ℕ es té xk=gakhbk. L'objectiu de l'algoritme és trobar l≠t tals que xl=xt. En eixe cas tindrem galhbl=gathbt, d'a on al−at=x(bt−bl) (mod n). Si bt−bl és coprimo en n, podem d'ací deduir el valor de x.

Per a trobar l≠t tals que xl=xt (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 xi en x2i.

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 xi calculem) i el de "comparacions" (quantes voltes veem si xi=x2i). 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 xi i x2i en cada pas.

Teske va realisar investigacions en les que prova empíricament que el número esperat d'evaluacions és aproximadament 1,37n per al cas en que el grup és ℤn*.[3]

Referències

  1. ↑ Pollard, John(1978).«Monte Carlo methods for index computation (mod p)».Mathematics of Computation.32(143): 918-924.ISSN 00255718.doi:10.2307/2006496.Consultat el 31 d'octubre de 2015.
  2. ↑ (2008).«On the Efficiency of Pollard’s Rho Method for Discrete Logarithms».Conferences in Research and Practice in Information Technology.77: 125-131.Consultat el 1 de novembre de 2015.
  3. ↑ Erro en la seqüencia d'órdens: no existix el mòdul «Citas».