Miller-Rabin Primality Test

Miller-Rabin est un test de primalité probabiliste : en écrivant n-1=2^s*d, il vérifie a^d≡1 ou un certain a^(2^r*d)≡-1 (mod n), avec une probabilité de faux positif d'au plus 1/4 par tour.

Objectif

Tester la primalité de manière efficace et probabiliste, utilisé pour générer les grands nombres premiers de RSA.

Mécanisme

Pour n-1=2^s*d, choisir un a aléatoire dans [2,n-2] et calculer x=a^d mod n. Si x=1 ou n-1, n est probablement premier. Sinon, élever au carré jusqu'à s-1 fois ; si n-1 apparaît, probablement premier, sinon n est définitivement composé. Après k tours, l'erreur est d'au plus 4^(-k).