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.

Algorisme

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

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

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

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

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

3. Calcular

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

Observeu que:

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

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

$y_{0}=\beta \,$

$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 $\{d_{0},d_{1},\ldots \}$ d'acord amb:

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

Observeu que:

$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 $\{y_{i}\}$ i $\{d_{i}\}$ quan es compleix alguna de les condicions següents:

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

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