Méthode de Shanks

On écrit toujours $\char93 {\mathbb K}-1= 2^k q$ avec q impair. Or

$$(u^\frac{q+1} {2})^2=u.u^q \Longleftrightarrow u=(u^\frac{q+... ...ongleftrightarrow \sqrt{u}= u^\frac{q+1}{2} \sqrt{(u^q)^{-1}}.$$

Pour trouver la racine carrée de u, on est donc ramené, d'après la formule magique ci-dessus, à élaborer un algorithme d'extraction de racine carrée de u^-q qui est élément d'un sous-groupe ${\mathbb G}$ cyclique, d'ordre 2^k.

$\omega$ étant un générateur de ${\mathbb G}$, voici l'algorithme :

DEBUT
($x,z,h,a)~:=(u^q,u^\frac{q+1}{2},k,\omega$) ;
On calcule le plus petit j tel que x^2j=1 ;
Si j=k alors on s'arrête car u n'est donc pas un carré ;
tant que $j\not = 0$ (* ux=z², Ord(a)=2^h, Ord x=2^j, j <h *)
(x,z,h,a) :=(x a^2h-j,z a^2h-j-1,j,a^2h-j) ;
Calculer le plus petit j tel que x^2j=1 ;
fin(tant que)
Retourner z ; (* x=1 et z est une racine carrée de u *)
FIN