Algorithme rho de Pollard (logarithme discret)
# Algorithme rho de Pollard (logarithme discret)

L'algorithme rho de Pollard a été introduit par John M. Pollard en 1978 pour résoudre le problème du logarithme discret. Il est analogue à l'algorithme rho de Pollard que le même auteur avait introduit pour résoudre le problème factorisation entière.

## Principe

Considérons un groupe cyclique $G$ d'ordre $n$ engendré par $\alpha$. Le but est de calculer $\gamma$ tel que $\alpha ^{\gamma }=\beta$, où $\beta$ appartient à $G$. L'algorithme cherche des entiers $a$, $b$, $A$, et $B$ tels que $\alpha ^{a}\beta ^{b}=\alpha ^{A}\beta ^{B}$. Une fois de tel entier trouvé, l'inconnue $\gamma$ est l'une des solutions de l'équation $(B-b)\gamma =(a-A){\pmod {n}}$, autrement dit $\gamma =(B-b)^{-1}(a-A){\pmod {n}}$, où $(B-b)^{-1}$est l'inverse modulaire de $(B-b)$.

Pour trouver les entiers $a$, $b$, $A$, et $B$ l'algorithme utilise l'algorithme du lièvre et de la tortue pour trouver un cycle dans les séquences $x_{i}=\alpha ^{a_{i}}\beta ^{b_{i}}$. Autrement dit les entiers $a$, $b$ sont des valeurs prises par $a_{i}$, $b_{i}$ et les entiers $A$ et $B$ sont les valeurs prises par $a_{2i}$, $b_{2i}$.

On définit la suite $(x_{i})_{i\in \mathbb {N} }$ par $x_{i+1}=f(x_{i})$ où $f$ est une fonction supposée pseudo-aléatoire : ainsi on a des chances d'entrer dans une boucle de longueur approximative ${\sqrt {\frac {\pi n}{8}}}$ après ${\sqrt {\frac {\pi n}{8}}}$ étapes. Un moyen de définir une telle fonction est d'utiliser les règles suivantes : diviser $G$ en trois sous-ensembles disjoints de tailles approximativement égales : $S_{0}$, $S_{1}$, et $S_{2}$. Si $x_{i}$ appartient à $S_{0}$ alors multiplier par deux $a$ et $b$ ; si $x_{i}\in S_{1}$ alors incrémenter $a$, si $x_{i}\in S_{2}$ alors incrémenter $b$.

## Algorithme

Soit G un groupe cyclique d'ordre n. Soient $\alpha ,\beta \in G$. Soit une partition $G=S_{0}\cup S_{1}\cup S_{2}$.

Soit une fonction $f:G\to G$ définie par

    $f(x)={\begin{cases}\beta x&x\in S_{0}\\x^{2}&x\in S_{1}\\\alpha x&x\in S_{2}\end{cases}}$

et soient enfin les deux fonctions $g:G\times \mathbb {Z} \to \mathbb {Z}$ et $h:G\times \mathbb {Z} \to \mathbb {Z}$ définies par

    ${\begin{aligned}g(x,a)&={\begin{cases}a&x\in S_{0}\\2a\ ({\bmod {\ }}n)&x\in S_{1}\\a+1\ ({\bmod {\ }}n)&x\in S_{2}\end{cases}}\\h(x,b)&={\begin{cases}b+1\ ({\bmod {\ }}n)&x\in S_{0}\\2b\ ({\bmod {\ }}n)&x\in S_{1}\\b&x\in S_{2}\end{cases}}\end{aligned}}$

La fonction g (respectivement h) permet de calculer les valeurs $a_i$ (respectivement $b_i).$ L'algorithme est le suivant :

## Exemple

Considérons par exemple le groupe engendré par 2 modulo $N=1019$ (l'ordre du groupe est $n=1018$). L'algorithme est implémenté par le programme suivant écrit en C++ :

Les résultats sont les suivants (édités):

Ce qui donne $2^{681}5^{378}=1010=2^{301}5^{416}{\pmod {1019}}$ et ainsi $(416-378)\gamma =681-301{\pmod {1018}}$, pour lequel $\gamma _{1}=10$ est une solution comme on l'avait prévu. Comme $n=1018$ n'est pas premier, il y a une autre solution $\gamma _{2}=519$, pour laquelle $2^{519}=1014=-5{\pmod {1019}}$ convient.

## Complexité

Le temps d'exécution moyen est en ${\mathcal {O}}({\sqrt {n}})$. Si cet algorithme est utilisé avec l'algorithme de Pohlig-Hellman, le temps d'exécution des deux algorithmes combinés est en ${\mathcal {O}}({\sqrt {p}})$, où $p$ est le plus grand facteur premier de $n$.

