Test de primalité de Miller-Rabin

Infos
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 probabilist
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 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/n\mathbb\right)^
- tel que a est premier a n, une des conditions suivantes doit être vérifiée: : a^ \equiv 1\pmod ou : a^2^r\cdot d \equiv -1\pmod 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^ \equiv 1\pmod Donc, si nous prenons les racines carrées de an − 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 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^ \not\equiv 1\pmod et : a^ \not\equiv -1\pmod 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 a dire que l'on a égalité pour l'une ou l'autre des deux equations) 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 2s × d en factorisant les puissances de 2 à partir de n − 1 :répéter k fois: ::prendre a aléatoirement dans l'intervalle ::si ad mod n ≠ 1 et a^ mod n ≠ −1 pour tous les r dans l'intervalle 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 à Õ(k × log2 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 '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)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 Õ((log n)4). ==
Sujets connexes
Algorithmique   Cryptologie   Exponentiation modulaire   Exposant (mathématiques)   Factorisation   Hypothèse de Riemann généralisée   Leonhard Euler   Michael Rabin   Nombre composé   Nombre premier   Petit théorème de Fermat   Racine carrée   Test de primalité   Test de primalité de Fermat   Test de primalité de Solovay-Strassen  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^