##  [Test de Primalité de Miller–Rabin](/fr/node/62000) 

 Définition

Algorithme probabiliste qui teste si un entier impair n est probablement premier en effectuant une ou plusieurs vérifications de 'strong probable prime' sur des bases aléatoires (ou choisies) à l'aide d'exponentiations modulaires et de règles de mise au carré.

 

 

 

 

 

 





## Principe

Principe

Écrire n-1 = 2^s * d avec d impair ; pour une base a, calculer a^d mod n puis les mises au carré successives ; si aucune de ces valeurs n'est égale à 1 ou n-1 selon le motif requis, n est composé. Répéter avec des bases indépendantes réduit exponentiellement la probabilité d'erreur.

 

 

 

 

 





## Démonstration

Démonstration

Tester n=561 avec la base a=2 : calculer 2^{d} mod 561 et ses carrés ; le test met en évidence un témoin de compositeness (561 est un nombre de Carmichael), donc Miller–Rabin le détecte comme composé pour certaines bases mais peut être 'strong probable prime' pour d'autres — d'où l'usage de plusieurs bases.

 

 

 

 

## Mauvaise application

Mauvaise application

Considérer un résultat 'probable prime' de Miller–Rabin comme une preuve absolue de primalité sans utiliser suffisamment de bases, ou employer trop peu de tours dans des contextes cryptographiques où l'erreur résiduelle peut être exploitée.

 

 

 

 

 





## Conséquence

Conséquence

Fournit un test de primalité probabiliste rapide et aisément réglable : avec un choix/ nombre de bases adéquat la probabilité qu'un composé passe tous les tests devient négligeable ; pour certaines plages de taille des bases fixes donnent des résultats déterministes.

 

 

 

 

## Inversion

Inversion

Recourir à des preuves de primalité déterministes (par exemple des algorithmes produisant des certificats) ou à la factorisation complète pour obtenir une certitude au lieu d'une assurance probabiliste.

 

 

 

 

 





## Limite

Limite

Test probabiliste uniquement : il affirme 'probable premier' ou 'composé' avec une erreur unilatérale (des composés peuvent passer) ; des garanties déterministes exigent des tours supplémentaires, des bases choisies pour des plages bornées ou des algorithmes différents.

 

 

 

 

 





## Tension sémantique

Tension sémantique

Entre en concurrence avec les tests déterministes et basés sur certificats : Miller–Rabin est beaucoup plus rapide pour de grands nombres et suffisant dans la plupart des usages pratiques, mais sa nature probabiliste contraste avec les algorithmes à primalité prouvée.

 

 

 

 

 





## Synthèse

Synthèse

Miller–Rabin est un filtre aléatoire rapide fondé sur l'exponentiation modulaire et les mises au carré qui, par la répétition sur bases indépendantes, réduit à un niveau négligeable la probabilité de classer à tort un composé comme premier tout en restant peu coûteux en calcul.