test de Miller-Rabin
test de primalité de Miller-Rabin
test de Rabin-Miller
algorithme de Miller-Rabin
ARITHMETIQUE
Test de primalité dont la première version, due à G. L. Miller est déterministe et qui a été modifié par M. O. Rabin en un algorithme probabiliste.
Il est basé sur la propriété suivante :
Soit n un nombre premier impair, on écrit n − 1 = 2s d, où s est un entier et d est impair. Alors, pour tout a de (Z/nZ)* tel que a est premier avec n, une des conditions suivantes doit être vérifiée :
ad = 1 (modulo n)
ou
a2rd = -1 (modulo n)
pour un certain r compris entre 0 et s-1.
On en déduit le test et l’algorithme de primalité .
Il existe des nombres qui échapppent à ce test, ce sont des nombres pseudo-premiers (dont les nombres de Carmichael )