Principe :
Miller-Rabin est un test probabiliste basé sur une extension du petit théorème de Fermat.
a^d ≡ 1 (mod n) 或 a^(2^i × d) ≡ -1 (mod n) 对某个 0 ≤ i < r
Rounds et précision :
- Test probabiliste :Sélection aléatoire d'une base a ; chaque round réduit l'erreur à 1/4
- k rounds :Erreur théorique ≤ (1/4)^k, erreur réelle bien inférieure
- Test déterministe :Pour n < 3,317,044,064,679,887,385,961,981, avec les bases {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}, résultat 100% précis.
Cas particuliers :
- Petits nombres premiers :Les nombres comme 2, 3, 5, 7 sont identifiés directement
- Nombres pairs :Tous les nombres pairs sauf 2 sont composés
- Nombres de Carmichael :Les nombres passant le test de Fermat mais composés (ex. 561) sont correctement identifiés par Miller-Rabin.