AKSprimaliteetittaus

AKSprimaliteetittaus, commonly understood as the AKS primality test, is a deterministic algorithm for determining whether a given integer n > 1 is prime in time polynomial in the number of digits of n. The method was introduced in 2002 by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, and it established that primality testing belongs to the complexity class P without relying on randomness. In Finnish contexts, the term AKSprimaliteetittaus is used to refer to this approach to primality testing.

The core idea of the AKS algorithm is to exploit properties of polynomials over rings modulo n. Rather than testing all potential divisors, the algorithm checks a family of polynomial congruences in the ring Z_n[X] with respect to a carefully chosen modulus X^r − 1 for some small integer r. If n behaves like a prime with respect to these polynomial relations, then n is prime; if any of the congruences fail, n is composite. The method proceeds through several stages to ensure correctness and to bound the required r and the size of the polynomial arithmetic involved. The overall guarantee is deterministic: for every input n, the algorithm either certifies primality or certifies compositeness in time polynomial in log n.

Although significant for theoretical computer science, AKSprimaliteetittaus is not the most practical primality test for very large numbers in everyday use, due to large polynomial factors and constants. In practice, probabilistic tests or specialized deterministic tests based on smaller bases are typically faster for cryptographic key generation, while AKS remains a landmark result proving that primality testing can be done deterministically in polynomial time.