Algèbre T1
Cela permet de mettre en évidence les deux ingrédients techniques dont nous
aurons besoin :
• la division euclidienne dans Z[i], déjà implémentée ;
• trouver un élément d’ordre 4 dans Z/pZ, p étant un nombre premier de la
forme 4k + 1.
Enfin, le travail de synthèse consiste à démontrer que x p ainsi construit est bien
de norme p. Ce sera fait en fin de TP.
Élément d’ordre 4 dans Z/pZ
L’idée est la suivante : Si p est un nombre premier de la forme 4k + 1, alors
en prenant « au hasard » un élément a de F ∗
p , il y a de « grande chance » que a k
soit un élément d’ordre 4.
6. Tester expérimentalement la stratégie proposée en prenant (« au hasard ») des
p 1000 de la forme désirée.
Remarque technique : Pour tirer des nombres « au hasard », on pourra utiliser la
fonction
RandomTools[Generate](integer(range=m..n))
qui renvoie un nombre entre deux entiers m et n. Par exemple, la procédure suivante
renvoie un nombre premier pseudo-aléatoire compris entre 3 et n :
> randprime:=proc(n);
RETURN(prevprime(RandomTools[Generate](integer(range=5..n+1))));
end;
7. À partir de vos tests, combien de a faut-il choisir en moyenne pour être sûr d’en
avoir un « bon ». Donner des arguments théoriques pour valider vos résultats
expérimentaux. (Remarquer que a k est d’ordre 4 si et seulement si a
p−1
2
= −1 ;
considérer alors l’endomorphisme x → x
p−1
2
de F ∗
p .)
8. En déduire une procédure ordre4 qui, étant donné en entrée un nombre premier p de la forme 4k + 1, renvoie un entier c, avec |c| < p/2, et tel que sa
classe dans F p soit un élément d’ordre 4.
234