Exercice 21 - Test de primarité

Vous utiliserez pour vérifier si un nombre est premier l'algorithme suivant, basé sur le petit théorème de Fermat. Il teste le théorème de Fermat pour s'assurer que $n$ est premier. Si $n$ ne vérifie pas ce théorème pour une valeur $a$ arbitraire, alors $n$ n'est pas premier. Sinon, on ne peut pas conclure immédiatement. Le cas particulier où on trouverait un nombre inversible $a$ qui ne soit pas un multiple de $n$ nous permet de conclure la non-primarité de $n$. Le test est effectué $m$ fois, si aucune valeur ne mettant en défaut le théorème de Fermat n'est trouvée, alors $n$ est probablement premier.

Ecrire cet algorithme sans gmp pour tester la primarité de nombres générés aléatoirement, vérifier les résultats retournés.