Malgré la demande explicite d’« écrire une procédure ou une fonction », un langage de programmation usuel ne permet pas de faire ce TP, en raison de la haute précision requise. Ce sera donc WxMaxima qui va être utilisé pour ce TP, et même là, on verra qu’il faudra ruser un peu.
WxMaxima permet de faire de la programmation déclarative, ce qui veut dire que pour écrire la fonction booléenne "pseudopremier", il suffit de décrire celle-ci :
Ceci veut dire qu’un nombre $n$ est pseudo-premier si et seulement si il divise $2^{n-1}-1$ et il n’est pas premier (mod(a,b) donne a modulo b).
Après ça il suffit d’entrer pseudopremier(5) pour vérifier que 5 n’est pas pseudopremier (affichage "false").
Pour chercher tous les nombres pseudo-premiers de 2 à 1000, la boucle suivante convient :
ce qui donne la réponse à la question A.2 :
| 341 |
| 561 |
| 645 |
Pour voir si $2^{341}-1$ est pseudo-premier, on se heurte à un problème lié à la taille du nombre considéré :
Pour avoir une meilleure chance de s’en sortir, il faut modifier la fonction pseudopremier, en utilisant non plus "mod(a,b)" mais "power_mod(a,b,n)" qui donne $a^b$ modulo $n$, en utilisant un algorithme rapide n’essoufflant pas l’ordinateur :
ce qui permet alors de vérifier les conjectures sur $2^{341}-1$, $2^{561}-1$ et $2^{645}-1$.
Commentaires