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

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

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 :=z² ;
fin( tant que )
(* le $y=t+\overline{X}$ était défavorable, on va en essayer un autre *)
fin( répéter )
FIN