Test de primalité AKS - AKS primality test

Le test de primalité AKS (également connu sous le nom de test de primalité Agrawal-Kayal-Saxena et test AKS cyclotomique ) est un algorithme déterministe de preuve de primalité créé et publié par Manindra Agrawal , Neeraj Kayal et Nitin Saxena , informaticiens à l' Indian Institute of Technology Kanpur , le 6 août 2002, dans un article intitulé « PRIMES is in P ». L'algorithme a été le premier à pouvoir déterminer de manière prouvée si un nombre donné est premier ou composé en temps polynomial , sans s'appuyer sur des conjectures mathématiques telles que l' hypothèse généralisée de Riemann . La preuve est aussi remarquable pour ne pas s'appuyer sur le domaine de l' analyse . En 2006, les auteurs ont reçu à la fois le prix Gödel et le prix Fulkerson pour leur travail.

Importance

AKS est le premier algorithme de preuve de primalité à être à la fois général , polynomial , déterministe et inconditionnel . Les algorithmes précédents avaient été développés pendant des siècles et atteignaient au plus trois de ces propriétés, mais pas les quatre.

L'algorithme AKS peut être utilisé pour vérifier la primalité de tout nombre général donné. De nombreux tests de primalité rapides sont connus et ne fonctionnent que pour les nombres avec certaines propriétés. Par exemple, le test de Lucas-Lehmer ne fonctionne que pour les nombres de Mersenne , tandis que le test de Pépin ne peut être appliqué qu'aux nombres de Fermat .
Le temps d'exécution maximal de l'algorithme peut être exprimé sous la forme d'un polynôme sur le nombre de chiffres du nombre cible. ECPP et APR prouvent ou réfutent de manière concluante qu'un nombre donné est premier, mais ne sont pas connus pour avoir des limites de temps polynomiales pour toutes les entrées.
L'algorithme est assuré de distinguer de manière déterministe si le nombre cible est premier ou composé. Les tests randomisés, tels que Miller-Rabin et Baillie-PSW , peuvent tester n'importe quel nombre donné pour la primalité en temps polynomial, mais sont connus pour ne produire qu'un résultat probabiliste.
L'exactitude de l'AKS ne dépend d'aucune hypothèse subsidiaire non prouvée . En revanche, la version de Miller du test Miller-Rabin est entièrement déterministe et s'exécute en temps polynomial sur toutes les entrées, mais son exactitude dépend de la vérité de l' hypothèse de Riemann généralisée encore non prouvée .

Bien que l'algorithme ait une immense importance théorique, il n'est pas utilisé dans la pratique, ce qui en fait un algorithme galactique . Pour les entrées 64 bits, le test de primalité Baillie-PSW est déterministe et exécute plusieurs ordres de grandeur plus rapidement. Pour les entrées plus importantes, les performances des tests ECPP et APR (également inconditionnellement corrects) sont de loin supérieures à celles de l'AKS. De plus, ECPP peut produire un certificat de primalité qui permet une vérification indépendante et rapide des résultats, ce qui n'est pas possible avec l'algorithme AKS.

notions

