Algorithme du lièvre et de la tortue

La suite dessinée ressemble à la lettre grecque rho.

Soit ${\displaystyle f\colon S\rightarrow S}$ une fonction, et S un ensemble fini de cardinal n. On considère la suite ${\displaystyle (a_{i})}$ définie par ${\displaystyle a_{0}\in S}$ et ${\displaystyle a_{i+1}=f(a_{i})}$. Cette suite possède un cycle, car le nombre de ses valeurs possibles est majoré par n. Knuth dit que la suite est ultimement périodique[1] , cela signifie que les valeurs

a₀, a₁, … a_λ, … a_λ+μ-1

sont distinctes et a_n+μ = a_n pour tout n ≥ λ (μ est la longueur du cycle et λ le nombre d'éléments à l'extérieur du cycle).

La suite dessinée ressemble à la lettre grecque ρ, comme montré sur la figure ci-contre. Si l'on parvient à trouver deux indices i < j avec ${\displaystyle a_{i}=a_{j}}$ alors j-i est un multiple de la longueur du cycle[2].

L'algorithme de Floyd de détection de cycle repose sur la propriété suivante : si la suite admet un cycle, alors il existe un indice m avec ${\displaystyle a_{m}=a_{2m}}$ et λ ≤ m ≤ λ+μ. Ainsi, l'algorithme consiste à parcourir la séquence simultanément à deux vitesses différentes : à vitesse 1 pour la tortue et à vitesse 2 pour le lièvre. Autrement dit, l'algorithme inspecte les couples[2] :

(a₁, a₂), (a₂, a₄), (a₃, a₆), (a₄, a₈), etc.

L'algorithme trouve le premier indice m tel que ${\displaystyle a_{m}=a_{2m}}$. Dès lors, ${\displaystyle 2m-m=m}$ est un multiple de la longueur du cycle μ.

Pour déterminer la valeur exacte de μ, il suffit de refaire tourner l'algorithme à partir de m+1, jusqu'à trouver un autre nombre ${\displaystyle m_{1}}$ tel que ${\displaystyle a_{m_{1}}=a_{2{m_{1}}}}$. Dès lors on a d'une part ${\displaystyle m_{1}\leq m+\mu }$ (car on retombe alors sur ${\displaystyle a_{m}}$) et d'autre part μ qui divise ${\displaystyle m_{1}-m}$ (car il divise ${\displaystyle m}$ et ${\displaystyle m_{1}}$), donc ${\displaystyle \mu =m_{1}-m}$.

Exemple

La séquence démarre en bas, monte et emprunte le cycle dans le sens des aiguilles d'une montre (voir figure). Suivant l'algorithme de Floyd, les deux parcours se rencontrent en ${\displaystyle a_{6}}$ après 6 itérations. Un deuxième tour de l'algorithme amène les deux parcours à se rencontrer après 6 nouvelles itérations, d'où la valeur ${\displaystyle \mu =6}$.

Parcours	${\displaystyle t_{1}}$	${\displaystyle t_{2}}$	${\displaystyle t_{3}}$	${\displaystyle t_{4}}$	${\displaystyle t_{5}}$	${\displaystyle t_{6}}$	${\displaystyle t_{7}}$	${\displaystyle t_{8}}$	${\displaystyle t_{9}}$	${\displaystyle t_{10}}$	${\displaystyle t_{11}}$	${\displaystyle t_{12}}$
Lent (tortue)	${\displaystyle a_{1}}$	${\displaystyle a_{2}}$	${\displaystyle a_{3}}$	${\displaystyle a_{4}}$	${\displaystyle a_{5}}$	${\displaystyle a_{6}}$	${\displaystyle a_{7}}$	${\displaystyle a_{2}}$	${\displaystyle a_{3}}$	${\displaystyle a_{4}}$	${\displaystyle a_{5}}$	${\displaystyle a_{6}}$
Rapide (lièvre)	${\displaystyle a_{2}}$	${\displaystyle a_{4}}$	${\displaystyle a_{6}}$	${\displaystyle a_{2}}$	${\displaystyle a_{4}}$	${\displaystyle a_{6}}$	${\displaystyle a_{2}}$	${\displaystyle a_{4}}$	${\displaystyle a_{6}}$	${\displaystyle a_{2}}$	${\displaystyle a_{4}}$	${\displaystyle a_{6}}$

Brent a amélioré l'algorithme du lièvre et de la tortue[5]. Il prétend qu'il est 36% plus rapide que l'algorithme du lièvre et de la tortue classique. Il améliore l'algorithme rho de Pollard de 24%.

entrée : une fonction f, valeur initiale a0
sortie : la longueur du cycle, et le nombre d'éléments avant d'atteindre le cycle
brent(f, a0)
    puissance = lam = 1
    tortue = a0
    lièvre = f(a0)
    while tortue != lièvre:
        if puissance == lam:  # on passe à la puissance de deux suivante
            tortue = lièvre
            puissance *= 2
            lam = 0
        lièvre = f(lièvre)
        lam += 1
    # on trouve ici l'indice de la première répétition de longueur λ
    tortue = lièvre = a0
    pour i = 0 à lam-1
            lièvre = f(lièvre)
    # la distance entre le lièvre et la tortue est λ.
    # Maintenant, le lièvre et la tortue bougent à la même vitesse jusqu'à être d'accord
    mu = 0
    tant que tortue != lièvre:
        tortue = f(tortue)
        lièvre = f(lièvre)
        mu += 1
    retourner lam, mu

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Floyd's cycle-finding algorithm » (voir la liste des auteurs).

• (en) Antoine Joux, Algorithmic Cryptanalysis, CRC Press, 2009, 520 p. (ISBN 978-1-4200-7003-3, présentation en ligne), p. 223-242.