\documentclass[a4paper,12pt]{amsart}
\usepackage{kb,kbexo,a4wide}
\course{Préparation à l'agrégation}

\author{Karim Belabas}
\begin{document}
\simpletitle{Algorithmes de détection de cycles}

\section{Le lièvre et la tortue}
Soit $E$ un ensemble fini à $p$ éléments et une fonction $f\colon E\to E$.
On considère une suite $(x_n)\in E^\NM$ définie par $x_0$ et la relation de
récurrence $x_{n+1} = f(x_n)$, $n \geq 0$. Elle est ultimement périodique
puisqu'il existe $i\neq j\leq p$ tels que $x_i = x_j$ (principe des
tiroirs : il y a $p+1$ indices et $p$ valeurs possibles), d'où il suit que
$x_{i+s} = x_{j+s}$ pour tout $s \geq 0$. Si $i < j$ sont les deux indices
minimaux tels que $x_i = x_j$, $P := i$ est la prépériode et $T := j - i$ la
période de la suite.

Un algorithme naïf pour détecter une telle collision examine les paires
$(x_i,x_j)$ pour $j = 1, 2, \dots$ et $0\leq i < j$ et s'arrête à la première
collision, c'est-à-dire quand $j = T+P$ et $i = P$. Il utilise donc
$O((T+P)^2) = O(p^2)$ comparaisons et stocke $T+P = O(p)$ élément de la
suite. Le lemme suivant permet un algorithme en $O(T+P) = O(p)$, et ne stocke
que $2$ éléments:

\begin{lemme*}
Soient $0\leq i < j$ les indices minimaux tels que $x_i = x_j$.
Il existe $0 < k \leq j$ tel que $x_k = x_{2k}$.
\end{lemme*}
\begin{proof}
On pose $T = j - i$ (période). Pour tout $\lambda\geq 0$ et $s\geq 0$
entiers, on a 
$$x_{i + s} = x_{j + \lambda T + s} \;;$$
on veut poser $k = i+s$ et $2k = j + \lambda T + s$, pour un $s\geq 0$ le
plus petit possible. Il faut donc choisir $s$ et $\lambda$ tels
que $2(i+s) = j + \lambda T + s$, soit $s = j - 2i + \lambda  T$.
\begin{itemize}
\item Si $j \geq 2i$, on peut choisir $\lambda = 0$ et on a bien $s = j - 2i
\geq 0$ et $k = j-i\leq j$.

\item Sinon, le $s\geq 0$ minimal est le reste de la division euclidienne de
$j - 2i < 0$ par $T$ : il est strictement inférieur à $T$, et le
quotient $-\lambda$ est bien négatif. On trouve $k = s + i < T+i = j$.
\end{itemize}
On remarque qu'on a bien $k > 0$ (sinon $i = j = 0$).
\end{proof}

Il suffit donc de considérer les paires $(x_k, x_{2k})$ pour $k = 1, 2,
\dots$ jusqu'à obtenir une collision. L'algorithme s'arrête après au plus
$T+P$ valeurs. La preuve du lemme montre qu'on peut choisir $k < j$ sauf
si $i = 0$ (prépériode nulle). Dans ce dernier cas, $j = T$ et $x_0 = x_T$
est la première collision; l'équation $x_k = x_{2k}$ est équivalente à $T
\mid 2k - k = k$  donc le plus petit $k$ possible est $T$ et le lemme est
optimal pour ce cas.

On appelle souvent cette méthode «l'algorithme du lièvre et de la tortue»,
le lièvre parcourant la suite deux fois plus vite que la tortue, jusqu'à la
rattraper contrairement à celui de la fable. Elle apparaît dans la
littérature à la fin des années 1960s (en 1969, Donald Knuth l'attribue à
Robert Floyd, mais sans doute à tort; c'est un algorithme du folklore).

\section{Un autre algorithme}

Il utilise une variante du lemme ci-dessus, qui repose sur un principe
différent : il s'agit de déterminer la plus petite puissance de $2$
supérieure à $P$ et $T$.
\begin{lemme*}
Si $2^j > \max(P,T)$, alors $x_{2^j-1} = x_{2^j+i}$ pour un indice
$0\leq i < 2^j$.
\end{lemme*}
\begin{proof}
Comme $2^j-1 \geq P$, on a $x_{2^j-1} = x_{2^j-1+T}$. On pose
$i = T-1 < 2^j$.
\end{proof}
L'algorithme est maintenant le suivant:
\begin{itemize}
\item Soit $y \leftarrow x_0$ et $z\leftarrow y$.
\item Pour $j = 0, 1, \dots$ (ici, $y$ vaut $x_{2^j-1}$)
  \begin{itemize}
  \item Pour $i = 0, 1, \dots, 2^j-1$: 
  \begin{itemize}
      \item $z \leftarrow f(z)$ ($= x_{2^j+i}$).
      \item si $z = y$, afficher $(2^j-1, 2^j+i)$ et stopper.
  \end{itemize}
  \item $y \leftarrow z$
  \end{itemize}
\end{itemize}
Pour $j = 1, 2, ...$, on compare $x_{2^j-1}$ à $x_{2^j+i}$ pour $0 \leq i <
2^j$. Remarquons que la dernière valeur de $2^j+i$ dans la boucle intérieure,
pour $i = 2^j-1$, vaut $2^{j+1}-1$ qui est la prochaine valeur de référence à
comparer avec les valeurs suivantes de la suite. Ainsi, on ne calcule jamais
deux fois le même $x_k$ ! L'algorithme s'arrête quand $2^j$ est la plus
petite puissance de $2$ qui soit $> \max(P,T)$, pour l'indice $i$ du lemme.

C'est de nouveau un algorithme utilisant $O(P+T)$ comparaisons et ne stockant
que $2$ éléments de la liste. On peut montrer qu'il ne calcule jamais plus
d'éléments de la suite que l'algorithme du lièvre et de la tortue. Cet
algorithme est dû à Richard Brent. D'autres variantes utilisent plus de
mémoire pour déterminer exactement période et prépériode (en gagnant au
mieux un facteur constant sur le temps).

\section{Application à la factorisation des entiers}
Soit $N > 0$ l'entier qu'on désire factoriser et soit $p \mid N$ un diviseur
strict de~$N$, par exemple le plus petit diviseur premier de $N$ ($p$ est
inconnu). On choisit une fonction $f\colon \ZM/N\ZM\to \ZM/N\ZM$ polynomiale,
par exemple $f(x) = x^2+1$ et un $X_0\in\ZM/N\ZM$ et on considère la suite
définie par la récurrence $X_{n+1} = f(X_n)$. La projection canonique
$\ZM/N\ZM\to\ZM/p\ZM$ permet de définir $x_n = X_n\mod p$ (on sait calculer
les $X_n$ mais pas les $x_n$). Motivés par le paradoxe des anniversaires on
\emph{espère} que la suite $x_n$ a une période $T$ et une prépériode $P$
qui sont toutes deux~$O(\sqrt{p})$.

Dans ce cas, on applique l'un ou l'autre algorithme à la suite des $X_n$,
en remplaçant le test $x_i = x_j$ dans $\ZM/p\ZM$ ($p$ étant inconnu, on ne
sait pas le faire) par le test $\pgcd(X_i - X_j, N) > 1$ (si $x_i = x_j$,
alors $p$ divise ce pgcd). On \emph{espère} que ce pgcd ne vaut pas $N$,
auquel cas on a factorisé $N$!
\end{document}
