Test de primalité de miller-rabin

Test de primalité de Miller-Rabin

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

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 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, 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 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 aboutissions alors (par divisions successives par 2) à la première équation qui doit aussi être égale à 1 ou −1, puisqu'elle est elle-même une racine carrée. Néanmoins, si la deuxième condition n'est jamais vérifiée, alors elle ne l'est pas non plus pour r = 0, ce qui veut dire que

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

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, si ces deux dernières inégalités ne sont pas vérifiées (C'est-à-dire que l'on a égalité pour l'une ou l'autre des deux équations) n est appelé: fortement probablement premier en base a. Lorsque n n'est pas premier mais composé, a est dit menteur fort.

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 on a au moins un Témoin de Miller a pour n, ce qui assure que n est composé, autrement il est fortement 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^{r}d}$ 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.

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)⁴).

Liens externes

• MathWorld - Rabin-Miller Strong Pseudoprime Test
• Code source de l'essai principal de nombre de Miller-Rabin, C++
• Interactive Online Implementation of the Deterministic Variant (en anglais)

Ce document provient de « Test de primalit%C3%A9 de Miller-Rabin ».