Test de primalidad AKS

El test de primalidad AKS o algoritme AKS és un algoritme determinista que decidix en temps polinòmic si un número natural és primer o compost. Va ser dissenyat pels científics de computació Manindra Agrawal, Neeraj Kayal i Nitin Saxena de l'Institut tecnològic hindú de Kanpur en l'any 2002, i eventualment millorat per atres investigadors de l'àrea. El seu descobriment posa fi a un dels més grans problemes de la teoria de números i teoria de la complexitat computacional.

El problema de la primalidad

El problema de la primalidad consistix en averiguar si un número natural és primer o compost. Hi ha métodos molt antics per a resoldre este problema com la garbell de Eratóstenes (200 a. C.) o la divisió per tentativa, no obstant estos métodos resulten ineficaços quan es desija analisar números grans. Per a decidir la primalidad d'un número $n$, el garbell de Eratóstenes requerix un temps d'eixecució que és proporcional a $n$. Per un atre costat, la cantitat de dígits que es necessiten per a escriure tal número és proporcional a $\log (n)$.

En térmens de complexitat computacional, es diu que un método eficaç deuria requerir un temps polinòmic respecte a la cantitat de dígits. En este cas es desija tindre un algoritme que decidixca en un temps proporcional a ${\log }^{k}n$, si $n$ és un número primo o compost. Utilisant la notació O gran, esta proporció s'abrevia com $𝒪\left({\log }^{k}n\right)$. L'algoritme AKS és el primer algoritme que es coneix en estes característiques.

Història

Ans que Agrawal, Kayal i Saxena descrigueren el seu algoritme, es varen fer molts intents per resoldre el problema de la primalidad de manera eficient. En 1798 Gauss va sugerir que per a distinguir als número primo dels número compuesto no era necessari descompondre en factors a estos últims.

En 1636 Fermat va presentar el seu célebre menuda teorema de Fermat en el qual es va donar a conéixer una característica que complixen tots els número primo. Dit teorema afirma que quan $n$ és un número primo la següent congruència es complix:

$a^n\equiv a(\mathrm{mod}n)$

Esta teorema es va prendre com a fonament de varis tests de primalidad.

El test de primalidad de Miller-Rabin va ser presentat en 1980. L'algoritme sí funciona en temps polinomial, pero és provabiliste. Per eixemple, despuix de realisar el test de Miller-Rabin $k$ voltes, l'algoritme o be expedix un certificat de que el número és compost o be afirma que el número té una alta provabilitat de ser primer. El test de Miller-Rabin requerix un temps $𝒪\left(k{\log }^{2}n\right)$ en una provabilitat d'error de $1$ en $4^k$.

En 1983 Leonard Adleman, Carl Pomerance, i Robert Rumely varen crear un test de primalidad que sí és determinista pero el temps del qual d'eixecució era exponencial: ${(\log n)}^{𝒪(\log \log \log n)}$. El seu algoritme està basat en teoria molt complexa i una generalisació de la chicoteta teorema de Fermat cap als número entero en camps ciclotòmics. No obstant, este algoritme és tan ràpit que durant molt temps es varen usar variants per a trencar marques sobre comprovar la primalidad de números en més de mil sifres decimals. A pesar d'este gran guany, encara existia la pregunta de si existix algun algoritme que funcione en temps polinòmic i que fora determinista.

En 1992 varen sorgir una atra classe algoritmes basats en curves elíptiques, pero que tampoc eren determinista.

Finalment, en 1999 Manindra Agrawal va estudiar una variant de la chicoteta teorema de Fermat. Dos anys despuix, ell i els seus dos estudiants de el IITK varen començar a analisar totes les propietats d'esta variant fins que varen trobar una caracterisació completa dels número primo. En base en esta caracterisació, en l'any 2002 varen presentar el seu algoritme en l'artícul PRIMES is in P.