next up previous contents
Next: Et maintenant, extrayons ! Up: Extraction de racine carrée Previous: Méthode de Zassenhauss-Cantor

Méthode de Shanks

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

\begin{displaymath}
(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}}.\end{displaymath}

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 2k.

$\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 x2j=1 ;
Si j=k alors on s'arrête car u n'est donc pas un carré ;
tant que $j\not = 0$ (* ux=z2, Ord(a)=2h, Ord x=2j, j <h *)
(x,z,h,a) :=(x a2h-j,z a2h-j-1,j,a2h-j) ;
Calculer le plus petit j tel que x2j=1 ;
fin(tant que)
Retourner z ; (* x=1 et z est une racine carrée de u *)
FIN



Cyril Banderier
7/23/1997