next up previous contents
Next: Réciprocité et tests de Up: Extraction de racine carrée Previous: Méthode de Shanks

Et maintenant, extrayons !

Nous allons calculer une racine carrée de x0=160 dans ${\mathbb Z}/641{\mathbb Z}$avec la méthode Shanks. On a p=641=5.27+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 x124=1. On vérifie que x1 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 x222=1. On vérifie que x2 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$.



Cyril Banderier
7/23/1997