Algorisme cangur de Pollard

En teoria computacional de nombres i àlgebra computacional, l'algoritme cangur de Pollard (també l'algoritme lambda de Pollard, vegeu Naming a continuació) és un algorisme per resoldre el problema del logaritme discret. L'algorisme va ser introduït l'any 1978 pel teòric dels nombres John M. Pollard, en el mateix article que el seu més conegut algorisme rho de Pollard per resoldre el mateix problema. Tot i que Pollard va descriure l'aplicació del seu algorisme al problema del logaritme discret en el grup multiplicatiu d'unitats mòdul un p primer, de fet és un algorisme genèric de logaritme discret: funcionarà en qualsevol grup cíclic finit.^[1][2]

Suposem ${\displaystyle G}$ és un grup cíclic finit d'ordre ${\displaystyle n}$ que és generada per l'element ${\displaystyle \alpha }$, i busquem trobar el logaritme discret ${\displaystyle x}$ de l'element ${\displaystyle \beta }$ a la base ${\displaystyle \alpha }$. En altres paraules, un busca ${\displaystyle x\in Z_{n}}$ de tal manera que ${\displaystyle \alpha ^{x}=\beta }$. L'algorisme lambda permet cercar ${\displaystyle x}$ en algun interval ${\displaystyle [a,\ldots ,b]\subset Z_{n}}$. Es pot cercar tot el rang de possibles logaritmes mitjançant la configuració ${\displaystyle a=0}$ i ${\displaystyle b=n-1}$.^[3]

1. Trieu un conjunt ${\displaystyle S}$ de nombres enters positius de mitjana aproximadament ${\displaystyle {\sqrt {b-a}}}$ i definir un mapa pseudoaleatori ${\displaystyle f:G\rightarrow S}$.

2. Trieu un nombre enter ${\displaystyle N}$ i calcular una seqüència d'elements de grup ${\displaystyle \{x_{0},x_{1},\ldots ,x_{N}\}}$ d'acord amb: ^[4]

${\displaystyle x_{0}=\alpha ^{b}\,}$

${\displaystyle x_{i+1}=x_{i}\alpha ^{f(x_{i})}{\text{ per }}i=0,1,\ldots ,N-1}$

3. Calcular

${\displaystyle d=\sum _{i=0}^{N-1}f(x_{i}).}$

Observeu que:

${\displaystyle x_{N}=x_{0}\alpha ^{d}=\alpha ^{b+d}\,.}$

4. Comenceu a calcular una segona seqüència d'elements de grup ${\displaystyle \{y_{0},y_{1},\ldots \}}$ d'acord amb:

${\displaystyle y_{0}=\beta \,}$

${\displaystyle y_{i+1}=y_{i}\alpha ^{f(y_{i})}{\text{ for }}i=0,1,\ldots ,N-1}$

i una seqüència de nombres enters corresponent ${\displaystyle \{d_{0},d_{1},\ldots \}}$ d'acord amb:

${\displaystyle d_{n}=\sum _{i=0}^{n-1}f(y_{i})}$

Observeu que:

${\displaystyle y_{i}=y_{0}\alpha ^{d_{i}}=\beta \alpha ^{d_{i}}{\mbox{ per }}i=0,1,\ldots ,N-1}$

5. Deixeu de calcular els termes de ${\displaystyle \{y_{i}\}}$ i ${\displaystyle \{d_{i}\}}$ quan es compleix alguna de les condicions següents:

A) ${\displaystyle y_{j}=x_{N}}$ per a alguns ${\displaystyle j}$. Si les seqüències ${\displaystyle \{x_{i}\}}$ i ${\displaystyle \{y_{j}\}}$ "xocar" d'aquesta manera, llavors tenim:

${\displaystyle x_{N}=y_{j}\Rightarrow \alpha ^{b+d}=\beta \alpha ^{d_{j}}\Rightarrow \beta =\alpha ^{b+d-d_{j}}\Rightarrow x\equiv b+d-d_{j}{\pmod {n}}}$

i així hem acabat.

B). ${\displaystyle d_{i}>b-a+d}$ Si això passa, l'algoritme no ha pogut trobar. Els intents posteriors es poden fer canviant l'elecció de ${\displaystyle S}$ i/o ${\displaystyle f}$.