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

Méthode de Zassenhauss-Cantor

En voici l'algorithme, sachant que $\char93 {\mathbb K}-1= 2^k q$ avec q impair et que la norme est définie par

\begin{displaymath}
N(a+b\overline{X})=(a+b\overline{X})(a+b\overline{X})^\sigma=a^2- ub^2.\end{displaymath}

DEBUT
répéter
choisir ``au hasard'' $t \in {\mathbb K}$ ;
$y~:=t+\overline{X}$ ;
si N(y)=0 alors retourner t ; (* $N(y)=t^2-u \Longrightarrow t= \sqrt{u}$ *)
sinon $z=a+b \overline{X}~:=y^q$ ;
tant que $z \not \in {\mathbb K}$
Si N(z-1)=0 alors retourner (a-1) b-1
sinon si N(z+1)=0 alors retourner (a+1)b-1 ;
z :=z2 ;
fin( tant que )
(* le $y=t+\overline{X}$ était défavorable, on va en essayer un autre *)
fin( répéter )
FIN



Cyril Banderier
7/23/1997