Et maintenant, extrayons !

Nous allons calculer une racine carrée de x₀=160 dans ${\mathbb Z}/641{\mathbb Z}$avec la méthode Shanks. On a p=641=5.2⁷+1, i.e. q=5, k=7 et on peut vérifier que $\omega=21$ est un générateur de ${\mathbb G}$.
$x_0^{2^4}=-1 \Longrightarrow (x_0 \omega^{2^2})^{2^4}= x_0^{2^4} \times \omega^{2^6}=(-1)\times(-1)=1$
On pose $x_1=x_0 \omega^{2^2}=256$, si bien que x₁²⁴=1. On vérifie que x₁ est d'ordre 8, d'où :
$x_1^{2^2}=-1 \Longrightarrow (x_1 \omega^{2^4})^{2^2}= x_1^{2^2} \times \omega^{2^6}=(-1)\times(-1)=1$
On pose $x_2=x_1 \omega^{2^4}=487$, si bien que x₂²²=1. On vérifie que x₂ est d'ordre 4, d'où :
$x_2^2=-1 \Longrightarrow (x_2 \omega^{2^5})^2= x_2^2 \times \omega^{2^6}=(-1)\times(-1)=1$
Et on s'arrête car $x_3=x_2 \omega^{2^5}=1=x_1 \omega^{2^4}\omega^{2^5} =x_0\omega^{2^2}\omega^{2^4}\omega^{2^5} =x_0 \omega^{52}$,si bien que $x_0=(x_0 \omega^{26})^2$ i.e. $\sqrt{x_0}=160 \times 308=564$.