test de Miller-Rabin

Prenons un entier impair dont on ignore s’il est premier. On choisit un nombre plus petit, appelé base, puis on calcule quelques puissances en ne gardant que leur reste après division par l’entier testé. Pour un nombre premier, ces restes doivent suivre un parcours très contraint : ils rencontrent 1 au départ ou −1 avant la fin.

Un parcours qui enfreint cette règle prouve que l’entier est composé. Un parcours conforme ne constitue pas toujours une preuve : une autre base peut encore révéler un diviseur caché.

Le test de Miller-Rabin est un test de primalité appliqué à un entier impair n. On décompose d’abord n − 1 en un produit d’une puissance de 2 et d’un entier impair. Si s désigne l’exposant positif de 2 et d l’entier impair obtenu, cette décomposition s’écrit $n-1=2^{s}dn-1=2^s\; d$. On choisit ensuite une base a dont le plus grand commun diviseur avec n vaut 1.

Lorsque n est premier, la base a satisfait nécessairement au moins une des conditions suivantes : la puissance a^d a pour reste 1 modulo n, ou l’une des puissances obtenues en doublant successivement l’exposant a pour reste −1 modulo n. En notant r le nombre de doublements, le critère complet est $a^d\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}n)\text{ou}{a}^{2^{r}d}\equiv -1(\mathrm{m}\mathrm{o}\mathrm{d}n)\text{pour un }r\in \{0,\dots ,s-1\}a^d\backslash equiv\; 1\backslash pmod\; n\backslash quad\backslash text\{ou\}\backslash quad\; a^\{2^r\; d\}\backslash equiv\; -1\backslash pmod\; n\backslash quad\backslash text\{pour\; un\; \}r\backslash in\backslash \{0,\backslash ldots,s-1\backslash \}$.

Si aucune condition n’est satisfaite, n est composé et a en est un témoin. Si une condition l’est, n franchit seulement ce tour : certains nombres composés, appelés pseudo-premiers pour cette base, peuvent imiter le comportement attendu. Sous l’hypothèse de Riemann généralisée, la formulation de Miller est déterministe en testant les bases jusqu’à une borne garantie ; dans le cadre général, Miller-Rabin choisit des bases de manière probabiliste et répète le test pour réduire le risque qu’un composé passe inaperçu.

Testons l’entier n = 221 avec la base a = 2. Les données sont n = 221, a = 2 et n − 1 = 220. La base est bien première avec 221.

1. Décomposer 220 donne $220=2^2\times 55220=2^2\backslash times55$. Ainsi, s = 2 et d = 55, qui est impair.

2. Calculer la première puissance donne $2^{55}\equiv 128(\mathrm{m}\mathrm{o}\mathrm{d}221)2^\{55\}\backslash equiv128\backslash pmod\{221\}$. Ce reste n’est ni 1 ni −1, ce dernier correspondant à 220 modulo 221.

3. Élever ce reste au carré donne ${128}^2\equiv 30(\mathrm{m}\mathrm{o}\mathrm{d}221)128^2\backslash equiv30\backslash pmod\{221\}$, donc $2^{110}\equiv 30(\mathrm{m}\mathrm{o}\mathrm{d}221)2^\{110\}\backslash equiv30\backslash pmod\{221\}$. Comme s = 2, il n’y a pas d’autre exposant à examiner.

Aucun reste attendu n’apparaît : 2 est un témoin et 221 est composé. Le contrôle se refait par division : 221 = 13 × 17. Le schéma récapitule les deux restes qui conduisent au verdict.

Pour filtrer une liste de grands entiers candidats, on élimine d’abord les divisibilités évidentes, puis Miller-Rabin écarte rapidement les composés restants. Une base qui échoue suffit à arrêter le calcul avec un verdict certain de compositivité.

Lorsqu’un entier franchit un tour, on recommence avec d’autres bases. Ce geste est préféré à une conclusion immédiate, car un composé peut se comporter comme un premier pour certaines bases.

Quand une preuve de primalité est exigée, le résultat probabiliste sert de filtre et non de certificat. Il faut alors employer une méthode déterministe adaptée au cadre considéré.

Nombre premier et premier probable. Un nombre premier impair satisfait le critère pour toute base admissible. Un premier probable ne l’a franchi que pour les bases essayées : 221, par exemple, est définitivement composé dès que la base 2 produit les restes 128 puis 30.

Nombre pseudo-premier et nombre de Carmichael. Un pseudo-premier de Fermat est un composé qui vérifie, pour une base donnée, la congruence issue du petit théorème de Fermat ; un composé qui passe un tour de Miller-Rabin est plus précisément un pseudo-premier fort pour cette base. Les nombres de Carmichael appartiennent à la famille plus large des composés capables de tromper certains tests ; les expressions ne sont donc pas interchangeables.

Un tour réussi ne prouve pas la primalité. Le symptôme est l’apparition d’un reste autorisé pour la base choisie. Il faut annoncer un « premier probable » et essayer d’autres bases, car un entier composé peut franchir ce tour.

La base doit être admissible. Pour une base vérifiant 1 < a < n, si le plus grand commun diviseur de a et n dépasse 1, les hypothèses du critère ne sont pas réunies. Ce calcul fournit alors un diviseur non trivial et permet de conclure directement que n est composé.

Le critère est formulé pour un entier premier impair. Un entier pair supérieur à 2 est composé sans lancer la chaîne de puissances. Les petits cas 2 et les entiers inférieurs à 2 doivent être traités séparément avant la décomposition de n − 1.

Les nombres de Carmichael restent un piège de lecture. Leur présence parmi les pseudo-premiers rappelle qu’un comportement conforme à une congruence nécessaire ne suffit pas à établir qu’un entier est premier. Le verdict doit rester attaché aux bases effectivement testées.

Le nombre premier donne le cadre du verdict recherché et rappelle ce que signifie n’avoir que deux diviseurs positifs.

Le nombre pseudo-premier précise comment un entier composé peut satisfaire un critère conçu comme condition nécessaire de primalité.

Le nombre de Carmichael approfondit une famille de composés particulièrement instructive pour comprendre les limites des tests fondés sur des congruences.