Le test de primalité AKS est basé sur le théorème suivant: Etant donné un entier et entier coprime à , est premier si et seulement si le polynôme relation de congruence $n\geq 2$ ${\style d'affichage a}$ ${\style d'affichage n}$ ${\style d'affichage n}$

(X+a)^{n}\equiv X^{n}+a{\pmod {n}}

( 1 )

tient dans l'anneau polynomial . Notez que désigne l' indéterminé qui génère cet anneau polynomial. $\mathbb {Z} _{n}[X]$ ${\style d'affichage X}$

Ce théorème est une généralisation aux polynômes du petit théorème de Fermat . Dans un sens, cela peut être facilement prouvé en utilisant le théorème du binôme avec la propriété suivante du coefficient du binôme :

{n \choisissez k}\equiv 0{\pmod {n}}

pour tout si est premier.

{\style d'affichage 0<k<n}

{\style d'affichage n}

Si la relation ( 1 ) constitue en elle-même un test de primalité, sa vérification prend un temps exponentiel : l' approche de la force brute nécessiterait l'expansion du polynôme et une réduction des coefficients résultants . ${\style d'affichage (X+a)^{n}}$ ${\pmod {n}}$ ${\style d'affichage n+1}$

La congruence est une égalité dans l' anneau polynomial . L'évaluation dans un anneau quotient de crée une limite supérieure pour le degré des polynômes impliqués. L'AKS évalue l'égalité dans , rendant la complexité de calcul dépendante de la taille de . Pour plus de clarté, cela est exprimé comme la congruence $\mathbb {Z} _{n}[X]$ $\mathbb {Z} _{n}[X]$ $\mathbb {Z} _{n}[X]/(X^{r}-1)$ ${\style d'affichage r}$

(X+a)^{n}\equiv (X^{n}+a){\pmod {X^{r}-1,n}}

( 2 )

qui est le même que :

{\style d'affichage (X+a)^{n}-(X^{n}+a)=(X^{r}-1)g+nf}

( 3 )

pour certains polynômes et . ${\style d'affichage f}$ ${\style d'affichage g}$

Notez que tous les nombres premiers satisfont cette relation (choisir dans ( 3 ) donne ( 1 ), ce qui est vrai pour premier). Cette congruence peut être vérifiée en temps polynomial lorsque est polynomial aux chiffres de . L'algorithme AKS évalue cette congruence pour un grand ensemble de valeurs, dont la taille est polynomiale aux chiffres de . La preuve de validité de l'algorithme AKS montre que l'on peut trouver un et un ensemble de valeurs avec les propriétés ci-dessus telles que si les congruences sont vérifiées, alors est une puissance d'un nombre premier. ${\style d'affichage g=0}$ ${\style d'affichage n}$ ${\style d'affichage r}$ ${\style d'affichage n}$ ${\style d'affichage a}$ ${\style d'affichage n}$ ${\style d'affichage r}$ ${\style d'affichage a}$ ${\style d'affichage n}$

Historique et durée de fonctionnement

Dans la première version de l'article cité ci-dessus, les auteurs ont prouvé que la complexité temporelle asymptotique de l'algorithme était (en utilisant Õ de la notation O big )—la douzième puissance du nombre de chiffres en n fois un facteur qui est polylogarithmique dans le nombre de chiffres. Cependant, cette limite supérieure était plutôt lâche; une conjecture largement répandue sur la distribution des nombres premiers de Sophie Germain , si elle était vraie, réduirait immédiatement le pire des cas à . ${\tilde {O}}(\log(n)^{12})$ ${\tilde {O}}(\log(n)^{6})$

Dans les mois qui ont suivi la découverte, de nouvelles variantes sont apparues (Lenstra 2002, Pomerance 2002, Berrizbeitia 2002, Cheng 2003, Bernstein 2003a/b, Lenstra et Pomerance 2003), qui ont grandement amélioré la vitesse de calcul. En raison de l'existence de nombreuses variantes, Crandall et Papadopoulos se réfèrent à la « classe AKS » des algorithmes dans leur article scientifique « Sur la mise en œuvre des tests de primalité de la classe AKS », publié en mars 2003.

En réponse à certaines de ces variantes, et à d'autres retours, l'article « PRIMES is in P » a été mis à jour avec une nouvelle formulation de l'algorithme AKS et de sa preuve d'exactitude. (Cette version a finalement été publiée dans Annals of Mathematics .) Alors que l'idée de base est restée la même, r a été choisi d'une nouvelle manière et la preuve de l'exactitude a été organisée de manière plus cohérente. La nouvelle preuve reposait presque exclusivement sur le comportement des polynômes cyclotomiques sur des corps finis . La nouvelle limite supérieure de la complexité temporelle a ensuite été réduite à l'aide de résultats supplémentaires de la théorie des tamis à . ${\tilde {O}}(\log(n)^{10.5})$ ${\tilde {O}}(\log(n)^{7.5})$

En 2005, Pomerance et Lenstra ont fait la démonstration d'une variante d'AKS qui fonctionne en opération, menant à une autre version mise à jour de l'article. Agrawal, Kayal et Saxena ont proposé une variante qui se produirait si la conjecture d'Agrawal était vraie ; cependant, un argument heuristique de Pomerance et Lenstra a suggéré qu'il est probablement faux. ${\tilde {O}}(\log(n)^{6})$ ${\tilde {O}}(\log(n)^{3})$

L'algorithme

L'algorithme est le suivant :

Entrée : entier

n > 1

.

Vérifier si n est une puissance parfaite : si $n = a b$ pour les entiers $a > 1$ et $b > 1$ , sortie composite .
Trouvez le plus petit r tel que $ord r (n) > (log 2 n) 2$ . (si r et n ne sont pas premiers entre eux, alors sautez ce r )
Pour tout 2 ≤ a ≤ min ( r , n −1), vérifier que a ne divise pas n : Si a | n pour certains 2 ≤ a ≤ min ( r , n −1), sortie composite .
Si n ≤ r , sortie prime .
Pour $a = 1$ à faire $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$
si ( X + a ) ⁿ ≠ X ⁿ + a (mod X ^r - 1, n ), la sortie composite ;
Premier de sortie .

Ici, ord _r ( n ) est l' ordre multiplicatif de n modulo r , log ₂ est le logarithme binaire , et est la fonction totale d'Euler de r . $\varphi (r)$

L'étape 3 est montrée dans l'article en vérifiant 1 < ( a , n ) < n pour tout a ≤ r . On peut voir que cela équivaut à une division d'essai jusqu'à r , ce qui peut être fait très efficacement sans utiliser pgcd . De même, la comparaison de l'étape 4 peut être remplacée en faisant en sorte que la division d'essai renvoie prime une fois qu'elle a vérifié toutes les valeurs jusqu'à et y compris $\left\lfloor {\sqrt {n}}\right\rfloor .$

Une fois au-delà des très petites entrées, l'étape 5 domine le temps pris. La réduction essentielle de la complexité (d'exponentielle à polynomiale) est obtenue en effectuant tous les calculs dans l'anneau fini

R:={\Bigl (}{\bigl (}\mathbb {Z} /(n){\bigr )}[X]{\Bigr )}{\Bigl /}(X^{r}\ !\!-\!\!1){\Bigr .}

constitué d' éléments. Cet anneau ne contient que les monômes , et les coefficients sont dans lesquels a des éléments tous codables dans les bits. ${\style d'affichage n\cdot r}$ ${\style d'affichage r}$ $\{X^{0},X^{1},\ldots ,X^{r-1}\}$ $\mathbb {Z} /(n)=:\mathbb {Z} _{n}$ ${\style d'affichage n}$ $\log _{2}(n)$

La plupart des améliorations ultérieures apportées à l'algorithme se sont concentrées sur la réduction de la taille de r, ce qui accélère l'opération de base à l'étape 5, et sur la réduction de la taille de s , le nombre de boucles effectuées à l'étape 5. Généralement, ces changements ne modifient pas le calcul. complexité, mais peut conduire à de nombreux ordres de grandeur en moins de temps, par exemple la version finale de Bernstein a une accélération théorique d'un facteur de plus de 2 millions.

Aperçu de la preuve de validité

Pour que l'algorithme soit correct, toutes les étapes qui identifient n doivent être correctes. Les étapes 1, 3 et 4 sont trivialement correctes, puisqu'elles sont basées sur des tests directs de la divisibilité de n . L'étape 5 est également correcte : puisque (2) est vrai pour tout choix d' un premier avec n et r si n est premier, une inégalité signifie que n doit être composé.

Le cas difficile de l'algorithme est l'énoncé itéré à l'étape 5. Si cela dans l'anneau fini R se trouve entraîner l'incongruence

u\not \equiv v\;{\bigl (}{\text{mod }}(X^{r}\!\!-\!\!1),n{\bigr )}

cela équivaut à

u\equiv v\;{\bigl (}{\text{mod }}(X^{r}\!\!-\!\!1){\bigr )}\quad \implies \quad u \not \equiv v\;({\text{mod }}n)

,

de sorte qu'après avoir réduit aux r monômes au moyen de doit seulement être vérifié. ${\text{mod }}(X^{r}\!\!-\!\!1)$ $u\pas \equiv v\;({\text{mod }}n)$

Exemple 1 : n = 31 est premier

Entrée : entier n = 31 > 1.

  If n = a^b for integers a > 1 and b > 1, output composite.
    For [ b=2, b <= log₂(n), b++,
      a=n^1/b;
      If [ a is integer, Return[Composite]]
    ];
    a=n^1/2...n^1/4={5.568, 3.141, 2.360}

  Find the smallest r such that O_r(n) > (log₂ n)².
    maxk=⌊(log₂ n)²⌋;
    maxr=Max[3, ⌈(Log₂ n)⁵⌉]; (*maxr really isn't needed*)
    nextR=True;
    For [r=2, nextR && r < maxr, r++,
      nextR=False;
      For [k=1,(!nextR) &&k ≤ maxk, k++,
        nextR=(Mod[n^k, r]==1 || Mod[n^k, r]==0)
      ]
    ];
    r--; (*the loop over increments by one*)
     
    r = 29

  If 1 < gcd(a,n) < n for some a ≤ r, output composite.
    For [a=r, a > 1, a--,
      If [(gcd=GCD[a,n]) > 1 && gcd < n, Return[Composite]]
    ];
     
    gcd={GCD(29,31)=1, GCD(28,31)=1, ..., GCD(2,31)=1} ≯ 1

  If n ≤ r, output prime.
    If [n ≤ r, Return[Prime]]; (* this step may be omitted if n > 5690034 *)
     
    31 > 29

  For a = 1 to  $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$  do
    if (X+a)ⁿ≠ Xⁿ+a (mod X^r − 1,n), output composite;
     
    φ[x_]:=EulerPhi[x];
    PolyModulo[f_]:=PolynomialMod[ PolynomialRemainder[f,x^r-1,x],n];
    max=Floor[Log[2,n]√φ[r]];
    For[a=1, a ≤ max, a++,
      If[PolyModulo[(x+a)ⁿ-PolynomialRemainder[xⁿ+a, x^r-1], x]≠0,
        Return[Composite]
      ]
    ];
     
    (x+a)³¹ =
      a³¹ +31a³⁰x +465a²⁹x² +4495a²⁸x³ +31465a²⁷x⁴ +169911a²⁶x⁵ +736281a²⁵x⁶ +2629575a²⁴x⁷ +7888725a²³x⁸ +20160075a²²x⁹ +44352165a²¹x¹⁰ +84672315a²⁰x¹¹ +141120525a¹⁹x¹² +206253075a¹⁸x¹³ +265182525a¹⁷x¹⁴ +300540195a¹⁶x¹⁵ +300540195a¹⁵x¹⁶ +265182525a¹⁴x¹⁷ +206253075a¹³x¹⁸ +141120525a¹²x¹⁹ +84672315a¹¹x²⁰ +44352165a¹⁰x²¹ +20160075a⁹x²² +7888725a⁸x²³ +2629575a⁷x²⁴ +736281a⁶x²⁵ +169911a⁵x²⁶ +31465a⁴x²⁷ +4495a³x²⁸ +465a²x²⁹ +31ax³⁰ +x³¹
     
    PolynomialRemainder [(x+a)³¹, x²⁹-1] =
      465a² +a³¹ +(31a+31a³⁰)x +(1+465a²⁹)x² +4495a²⁸x³ +31465a²⁷x⁴ +169911a²⁶x⁵ +736281a²⁵x⁶ +2629575a²⁴x⁷ +7888725a²³x⁸ +20160075a²²x⁹ +44352165a²¹x¹⁰ +84672315a²⁰x¹¹ +141120525a¹⁹x¹² +206253075a¹⁸x¹³ +265182525a¹⁷x¹⁴ +300540195a¹⁶x¹⁵ +300540195a¹⁵x¹⁶ +265182525a¹⁴x¹⁷ +206253075a¹³x¹⁸ +141120525a¹²x¹⁹ +84672315a¹¹x²⁰ +44352165a¹⁰x²¹ +20160075a⁹x²² +7888725a⁸x²³ +2629575a⁷x²⁴ +736281a⁶x²⁵ +169911a⁵x²⁶ +31465a⁴x²⁷ +4495a³x²⁸
     
    (A) PolynomialMod [PolynomialRemainder [(x+a)³¹, x²⁹-1], 31] = a³¹+x²
     
    (B) PolynomialRemainder [x³¹+a, x²⁹-1] = a+x²
     
    (A) - (B) = a³¹+x² - (a+x²) = a³¹-a
     
    max =  $\left\lfloor \log _{2}(31){\sqrt {\varphi (29)}}\right\rfloor$  = 26
     
    {1³¹-1=0 (mod 31), 2³¹-2=0 (mod 31), 3³¹-3=0 (mod 31), ..., 26³¹-26=0 (mod 31)}

```
  Output prime.
    31 Must be Prime
```

Où PolynomialMod est une réduction modulo par terme du polynôme. ex. PolynomialMod[x+2x ² +3x ³ , 3] = x+2x ² +0x ³

Les références

Lectures complémentaires

Dietzfelbinger, Martin (2004). Test de primalité en temps polynomial. Des algorithmes randomisés à PRIMES est dans P . Notes de cours en informatique. 3000 . Berlin : Springer-Verlag . ISBN 3-540-40344-2. Zbl 1058.11070 .

Liens externes

Weisstein, Eric W. " AKS Primality Test " . MathWorld .
R. Crandall, Apple ACG et J. Papadopoulos (18 mars 2003) : sur la mise en œuvre des tests de primalité de classe AKS (PDF)
Article de Borneman, contenant des photos et des informations sur les trois scientifiques indiens (PDF)
Andrew Granville : Il est facile de déterminer si un nombre entier donné est premier
Les faits principaux : d'Euclide à AKS , par Scott Aaronson (PDF)
Le PRIMES est en P petite FAQ par Anton Stiglic
Citation au prix Gödel 2006
Citation au prix Fulkerson 2006
La ressource d'algorithme AKS "PRIMES in P"
Grime, Dr James. "Test infaillible pour les nombres premiers - Numberphile" (vidéo) . Brady Haran . [la vidéo décrit la relation temporelle exponentielle (1), qu'elle appelle AKS]

Languages

In other projects