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.

Sommaire

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 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 pseudopremier en base a.

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

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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Test de primalité de Miller-Rabin de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Test de primalite 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… …   Wikipédia en Français

  • 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… …   Wikipédia en Français

  • Test de primalite — Test de primalité Un test de primalité est un algorithme permettant de savoir si un nombre entier est premier. Sommaire 1 Méthode naïve 2 Tests probabilistes 3 Tests déterministes rapides …   Wikipédia en Français

  • Test de primalite AKS — Test de primalité AKS Le test de primalité AKS (aussi connu comme le test de primalité Agrawal Kayal Saxena et le test cyclotomique AKS) est un algorithme déterministe de preuve de primalité découvert et publié le 6 août 2002 par trois… …   Wikipédia en Français

  • Test de primalité aks — Le test de primalité AKS (aussi connu comme le test de primalité Agrawal Kayal Saxena et le test cyclotomique AKS) est un algorithme déterministe de preuve de primalité découvert et publié le 6 août 2002 par trois scientifiques indiens nommés… …   Wikipédia en Français

  • Test de primalité — Un test de primalité est un algorithme permettant de savoir si un nombre entier est premier. Sommaire 1 Méthode naïve 2 Tests probabilistes 3 Tests déterministes rapides …   Wikipédia en Français

  • Test de primalité AKS — Le test de primalité AKS (aussi connu comme le test de primalité Agrawal Kayal Saxena et le test cyclotomique AKS) est un algorithme déterministe de preuve de primalité découvert et publié le 6 août 2002 par trois scientifiques indiens nommés… …   Wikipédia en Français

  • Primalité — Test de primalité Un test de primalité est un algorithme permettant de savoir si un nombre entier est premier. Sommaire 1 Méthode naïve 2 Tests probabilistes 3 Tests déterministes rapides …   Wikipédia en Français

  • Michael O. Rabin — Michael Rabin  Pour l’article homonyme, voir Michael Rabin (violoniste).  Michael O. Rabin (né en 1931 à Breslau en Allemagne, maintenant Wrocław en Pologne) est un informaticien et un logicien ; il a été récipiendaire du prix… …   Wikipédia en Français

  • Michael Rabin —  Pour l’article homonyme, voir Michael Rabin (violoniste).  Michael Rabin Michael Oser Rabin (né en 1931 à Breslau en Allemagne, maintenant …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”