Test de primalité de Miller-Rabin

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

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.

[modifier] Concepts

Comme pour les tests de Fermat et de Solovay-Strassen, avec le test de Miller-Rabin nous relions une équation ou un système d'équations qui sont vraies pour des valeurs premières, et nous regardons 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 2^s × 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, une des équations suivantes doit être vraie pour un certain $a\in \left(\mathbb{Z}/n\mathbb{Z}\right)^*$ :

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

$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, réutilisons le petit théorème de Fermat :

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

Donc, si nous prenons les racines carrées de a^{n − 1}, nous obtiendrons soit 1 ou −1. Si nous obtenons −1 alors la deuxième équation est vraie et nous avons fini.

Dans le cas où nous avons extrait chaque puissance de 2 et que la deuxième équation n'est jamais vraie, nous partons avec la première équation qui doit aussi être égale à 1 ou −1, lors de l'extraction de la racine carrée. Néanmoins, si la deuxième équation n'est jamais vraie, alors elle ne peut pas être vraie pour r = 0, ce qui veut dire que

$a^{2^0\cdot d} = a^d \not\equiv -1\pmod{n}$

Ainsi, dans le cas ou la deuxième équation n'est pas vraie ; la première équation doit l'être.

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}$

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

alors a est appelé un témoin fort pour la composition de n. Autrement, a est appelé un menteur fort et n est un nombre probablement premier.

[modifier] Algorithme et temps d'exécution

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 n est composé, autrement il est probablement premier

écrire n − 1 comme 2^s × 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 ≠ 1 et $a^{2^rd}$ mod n ≠ −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 × log³ 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 à Õ(k × log² n), ainsi cet algorithme est de temps polynomial et efficient.

[modifier] Informations supplémentaires

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 pseudopremiè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 actuellement 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)² 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 Õ((log n)⁴).