Bonsoir à toutes et à tous .
voici un test de primalité que j'aimerai rentrer en machine , c'est celui de Miller-Rabin plus précisément .
soit n un entier impair.
on definit r et s teles que n=2^r.s+1 avec s impair et r1.
Choisir un nombre avec 1<<n et calcluler (,n)
. Si (c1,n)>1 alors n n'est pas premier et le test est terminé .
. sinon , calculer (mod n)
- si alors soit n est premier soit n est pseudo premier-fort de base c1 .
- sinon , calculer
- si , alors soit n est premier soit n est pseudo-premier fort de base c1
-sinon calculer , tant que
- si pour 1i r-1 alors n n'est pas premier et le test est terminé .
Si le test n'a pas été interompu , recommencer le test pour un autre entier que c1 , puis un autre entier que c1 et c2 ...
voici ce que je propose mais ca me ca marche pas j'ai essayé de respecter le l'algorithme mais je sais pas ,
def TestMiller(n):
s = n-1
r = 0
while (s%2)==0:
s//=2
r+=1
for c1 in range(2,100):
if pgcd(c1,n)>1:
return " {} n'est pas premier".format(n)
else :
if expon(c1,s,n) == 1 :
return "{} pseudo premier de base {}".format(n,c1)
else :
if expon(c1,2*s,n)==-1:
return "{} pseudo premier de base {}".format(n,c1)
else:
i=2
while expon(c1,2**i*s,n)!=-1:
i=+1
for i in range (2,r):
while expon(c1,2**i*s,n)!=-1:
return "{} n'est pas premier".format(n)
notez par ailleurs que les fonction pgcd et expon sont respectivement les fonction me return le pgcd et l'exponentiation rapide .
Merci!