from time import time
from random import randint
def gcd(a,b):
# Calcule le PGCD de a et b
while b>0:
a,b=b,a%b
return a
def millerTest(a,d,n,r):
# test de Miller pour un témoin a
# Retourne faux si n est composé et vrai si n est probablement premier
# d et r doivent vérifier n = 2^r * d + 1 avec d impair
x = pow(a, d, n) # Calcule a^d % n
if (x == 1 or x == n-1):
return True
for _ in range(r):
x = (x * x) % n
if (x == 1):
return False
if (x == n-1):
return True
return False
def isPrime(n, k=25):
# Test de primalité de Miller Rabin
# Si faux alors n est composé et si vrai alors n est probablement premier
# k determine le niveau de certitude : P(erreur) < 1/4**k
if (n <= 1 or n == 4):
return False
if (n <= 5):
return True
# Trouver d et r tels que n = 2^r * d + 1 avec d impair
d = n - 1
r = 0
while (d&1 == 0):
d >>= 1
r += 1
# Effectuer k tests de Miller
for i in range(k):
a = randint(2,n-2)
if (not millerTest(a, d, n, r)):
return False
return True
