Fact-checked by Grok 2 weeks ago

AKS primality test

The AKS primality test is a deterministic algorithm for determining whether a given natural number n is prime, developed by Indian computer scientists Manindra Agrawal, Neeraj Kayal, and Nitin Saxena at the Indian Institute of Technology Kanpur.^[1] Announced in August 2002 and formally published in 2004, it provides an unconditional polynomial-time solution to primality testing, proving that the decision problem PRIMES belongs to the complexity class P.^[1] The test avoids probabilistic assumptions and works for all inputs, representing a landmark achievement in computational number theory.^[2] The algorithm begins by checking if n is a perfect power (i.e., n = a^b for integers a > 1 and b > 1), outputting "composite" if so; otherwise, it finds the smallest integer r such that the multiplicative order of n modulo r exceeds (log₂ n)² and gcd(n, r) = 1.^[3] It then verifies that n has no small prime factors up to r; if n ≤ r, it outputs "prime". Otherwise, for a from 1 to ⌊√φ(r) log₂ n⌋ (where φ is Euler's totient function), it checks the polynomial congruence (x + a)ⁿ ≡ xⁿ + a (mod n, x^r − 1) in the ring ℤ/nℤ[x] / (x^r − 1).^[3] If all checks pass, it outputs "prime"; failure at any step indicates "composite".^[3] This approach leverages extensions of Fermat's Little Theorem to polynomial rings and properties of cyclic groups to distinguish primes from composites.^[2] Historically, primality testing evolved from trial division and sieve methods to more efficient but conditional or probabilistic algorithms, such as the Miller-Rabin test introduced in 1976, which runs in expected subexponential time but requires randomness for certainty.^[3] The AKS test emerged from undergraduate research theses at IIT Kanpur in 2001–2002, building on earlier work exploring binomial expansions modulo composite numbers.^[2] Its proof of correctness relies on group-theoretic arguments showing that composites fail the key congruence due to non-trivial factorizations, while primes satisfy it by field properties.^[3] The original AKS implementation has a time complexity of \tilde{O}(\log^{15/2} *n*), where the tilde hides polylogarithmic factors and n is the input number; subsequent refinements by researchers like Hendrik Lenstra and Carl Pomerance reduced this to \tilde{O}(\log^6 *n*).^[1]^[2] Despite its theoretical elegance, the test's high constant factors make it impractical for large n—for example, testing a 22-digit prime can take over an hour—leading to its limited use outside academia, where probabilistic tests like Miller-Rabin dominate cryptographic applications.^[3] Nonetheless, AKS has inspired further advancements in deterministic testing and remains a cornerstone for understanding the boundaries of P.^[2]

Overview and Significance

Overview

The AKS primality test is a deterministic algorithm created by Indian computer scientists Manindra Agrawal, Neeraj Kayal, and Nitin Saxena for determining the primality of any given integer n in polynomial time relative to the number of digits in n.^[4] The algorithm provides a rigorous proof of primality without relying on probabilistic methods or unproven conjectures, marking a significant advancement in computational number theory.^[1] Announced in August 2002 via a preprint and formally published in 2004 in the Annals of Mathematics under the title "PRIMES is in P," the work demonstrates that testing primality is solvable in polynomial time using a general, unconditional, and deterministic procedure.^[4] This was the first such algorithm to achieve these properties without depending on hypotheses like the Generalized Riemann Hypothesis, which had underpinned earlier deterministic tests.^[1] In recognition of their achievement, Agrawal, Kayal, and Saxena were awarded the 2006 Gödel Prize by the Association for Computing Machinery and the European Association for Theoretical Computer Science, as well as the 2006 Fulkerson Prize by the American Mathematical Society and the Mathematical Programming Society.^[5] Theoretically, the AKS test confirmed that the PRIMES decision problem resides in the complexity class P, affirming primality testing as a tractable computational task.^[4]

Importance in Number Theory

The AKS primality test represents a landmark achievement in computational complexity theory by providing the first unconditional deterministic polynomial-time algorithm for determining whether a given integer is prime, thereby proving that the PRIMES decision problem belongs to the complexity class P.^[1] This resolved a longstanding open question dating back decades, as prior deterministic algorithms, such as the Adleman-Pomerance-Rumely test, achieved only subexponential time complexity, while randomized methods like the Solovay-Strassen and Miller-Rabin tests offered polynomial time but with probabilistic error bounds.^[1] The test's reliance on elementary algebraic techniques, including a generalization of Fermat's Little Theorem to polynomials, underscores its theoretical elegance and broadens the understanding of prime distribution properties in number theory.^[1] Unlike probabilistic primality tests such as Miller-Rabin, which can produce false positives with small but nonzero probability, or deterministic tests conditioned on unproven hypotheses like the Generalized Riemann Hypothesis (e.g., certain variants of Miller's test), the AKS algorithm operates without any assumptions, guaranteeing correctness for all inputs.^[6] It contrasts sharply with special-case deterministic tests like the Lucas-Lehmer algorithm, which efficiently verifies Mersenne primes but applies only to numbers of the form $2^p - 1, and faster probabilistic alternatives such as the Baillie-PSW test or the Elliptic Curve Primality Proving (ECPP) method, which, while practical, lack AKS's unconditional certainty—ECPP, for instance, provides proofs but relies on elliptic curve machinery and is not proven polynomial-time in the worst case.^[6] Although AKS's running time is polynomial, its high exponent (initially O(\log^{10.5} n), later refined) and large constants render it vastly slower than these alternatives in practice, earning it the informal designation of a "galactic algorithm"—theoretically groundbreaking but impractical for numbers beyond modest sizes.^[6] In cryptography, the AKS test enables the reliable, unconditional generation and verification of large primes essential for protocols like RSA, where probabilistic tests have traditionally been used due to speed, but AKS provides a theoretical foundation for error-free prime selection without relying on randomness or unproven conjectures.^[7] However, its computational demands preclude practical deployment in key generation, where Miller-Rabin variants suffice with negligible error rates for cryptographic sizes.^[7] Despite this, the algorithm's existence assures that prime-based cryptographic primitives can, in principle, be implemented deterministically in polynomial time, bolstering confidence in the security models of systems dependent on prime factorization hardness. Beyond primality, the AKS test's success highlights advances in deterministic algorithms for number-theoretic problems, contrasting with integer factorization, which remains computationally infeasible and is presumed outside P, forming the basis for public-key cryptography's security.^[7] It has inspired subsequent optimizations and variants that reduce its time complexity while preserving determinism, influencing research in algebraic number theory and computational complexity by demonstrating how polynomial identities can yield breakthroughs in seemingly intractable domains.^[6]

Mathematical Foundations

Polynomial Identities and Rings

The AKS primality test relies on fundamental polynomial identities derived from the binomial theorem, particularly in the context of modular arithmetic over polynomial rings. For a prime p, the binomial expansion of (x + a)^p simplifies significantly: all intermediate binomial coefficients \binom{p}{k} for $1 \leq k \leq p-1 are divisible by p, yielding the congruence (x + a)^p \equiv x^p + a^p \pmod{p} in the polynomial ring (\mathbb{Z}/p\mathbb{Z}).^[8] This identity, known as the Freshman's dream, extends the scalar case of Fermat's Little Theorem (a^p \equiv a \pmod{p}) to polynomials and highlights how primality enforces a collapse in the binomial structure modulo p.^[4] To adapt this for testing arbitrary n \geq 2, the AKS framework performs computations in the quotient ring R = (\mathbb{Z}/n\mathbb{Z}) / (x^r - 1), where r is a parameter chosen such that the multiplicative order of n modulo r exceeds (\log_2 n)^2 (detailed in subsequent sections). Elements of this ring are polynomials of degree less than r with coefficients in \mathbb{Z}/n\mathbb{Z}, and arithmetic involves reducing products modulo x^r - 1 (effectively treating x^r \equiv 1) and coefficients modulo n. The core verification checks whether (x + a)^n \equiv x^n + a \pmod{(x^r - 1, n)} for several integers a coprime to n; this congruence means the polynomial (x + a)^n - x^n - a has all coefficients divisible by n after reduction in R. For prime n, this identity holds universally for all a, generalizing Fermat's Little Theorem to the polynomial setting, while failure for any a signals compositeness.^[8]^[4] The structure of the ring R is informed by the factorization of x^r - 1 = \prod_{d \mid r} \Phi_d(x), where \Phi_d(x) are the cyclotomic polynomials, irreducible over the integers and defining the minimal polynomials for primitive d-th roots of unity. In the AKS context, this decomposition ensures that the ring decomposes into factors corresponding to these cyclotomic components, which helps isolate prime-like behavior by leveraging the order condition on r to prevent unwanted relations that could mimic the identity for composites. The key algebraic insight is that, for prime n, the polynomial (x + a)^n - x^n - a is divisible by n in \mathbb{Z}, but the modular reduction modulo x^r - 1 allows efficient verification without full expansion.^[8]^[4]

Order in Modular Arithmetic

In modular arithmetic, the multiplicative order of an integer n modulo r, denoted \operatorname{ord}_r(n) or o_r(n), is defined as the smallest positive integer k such that n^k \equiv 1 \pmod{r}, provided that \gcd(r, n) = 1.^[1] This concept arises from the structure of the multiplicative group of integers modulo r, where the order divides Euler's totient function \phi(r), satisfying \operatorname{ord}_r(n) \leq \phi(r) < r.^[1] Within the AKS primality test, the multiplicative order plays a crucial role in selecting an appropriate parameter r during the algorithm's second step. Specifically, the test requires finding the smallest integer r \geq 2 such that \gcd(r, n) = 1 and \operatorname{ord}_r(n) > (\log_2 n)^2, where \log_2 n is the base-2 logarithm.^[1] This condition ensures that the subsequent polynomial congruences in the ring \mathbb{Z}/n\mathbb{Z} behave in a way that distinguishes primes from composites, as the order bound prevents premature cyclicity in the powers of n modulo r.^[1] A key result guarantees the existence of such an r \leq \max\{3, \lfloor (\log_2 n)^5 \rfloor\} if n is prime, allowing the algorithm to proceed efficiently.^[1] To compute this order for candidate values of r, the algorithm checks whether n^k \equiv 1 \pmod{r} for any k = 1, 2, \dots, (\log_2 n)^2; if no such k exists, then \operatorname{ord}_r(n) > (\log_2 n)^2.^[1] This verification is performed sequentially starting from r = 2, skipping any r where \gcd(r, n) > 1, which immediately indicates that n is composite since r is small and reveals a nontrivial factor.^[1] The process resembles a sieve over small candidates, testing each potential r (often primes initially, though not required) up to the logarithmic bound, ensuring the selected r is of size approximately O((\log_2 n)^5).^[1] If no suitable r satisfying \gcd(r, n) = 1 and \operatorname{ord}_r(n) > (\log_2 n)^2 exists within the bound, the algorithm concludes that n is composite, as the existence lemma holds only for primes.^[1] This order-based selection thus serves as both a preprocessing filter for compositeness and a foundational parameter for the test's algebraic verification.

Historical Development

Discovery and Original Publication

The AKS primality test was developed by Manindra Agrawal, a professor in the Department of Computer Science and Engineering at the Indian Institute of Technology (IIT) Kanpur, along with two of his undergraduate students, Neeraj Kayal and Nitin Saxena, who were completing their BTech degrees.^[1]^[9] The work originated as a research project for Kayal and Saxena under Agrawal's supervision during their final year, drawing inspiration from Agrawal's prior investigations into connections between the Riemann hypothesis and efficient primality testing methods.^[10]^[1] The algorithm was conceived between 2001 and 2002, building directly on the foundational 1982 result by Leonard Adleman, Carl Pomerance, and Ronald Rumely, which provided a subexponential-time primality test conditional on the generalized Riemann hypothesis (GRH).^[1] The AKS test sought to eliminate this GRH dependency, achieving an unconditional deterministic polynomial-time solution to the primality testing problem. It was first announced on August 6, 2002, through a preprint posted on the IIT Kanpur website, titled "PRIMES is in P."^[11] The full paper, co-authored by Agrawal, Kayal, and Saxena, was submitted to the Annals of Mathematics on January 24, 2003, and published in 2004.^[1] In the initial announcement, the algorithm's time complexity was stated as \tilde{O}(\log^{12} n), where n is the number to be tested, though subsequent refinements in the published version improved this bound.^[1] The discovery received immediate international acclaim as a major breakthrough in computational number theory, with coverage in outlets like The New York Times highlighting its implications for cryptography and complexity theory. The work earned the trio the 2006 Gödel Prize from ACM SIGACT and EATCS, among other accolades such as the 2003 Fulkerson Prize.^[12]^[9] Independent verification followed swiftly; in 2003, cryptographer Daniel J. Bernstein provided a detailed exposition and confirmation of the algorithm's correctness in his paper "Proving Primality After Agrawal-Kayal-Saxena."^[13] As a landmark achievement from an Indian academic institution, the AKS test underscored IIT Kanpur's contributions to theoretical computer science and elevated the global profile of Indian research in algorithms.^[9]^[14]

Optimizations and Variants

Following the publication of the original AKS algorithm, Agrawal, Kayal, and Saxena refined it in 2004, reducing the time complexity from the initial O~(log^{12} n) to O~(log^{10.5} n) by optimizing the search for the parameter r and incorporating bounds on its size.^[1] In 2005, Lenstra and Pomerance further improved this to O~(log^6 n) through a variant that replaces the cyclotomic polynomial with Gaussian periods, allowing for a smaller effective r while maintaining deterministic polynomial-time guarantees.^[15] Key optimizations to the AKS framework focus on two main areas: tighter bounds on the multiplier r to reduce the number of polynomial evaluations and the integration of fast multiplication techniques, such as the Fast Fourier Transform (FFT), to accelerate arithmetic operations in the finite field rings. These changes lower the exponent in the logarithmic complexity without altering the core identity-based verification. For instance, selecting r on the order of O(log^2 n) via improved sieving or density arguments minimizes the iteration count in the main loop.^[1] Variants of the AKS test include practical implementations with tweaks for efficiency, such as Bernstein's 2003 approach, which incorporates randomized elements to achieve expected quartic time (O~(log^4 n)) while preserving correctness through multiple runs, making it more viable for numbers up to moderate sizes. Quasi-deterministic versions, assuming access to a root-finding oracle for efficiently locating suitable r values in the multiplicative group, can attain O~(log^4 n) complexity by bypassing the exhaustive search phase.^[1] Recent developments from 2020 to 2025 highlight AKS's role in hybrid primality testing frameworks, where it serves as a deterministic verifier after probabilistic sieves like Miller-Rabin, as noted in 2023 comparative analyses that emphasize its theoretical purity in combined pipelines for cryptographic applications.^[16] A notable 2025 contribution on arXiv introduces a circulant matrix-based primality test inspired by AKS's cyclotomic constructions, leveraging eigenvalue computations in matrix algebras to achieve comparable polynomial bounds of O~(log^6 n) while offering potential for parallelization.^[17] Open-source implementations of AKS and its variants are available in systems like SageMath, where user-contributed code enables direct execution, and on Rosetta Code, which provides task-specific examples across multiple programming languages for educational and benchmarking purposes. Despite these resources, AKS remains rarely used in practice due to its slower performance compared to heuristic methods for numbers beyond about 20-30 digits.^[18]^[19] A limitation arose from Agrawal's 2003 conjecture, which posited the existence of r with order exceeding (log n)^2 in O~(log^3 n) time, potentially yielding O~(log^3 n) overall complexity; this was disproven through constructions showing counterexamples via generalized Carmichael numbers. The current best theoretical deterministic complexity for AKS variants stands at O~(log^6 n).^[20]^[15]

The Algorithm

Preliminary Tests

The preliminary tests in the AKS primality test serve to efficiently eliminate trivially composite numbers, manage small inputs, and determine a crucial parameter r for the subsequent core procedure, all while running in polynomial time relative to \log n. These steps collectively require \tilde{O}(\log^7 n) time, dominated by the search for r, ensuring that only potentially prime candidates proceed to the more demanding verification.^[1] The initial check determines if n is a perfect power, meaning n = a^b for integers a > 1 and b \geq 2. If such a and b exist, n is composite, and the algorithm outputs "COMPOSITE". To perform this test, exponents b from 2 up to \lfloor \log_2 n \rfloor are examined; for each b, the b-th root of n is approximated using binary search or Newton's method to find candidate a = \lceil n^{1/b} \rceil, followed by verification that a^b = n via fast exponentiation. This step rules out numbers like powers of primes or composites with repeated factors and takes \tilde{O}(\log^3 n) time with optimized arithmetic.^[1]^[21] For small values of n, the algorithm directly assesses primality after basic factor checks. Specifically, if n \leq 2, n = 2 is prime while n = 1 is neither (though inputs are typically n > 1); if n = 3, it is prime. More generally, after locating the parameter r and performing trial division up to r (detailed below), if n \leq r, n is output as "PRIME", as any composite n in this range would have been detected by the divisibility tests up to r. This handles inputs up to roughly $10^6 in practice, where r bounds are small enough for exhaustive verification.^[1]^[22] The most involved preliminary step identifies the smallest integer r such that the multiplicative order of n modulo r, denoted \ord_r(n), satisfies \ord_r(n) > (\log_2 n)^2 and \gcd(r, n) = 1. The order \ord_r(n) is the smallest positive integer k for which n^k \equiv 1 \pmod{r}. To find r, candidates begin at 2 and increment sequentially; for each candidate, \gcd(r, n) is computed first—if greater than 1, n is composite (as perfect powers were already excluded) and the algorithm outputs "COMPOSITE". If \gcd(r, n) = 1, the order is computed by testing the divisors of \phi(r) (Euler's totient) via repeated modular exponentiation. Number-theoretic results guarantee such an r \leq O(\log^5 n) exists for prime n, limiting the search to O(\log^5 n) candidates, with each order computation taking \tilde{O}(\log^2 n) time, for a total of \tilde{O}(\log^7 n) time. This parameter r is essential for the ring in which the core polynomial identities are verified.^[1]^[21] After finding r, a trial division step checks for small prime factors: for each integer a from 2 to r, compute \gcd(a, n); if $1 < \gcd(a, n) < n, output "COMPOSITE". This eliminates composites with any prime factors ≤ r and takes \tilde{O}(\log^6 n) time. If n \leq r at this point, output "PRIME".^[1]^[21]

Core Verification Procedure

After the preliminary tests confirm that the number n passes initial checks for small factors and suitable parameters, the core verification procedure begins by selecting the maximum value for the parameter a, defined as a_{\max} = \lfloor \sqrt{\phi(r) \log_2 n} \rfloor, where r is the order parameter chosen earlier and \phi denotes Euler's totient function.^[1] The primary computational step involves iterating over each integer a from 1 to a_{\max} and verifying the polynomial congruence (x + a)^n \equiv x^n + a \pmod{x^r - 1, n} in the ring (\mathbb{Z}/n\mathbb{Z}).^[1] This check is performed by computing the left-hand side via repeated squaring for the exponentiation, with intermediate results reduced modulo x^r - 1 to keep polynomial degrees below r, and all coefficients taken modulo n.^[1] Each individual verification requires \tilde{O}(r^2 \log n) operations in basic implementations due to polynomial multiplications and modular reductions during exponentiation.^[1] The procedure conducts O(\sqrt{r \log n}) such checks, which approximates to \tilde{O}(\log^3 n) given the bounds on r, making this the dominant runtime component of the algorithm.^[1] In the ring arithmetic, all polynomials are represented with degrees less than r and coefficients in \{0, 1, \dots, n-1\}, ensuring efficient modular operations.^[1] If the congruence fails for any value of a, the algorithm immediately outputs that n is composite.^[1] Conversely, if all checks succeed, it concludes that n is prime.^[1]

Worked Example for n=31

To illustrate the application of the AKS primality test, consider the input integer n = 31.^[1] The algorithm begins with preliminary checks. First, verify whether n is a perfect power, i.e., if there exist integers a \geq 2 and b \geq 2 such that n = a^b. Since \log_2 31 \approx 4.95, test exponents up to 4: the square root of 31 is approximately 5.57 (not an integer), the cube root is approximately 3.14 (not an integer), and higher roots yield even smaller non-integer values. Thus, 31 is not a perfect power.^[23]^[1] Next, find the smallest integer r such that the multiplicative order of n modulo r, denoted \mathrm{ord}_r(n), exceeds (\log_2 n)^2 \approx 24.5, and \gcd(n, r) = 1. Testing small values of r shows that r = 29 satisfies this condition, with \mathrm{ord}_{29}(31) = 28 > 24.5.^[23]^[1] Proceed to trial division: for each a = 2 to r = 29, compute \gcd(a, 31). Since 31 is greater than 29 and prime, all such gcds equal 1, so no nontrivial factors are found. As n = 31 > r = 29, continue to the core verification.^[23]^[1] For the core procedure, compute the maximum a as a_{\max} = \lfloor \sqrt{\phi(29) \log_2 31} \rfloor, where \phi(29) = 28 is Euler's totient function. This yields \sqrt{28 \times 4.95} \approx \sqrt{138.6} \approx 11.78, so a_{\max} = 11. For each a = 1 to 11, verify the polynomial identity (x + a)^{31} \equiv x^{31} + a \pmod{x^{29} - 1, 31} in the ring (\mathbb{Z}/31\mathbb{Z}) / (x^{29} - 1). These computations involve polynomial exponentiation, typically via repeated squaring, followed by reduction modulo x^{29} - 1 and coefficients modulo 31. (Note: for primes, the identity holds for all a coprime to n, but the test only requires checking up to a_max.)^[23]^[1] As a representative case, consider a = 1. Expand (x + 1)^{31} using the binomial theorem: (x + 1)^{31} = \sum_{k=0}^{31} \binom{31}{k} x^k. Modulo 31 (a prime), the binomial coefficients \binom{31}{k} \equiv 0 \pmod{31} for $1 < k < 31, so (x + 1)^{31} \equiv x^{31} + 1 \pmod{31}. Now reduce this polynomial modulo x^{29} - 1: x^{31} = x^{2} \cdot x^{29} \equiv x^{2} \cdot 1 = x^{2} \pmod{x^{29} - 1}, yielding x^{2} + 1. The right side x^{31} + 1 reduces similarly to x^{2} + 1 \pmod{x^{29} - 1, 31}, confirming the identity holds. Analogous computations (via binomial expansion or efficient squaring methods) verify the identity for all a = 2 to 11.^[23]^[1] Since all checks pass, the algorithm outputs that 31 is prime. For such a small n, the process is feasible manually, demonstrating the practicality of the \tilde{O}(\log^{10.5} n) time complexity in the original formulation, which evaluates to a small constant here.^[1]

Correctness and Analysis

Proof of Validity

The proof of validity for the AKS primality test demonstrates that the algorithm unequivocally distinguishes primes from composites for any integer n > 1. If n is prime, all steps of the algorithm succeed, leveraging a generalization of Fermat's Little Theorem and properties of the binomial theorem. In particular, the core polynomial congruence (x + a)^n \equiv x^n + a \pmod{x^r - 1, n} holds for all relevant a, as the intermediate binomial terms vanish modulo n due to Fermat's Little Theorem, and the cyclotomic structure of x^r - 1 preserves the identity in the quotient ring.^[1] The preliminary steps (1 through 4) effectively detect compositeness in cases of prime powers, small prime factors, or insufficient multiplicative order o_r(n) \leq (\log n)^2. These checks eliminate trivial composites, ensuring that any n advancing to the core verification is either prime or a composite without these properties, with r chosen such that o_r(n) > (\log n)^2 to enforce non-trivial behavior in the modular arithmetic.^[1] The main theorem underpinning correctness states that if n > 1 is composite and not a prime power, then there exists some a \leq a_{\max} (where a_{\max} = 2\sqrt{r \log n}) such that (x + a)^n \not\equiv x^n + a \pmod{x^r - 1, n}. This incongruence occurs because, in the ring \mathbb{Z}/n\mathbb{Z}/(x^r - 1), the composite n introduces distinct roots corresponding to the factors of x^r - 1, disrupting the polynomial identity that holds seamlessly for primes. The multiplicative order condition on r guarantees that the polynomial does not factor in a way that trivially satisfies the congruence, forcing a detectable failure for composites.^[1] The proof proceeds via contradiction: suppose n is composite yet passes all steps, including the polynomial checks for every a \leq a_{\max}. This assumption implies n must mimic prime behavior in an algebraic group structure derived from the ring, but it leads to an inconsistency in group orders. Specifically, the setup would require the multiplicative group modulo n to exceed bounds imposed by the number of distinct prime factors of n, which is at most O(\log n / \log \log n). The preliminaries already rule out prime powers, collapsing the contradiction to affirm that n must be prime.^[1] This validity relies on foundational number-theoretic results, including bounds on the smallest prime in residue classes (to select suitable r) and the irreducibility of cyclotomic polynomials, which ensure the ring's structure amplifies differences between primes and composites.^[1]

Time Complexity and Practicality

The original AKS primality test, as announced in 2002, achieves a time complexity of \tilde{O}(\log^{12} n), arising primarily from the naive search for a suitable parameter r up to \log^5 n and the use of standard polynomial exponentiation in the verification step.^[24] Subsequent refinements in the 2004 journal version reduced this to \tilde{O}(\log^{10.5} n) through more careful analysis of the parameter bounds. Further improvements in the 2004 journal version yielded a bound of \tilde{O}(\log^{7.5} n) through refined parameter analysis.^[1] A significant advancement came in 2011 with the work of Lenstra and Pomerance, who optimized the selection of r using Gaussian periods, achieving an unconditional deterministic time complexity of \tilde{O}(\log^6 n).^[25] In this variant, the search for r requires \tilde{O}(\log^6 n) time, while the core verification involves approximately \tilde{O}(\log^{2.5} n) iterations, each performing polynomial operations in \tilde{O}(\log^3 n) time via FFT-based multiplication.^[25] Despite these theoretical improvements, the AKS test remains impractical for real-world applications due to large hidden constants and the overhead of deterministic verification. For numbers near $2^{64} (around 20 decimal digits), implementations on modern hardware can take days to complete, whereas probabilistic tests like Miller-Rabin finish in milliseconds with negligible error probability.^[24] Existing implementations are largely theoretical or used for research verification of small to medium-sized numbers, with no widespread adoption in cryptographic or computational libraries.^[26] Looking ahead, conditional improvements under conjectures such as the existence of suitable primes in short intervals could potentially reduce the complexity to \tilde{O}(\log^3 n), though current unconditional variants remain too slow for practical use beyond theoretical demonstrations.^[27] Recent 2025 developments, including matrix-inspired approaches using circulant eigenvalue structures, offer promising theoretical connections to cyclotomic fields but do not yet surpass established methods in efficiency or practicality.

References

[1]
[PDF] PRIMES is in P - Microsoft
By Manindra Agrawal, Neeraj Kayal, and Nitin Saxena*. Abstract. We present ... Sudan, Notes on primality test and analysis of AKS,. Private communication ...Missing: original | Show results with:original
[2]
http://www.dms.umontreal.ca/~andrew/PDF/Bulletin04.pdf
[3]
[PDF] Deterministic Primality Testing - arXiv
Nov 15, 2013 · AKS algorithm, which could test whether a given number is prime or compos- ite in polynomial time. This project is an attempt at ...
[4]
PRIMES is in P - Annals of Mathematics - Princeton University
PRIMES is in P. Pages 781-793 from Volume 160 (2004), Issue 2 by Manindra Agrawal, Neeraj Kayal, Nitin Saxena. Abstract. We present an unconditional ...
[5]
2006 Fulkerson Prize Citation - Mathematical Optimization Society
Testing whether an integer is a prime number is one of the most fundamental computational and mathematical problems.Missing: AKS | Show results with:AKS
[6]
[PDF] Some Algorithms for Primality Testing
AKS is not a practical algorithm. ECPP is much faster. Rabin-Miller is even faster, at the price of a minute probability of error. A combination ...
[7]
[PDF] Notes on Primality Testing And Public Key Cryptography Part 1
2002, it has been known that primality testing can be done in polynomial time. This result is due to Agrawal, Kayal, and Saxena and known as the AKS test solved ...<|separator|>
[8]
[PDF] PRIMES is in P - Computer Science | UC Davis Engineering
Aug 6, 2002 · PRIMES is in P. Manindra Agrawal, Neeraj Kayal and Nitin Saxena*. Department of Computer Science & Engineering. Indian Institute of Technology ...
[9]
New Method Said to Solve Key Problem In Math - The New York Times
Aug 8, 2002 · So-called primality testing plays a crucial role in the widely used RSA algorithm, whose security relies on the difficulty of finding a number's ...
[10]
[PDF] Primality and Identity Testing via Chinese Remaindering
Feb 21, 2003 · Abstract. We give a simple and new randomized primality testing algorithm by reducing primality testing for number n to testing if a ...
[11]
https://www.cse.iitk.ac.in/news/primality.ps
[12]
[PDF] Draft. PROVING PRIMALITY AFTER AGRAWAL-KAYAL-SAXENA ...
The original Agrawal-Kayal-Saxena paper used an extremely crude lower bound for the number of images, and compensated by choosing r and W unnecessarily large.
[13]
Award for algorithm - Frontline - The Hindu
Dec 20, 2002 · In association with his two students, Neeraj Kayal and Nitin Saxena, Agrawal discovered an algorithm that can test for the primality ... (AKS) ...
[14]
[PDF] Primality testing with Gaussian periods H. W. Lenstra, Jr. and Carl ...
In this paper we show how one may replace the choice of f(x) as a cyclotomic polynomial in Theorem AKS with an arbitrary integer monic polynomial f(x) of degree.Missing: optimizations | Show results with:optimizations
[15]
[PDF] Improving AKS Algorithm. Proving the Simplicity of Integers
Jan 1, 2023 · The AKS algorithm, derived from a theorem, is improved to determine integer simplicity by reducing computational complexity. It has two phases.
[16]
Implementing the AKS primality test - ASKSAGE: Sage Q&A Forum
Nov 14, 2018 · I am implementing the infamous AKS deterministic primality test using SageMath. My code is as follows:
[17]
AKS test for primes - Rosetta Code
The AKS algorithm for testing whether a number is prime is a polynomial-time algorithm based on an elementary theorem about Pascal triangles.Missing: galactic | Show results with:galactic
[18]
[PDF] A note on Agrawal conjecture Roman Popovych 1 Introduction ...
Abstract. We prove that Lenstra proposition suggesting existence of many counterexamples to Agrawal conjecture is true in a more general case.Missing: disproven | Show results with:disproven
[19]
[PDF] An Introduction to the AKS Primality Test Andreas Klappenecker ...
Sep 4, 2002 · The purpose of these lecture notes is to give a short overview of this primality test, and to provide a guide to the related literature.Missing: original | Show results with:original
[20]
[PDF] WXML Final Report: AKS Primality Test
In 2002, Agrawal, Kayal, and. Saxena published the first deterministic primality test that also runs in poly- nomial time relative to the binary ...
[21]
[PDF] Some Methods of Primality Testing - Lakehead University
... r = 29. Since. (a,31) = 1 for all 1 ≤ a ≤ r = 29, we cannot conclude that 31 is composite in step (3), and since n = 31 ... as in the AKS test. Though some ...
[22]
[PDF] An Empirical Study towards Refining the AKS Primality Testing ...
The AKS (Agrawal-Kayal-Saxena) algorithm is the first ever deterministic polynomial- time primality-proving algorithm whose asymptotic run time complexity is O( ...
[23]
[PDF] IIT Kharagpur 1 Test for prime III (Agrawal, Kayal, and Saxena)
[DGB] Proving Primality after Agrawal, Kayal and Saxena, by D G Bernstein, preprint http://cr.yp.to/papers#aks, January 25, 2003. [MD] Primality Testing in ...
[24]
[PDF] Primality testing with Gaussian periods H. W. Lenstra jr. and Carl ...
The same result, with 21/2 in the place of 6, was proved by Agrawal, Kayal, and Saxena. Our algorithm follows the same pattern as theirs, performing.Missing: complexity | Show results with:complexity
[25]
https://www.math.dartmouth.edu/~carlp/aks041411.pdf
[26]
[PDF] Some remarks and questions about the AKS algorithm and related ...
They also stated conjecture which, if true, enables to make a deterministic primality-testing algorithm running in ˜O(log3 n) time. In second section we ask ...