Worldlex Wiki Un test de primalité est un algorithme permettant de déterminer si un nombre donné est premier . Il est notamment utilisé en cryptographie . Contrairement à la factorisation d'entiers , les tests de primalité ne fournissent généralement pas les facteurs premiers , mais indiquent seulement si le nombre donné est premier ou non. La factorisation est considérée comme un problème de calcul complexe, tandis que les tests de primalité sont relativement simples (leur complexité est polynomiale par rapport à la taille du nombre). Certains tests de primalité prouvent qu'un nombre est premier, tandis que d'autres, comme le test de Miller-Rabin, prouvent qu'il est composé . Par conséquent, ces derniers pourraient être plus justement appelés tests de primalité.
la division par essais successifs : étant donné un nombre , on vérifie s’il est divisible par un nombre premier compris entre 2 et (c’est-à-dire si la division ne laisse aucun reste ). Si c’est le cas, alors est composé . Sinon, il est premier. Tout diviseur , possède nécessairement un diviseur , et un diviseur premier de , donc la recherche de diviseurs premiers au plus est suffisante.Tests heuristiques
- 2 p −1 ≡ 1 (mod p ),
- f p +1 ≡ 0 (mod p ),
où f<sub> k</sub> est le k -ième nombre de Fibonacci . La première condition est le test de primalité de Fermat en base 2.
En général, si p ≡ a (mod x 2 +4), où a est un non-résidu quadratique (mod x 2 +4), alors p doit être premier si les conditions suivantes sont vérifiées :
- 2 p −1 ≡ 1 (mod p ),
- f ( x ) p +1 ≡ 0 (mod p ),
f ( x ) k est le k -ième polynôme de Fibonacci en x .
Selfridge , Pomerance et Wagstaff ont offert ensemble 620 $ pour un contre-exemple ou une preuve qu'il n'y en a pas, le prix étant maintenant dû par la Fondation de théorie des nombres .Les tests probabilistes sont plus rigoureux que les heuristiques car ils fournissent des bornes vérifiables sur la probabilité d'être trompé par un nombre composé. De nombreux tests de primalité populaires sont des tests probabilistes. Ces tests utilisent, outre le nombre testé n , d'autres nombres a choisis aléatoirement dans un espace d'échantillonnage ; les tests de primalité aléatoires classiques ne classent jamais un nombre premier comme composé, mais il est possible qu'un nombre composé soit classé comme premier. La probabilité d'erreur peut être réduite en répétant le test avec plusieurs valeurs de a choisies indépendamment ; pour deux tests couramment utilisés, pour tout nombre composé n, au moins la moitié des valeurs probablement premier .
Test de primalité de Fermat
Le test de primalité probabiliste le plus simple est le test de primalité de Fermat (en réalité un test de primalité). Son fonctionnement est le suivant :
- Étant donné un entier n , choisissez un entier premier avec n et calculez n − 1 modulo n . Si le résultat est différent de 1, alors n est composé. S'il est égal à 1, alors n peut être premier.
Si a <sub>n -1</sub> (modulo n ) vaut 1 mais que n n'est pas premier, alors n est dit pseudo-premier de base a . En pratique, si a <sub>n -1</sub> (modulo n ) vaut 1, alors n est généralement premier. Voici cependant un contre-exemple : si n = 341 et a = 2, alors
même si 341 = 11·31 est composé. En fait, 341 est le plus petit pseudopremier de base 2 (voir figure 1 de ).
Il n'existe que 21853 nombres pseudopremiers en base 2 dont la valeur est inférieure à 2,5 nombres de Carmichael ) ont la propriété que a <sub>n -1 </sub> vaut 1 (modulo n ) pour tout a premier avec n . Le plus petit exemple est n = 561 = 3 × 11 × 17, pour lequel a <sub>560 </sub> vaut 1 (modulo 561) pour tout a premier avec 561. Néanmoins, le test de Fermat est souvent utilisé lorsqu'un criblage rapide des nombres est nécessaire, par exemple lors de la génération des clés de l' algorithme cryptographique à clé publique RSA .
Test de primalité de Miller-Rabin et de Solovay-Strassen
Les tests de primalité de Miller-Rabin et de Solovay-Strassen sont des variantes plus sophistiquées qui détectent tous les nombres composés (ce qui signifie, encore une fois, que pour chaque nombre composé n , au moins 3/4 (Miller-Rabin) ou 1/2 (Solovay-Strassen) des nombres a sont des témoins de la primalité de n ). Ce sont également des tests de primalité.
Le test de primalité de Miller-Rabin fonctionne comme suit : étant donné un entier n , on choisit un entier positif a < n . Soit 2ᵀd = n − 1 , où d est impair. Si
et
Alors n est composé et a est un témoin de cette composition. Sinon, n peut être premier ou non. Le test de Miller-Rabin est un test de primalité probable robuste (voir PSW , page 1004).
Le test de primalité de Solovay-Strassen utilise une autre égalité : étant donné un nombre impair n , choisissez un entier a < n , si
Alors n est composé et a est un témoin de cette composition. Sinon, n peut être premier ou non. Le test de Solovay-Strassen est un test de primalité probable d'Euler (voir PSW , page 1003).
Pour chaque valeur individuelle de a , le test de Solovay-Strassen est moins puissant que le test de Miller-Rabin. Par exemple, si n = 1905 et a = 2, le test de Miller-Rabin indique que n est composé, contrairement au test de Solovay-Strassen. Cela s'explique par le fait que 1905 est un nombre pseudopremier d'Euler en base 2, mais pas un nombre pseudopremier fort en base 2 (ceci est illustré dans la figure 1 de PSW ).
test de primalité de Frobenius
Les tests de primalité de Miller-Rabin et de Solovay-Strassen sont simples et beaucoup plus rapides que les autres tests de primalité généraux. Le test de pseudoprimalité de Frobenius permet d'améliorer encore l'efficacité dans certains cas ; une itération de ce test prend environ trois fois plus de temps qu'une itération de Miller-Rabin, mais atteint une borne de probabilité comparable à celle de sept itérations de Miller-Rabin.
Le test de Frobenius est une généralisation du test de primalité probable de Lucas .
Test de primalité de Baillie-PSW
Le test de primalité de Baillie-PSW est un test probabiliste qui combine un test de Fermat ou de Miller-Rabin avec un test de primalité probable de Lucas afin d'obtenir un test de primalité sans contre-exemples connus. Autrement dit, il n'existe aucun nombre composé n pour lequel ce test conclut à une probable primalité de n . Il a été démontré qu'il n'existe aucun contre-exemple pour n .
Autres tests
Leonard Adleman et Ming-Deh Huang ont présenté une variante sans erreur (mais de complexité polynomiale attendue) du test de primalité des courbes elliptiques . Contrairement aux autres tests probabilistes, cet algorithme produit un certificat de primalité et peut donc être utilisé pour prouver qu'un nombre est premier. En pratique, l'algorithme est extrêmement lent.
Si des ordinateurs quantiques étaient disponibles, la primalité pourrait être testée asymptotiquement plus rapidement qu'avec des ordinateurs classiques. Une combinaison de l' algorithme de Shor , une méthode de factorisation d'entiers, avec le test de primalité de Pocklington pourrait résoudre le problème .
Tests déterministes rapides
Au début du XXe siècle, il a été démontré qu'un corollaire du petit théorème de Fermat pouvait servir à tester la primalité . Ceci a conduit au test de primalité de Pocklington . Cependant, comme ce test nécessite une factorisation partielle de n − 1, son temps d'exécution restait relativement long, même dans le pire des cas. Le premier test de primalité déterministe significativement plus rapide que les méthodes naïves fut le test de cyclotomie ; son temps d'exécution est de l'ordre de O ((log n ) c log log log n ), où n est le nombre d'éléments à tester et c une constante indépendante de n . Plusieurs améliorations ont été apportées par la suite, mais aucune n'a pu être démontrée comme ayant un temps d'exécution polynomial. Le temps d'exécution est mesuré en fonction de la taille de l'entrée, qui dans ce cas est de l'ordre de log n , c'est-à-dire le nombre de bits nécessaires pour représenter le nombre n . On peut démontrer que le test de primalité des courbes elliptiques s'exécute en O(log n ) ⁶ , sous certaines conjectures de la théorie analytique des nombres . De même, sous l' hypothèse de Riemann généralisée (que Miller appelle, de manière confuse, « l' hypothèse de Riemann étendue »), on peut démontrer que le test déterministe de Miller , qui constitue la base du test probabiliste de Miller-Rabin, s'exécute en O (log n ) ⁴ . En pratique, cet algorithme est plus lent que les deux autres pour les nombres de taille acceptable. L'implémentation de ces deux méthodes étant relativement complexe et sujette aux erreurs de programmation, des tests plus lents mais plus simples sont souvent privilégiés.
En 2002, Manindra Agrawal , Neeraj Kayal et Nitin Saxena ont inventé le premier test de primalité déterministe inconditionnel et polynomial . Le test de primalité AKS s'exécute en O((log n ) <sup>12</sup> ) (amélioré à O((log n ) <sup>7,5</sup> ) dans la version révisée et publiée de leur article), et peut être réduit à O((log n ) <sup> 6 </sup> ) si la conjecture de Sophie Germain est vraie. Par la suite, Lenstra et Pomerance ont présenté une version du test qui s'exécute en temps O((log n ) <sup>6</sup> ) de manière inconditionnelle.
Agrawal, Kayal et Saxena proposent une variante de leur algorithme qui s'exécuterait en O((log n ) ³ ) si la conjecture d'Agrawal est vraie ; cependant, un argument heuristique d'Hendrik Lenstra et Carl Pomerance suggère qu'elle est probablement fausse. Une version modifiée de la conjecture d'Agrawal, la conjecture d'Agrawal-Popovych, pourrait néanmoins être vraie.
Complexité
En théorie de la complexité algorithmique , le langage formel correspondant aux nombres premiers est noté PRIMES. Il est facile de montrer que PRIMES appartient à Co-NP : son complémentaire, COMPOSITES, appartient à NP car on peut déterminer la compositivité en devinant un facteur de manière non déterministe.
En 1975, Vaughan Pratt a démontré qu'il existait un certificat de primalité vérifiable en temps polynomial, et donc que PRIMES appartenait à NP , et par conséquent à le certificat de primalité pour plus de détails.
La découverte ultérieure des algorithmes de Solovay–Strassen et de Miller–Rabin a placé PRIMES dans coRP . En 1992, l'algorithme d'Adleman–Huang a réduit la complexité à , ce qui a remplacé le résultat de Pratt.
Le test de primalité d'Adleman–Pomerance–Rumely de 1983 a placé PRIMES dans QP ( temps quasi-polynomial ), qui n'est pas connu pour être comparable aux classes mentionnées ci-dessus.
Du fait de sa simplicité pratique, de l'existence d'algorithmes polynomiaux sous l'hypothèse de Riemann et d'autres observations similaires, on a longtemps soupçonné, sans toutefois le prouver, que le problème de primalité pouvait être résolu en temps polynomial. L'existence du test de primalité AKS a finalement tranché cette question et a placé PRIMES dans P. Cependant, on ignore si PRIMES est P-complet et s'il appartient à des classes incluses dans P, telles que NC ou L. On sait que PRIMES n'appartient pas à AC <sub>0 </sub> .
méthodes de théorie des nombres
Il existe des méthodes arithmétiques permettant de déterminer si un nombre est premier, comme le test de Lucas et le test de Proth . Ces tests nécessitent généralement la factorisation de n + 1, n − 1 ou d'une quantité similaire, ce qui les rend inadaptés aux tests de primalité généraux. Cependant, ils se révèlent souvent très efficaces lorsque le nombre testé n possède une forme particulière.
Le critère de Lucas repose sur le fait que l' ordre multiplicatif d'un nombre a modulo n est n − 1 pour un nombre premier n lorsque a est une racine primitive modulo n . Si nous pouvons montrer que a est primitif pour n , nous pouvons montrer que n est premier.
Plus d articles de Worldlex Wiki
Revenez a l index pour explorer davantage de pages sur l histoire, la science, la culture, la geographie et la societe en francais.
Explorer l index