Bonjour.
Je propose les modifications de code suivantes:
def test(n):
if (n%2)==0:
return "{} est non premier".format(n)
for i in range(100):
b1 = randint(2,n-1)
if expon(b1,(n-1)//2,n)!=jacobi(b1,n)%n:
return "{} n'est pas premier".format(n)
return "{} est probablement premier".format(n)
Commentaires:
1) On ne réalise pas n "tests de jacobi", le but est d'obtenir une procédure rapide.
2) De mémoire, lorsque n n'est pas premier, au moins la moitié des entiers b ne passent pas le "test de jacobi" . Si p "tests de jacobi" sont passés avec succès, on a une chance sur 2^p au maximum de déclarer un entier n premier alors qu'en fait il ne l'est pas. J'ai choisi de prendre p=100, vous pouvez le prendre plus grand si vous voulez mais cela augmentera d'autant le temps de la procédure.
3) Il est inutile de tester si n et p sont premiers entre eux, le "test de jacobi" établira que n n'est pas premier dans ce cas.
3) J'ai testé la procédure pour n=5, puis pour
(premier de Mersenne), puis pour
(il n'est pas premier). Dans les trois cas, le résultat est instantané et juste.
4) Plutôt que de mettre un message convivial, je suggère d'utiliser True et False. Le but de la procédure est de trouver de grands entiers premiers rapidement et il faut tester beaucoup de valeurs de n avant d'en trouver un qui convienne.
5) Je n'ai pas enlevé la vérification du fait que n n'est pas multiple de 2, mais il faudrait l'enlever. On ne teste évidemment pas si un entier pair est premier, on le sait.