Test de primalité de Miller-Rabin

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le test de primalité de Miller-Rabin est un test de primalité probabiliste : c’est-à-dire un algorithme qui détermine si un nombre donné est probablement premier, de façon similaire au test de primalité de Fermat et le test de primalité de Solovay-Strassen. Sa version originale, due à G. L. Miller, est déterministe, mais elle est reliée à l'hypothèse de Riemann généralisée non démontrée ; M. O. Rabin l'a modifiée pour obtenir un algorithme probabiliste inconditionnel.

Concepts[modifier | modifier le code]

Comme pour les Tests de primalité de Fermat ou de Solovay-Strassen, celui de Miller-Rabin consiste à tirer parti d'une équation ou d'un système d'équations qui sont vraies pour des valeurs premières, et à regarder si elles sont toujours vraies ou non pour un nombre dont nous voulons tester la primalité.

Soit n un nombre premier impair, alors nous pouvons écrire n − 1 comme 2s × d, où s est un entier et d est impair -- ceci est la même chose si nous factorisons 2 à partir de n - 1 de façon répétée. Alors, pour tout a\in \left(\mathbb{Z}/n\mathbb{Z}\right)^* tel que a est premier avec n, une des conditions suivantes doit être vérifiée:


a^{d} \equiv 1\pmod{n}

ou


a^{2^r\cdot d} \equiv -1\pmod{n} pour un certain 0 \le r \le s-1

Pour montrer que l'une d'elles doit être vraie, utilisons le petit théorème de Fermat :


a^{n-1} \equiv 1\pmod{n}

Donc, si nous prenons les racines carrées de an − 1, nous obtiendrons soit 1 ou −1 (toujours sous la condition que n est premier impair : en effet, ces extractions sont alors effectuées dans un corps (fini) de caractéristique différente de 2, à savoir \mathbb{Z}/n\mathbb{Z}). Si nous obtenons −1 alors la deuxième équation est vraie et nous avons fini.

Dans le cas où aucun des nombres a^{2^r\cdot d} ne s'est trouvé être égal à -1 modulo n, c'est que nous avons à chaque étape extrait l'autre racine carrée de 1, à savoir 1 lui-même, et que tous les nombres a^{2^r\cdot d} sont égaux à 1 modulo n. En particulier, pour r=0, on retrouve la première équation. Ce qui achève la démonstration.

Le test de primalité de Miller-Rabin est basé sur les équations précédentes. Nous voulons tester n pour voir s'il est premier, alors si


a^{d} \not\equiv 1\pmod{n}

et


a^{2^rd} \not\equiv -1\pmod{n} pour tous les 0 \le r \le s-1

alors a est appelé un témoin de Miller ou témoin fort pour la composition de n. Autrement, n est appelé: fortement probablement premier en base a. Lorsque n n'est pas premier mais composé, mais qu'il est fortement probablement premier en base a, on dit que a est un menteur fort et que n est pseudo-premier en base a.

Algorithme et temps d'exécution[modifier | modifier le code]

L'algorithme peut être écrit de la façon suivante :

Entrées : n : une valeur à tester pour sa primalité ; k : un paramètre qui détermine le nombre de fois qu'il faut tester pour la primalité.
Sortie : composé si on a au moins un Témoin de Miller a pour n, ce qui assure que n est composé, autrement fortement probablement premier
écrire n-1 comme 2^s \times d en factorisant les puissances de 2 à partir de n-1
répéter k fois:
prendre a aléatoirement dans l'intervalle [1 ; n − 1]
si a^d \mod n \neq 1 et a^{2^{r}d}\mod n \neq -1 pour tous les r dans l'intervalle [0 ; s − 1] alors retourner composé
retourner probablement premier

En utilisant l'exponentiation modulaire par carré répété, le temps d'exécution de cet algorithme est O(k × log3 n), où k est le nombre des différentes valeurs de a que nous testons. En allant plus loin, la multiplication rapide FFT peut rabaisser le temps d'exécution à O(k × log2 n), ainsi cet algorithme est de temps polynomial et efficace.

Informations supplémentaires[modifier | modifier le code]

Comme tous les tests de primalité probabilistes, il existe des valeurs de n qui produiront de manière répétée des menteurs, qui indiqueront que n est premier alors qu'il est composé -- ces valeurs sont appelées pseudo-premières.

Plus on teste de valeurs de a, meilleure est la précision du test. Il peut être montré qu'il existe toujours un témoin fort pour n'importe quel composé impair n, et qu'au moins 3/4 de ces valeurs pour a sont des témoins forts pour la composition de n. Ainsi, l'ensemble des menteurs forts est plus petit que l'ensemble des menteurs d'Euler (utilisés dans le test de primalité de Solovay-Strassen).

Dans l'usage général, le nombre actuel de témoins est plus grand que la borne inférieure. Par exemple, si nous testons un entier impair de 1024 bits n, en utilisant la borne inférieure, nous devrions avoir besoin de tester 44 valeurs différentes de a pour nous assurer que la chance qu'un nombre n donné soit déclaré premier alors qu'il est en fait composé, est inférieure à 2-80, ce qui veut dire que la valeur de n peut être utilisée de manière sûre dans les applications cryptologiques. Néanmoins, dans la pratique, nous avons généralement besoin de tester seulement 6 valeurs différentes de a pour garantir cette probabilité. Comparer ceci aux 90 itérations pour le test de primalité de Solovay-Strassen.

En supposant la véracité de l'hypothèse de Riemann généralisée, on peut prouver que, si toutes les valeurs de a comprises entre 1 et 2(log n)2 ont été testées et que n est encore « probablement premier », alors il est en fait assuré d'être premier. Ceci mène à un test de primalité déterministe qui possède un temps d'exécution de O((log n)4).

Liens externes[modifier | modifier le code]