PRIMES is in P
type: Item
instance of: scholarly article
title: PRIMES is in P
zbMATH Open document ID: 1071.11070
author: Manindra Agrawal
author: Neeraj Kayal
author: Nitin Saxena
published in: Annals of Mathematics. Second Series
publication date: 2005-04-18T00:00:00Z
review text: This is a historical breakthrough which solved the complexity theoretical question PRIMES (distinguishing prime numbers from composites) in {deterministic polynomial} time. The results excels not only by its importance but also by the elegance and simplicity of the arguments. Thus, the reader of this note is well advised to consult the original paper. If \(n\) is an integer to be tested for primality, all previous algorithms to this respect did use some version of the {Pocklington Lemma}, thus essentially seeking elements \(\alpha \in A(n)\) of {high order} in some group \(A(n)\) related to \(n\) -- for instance \(A(n) = \mathbb Z/n\mathbb Z\). Compared to this, the idea of AKS consists in considering a certain subgroup \[ G \subset A(n) = \left( \mathbb Z[\zeta]/\left(n \cdot \mathbb Z[\zeta] \right)\right)^{\times} \] as an abelian group with generators; here \(\zeta \in \mathbb C\) is a primitive \(r\)th root of unity and \(r\) is an integer satisfying the crucial size restriction \(\text{ord}_r(n) = \left(\# \langle n \bmod r \rangle\right) > \left(2 \log(n)\right)^2\). The test of AKS essentially consists in verifying that \[ (\zeta + a)^n \equiv \zeta^n + a \bmod n \mathbb Z[\zeta] \quad \text{ for } 1 \leq a \leq \ell \quad \text{and } \ell = \lfloor \varphi(r) \log(n) \rfloor.\tag{t} \] If these and some simple additional conditions on \(r, n\) are verified, then \(n\) is prime. The proof is based on the concept of {introspection}: let \(p\mid n\) be a possible prime divisor. A pair \(\left(\alpha, m\right), \alpha \in \mathbb Z[\zeta], m \in \mathbb Z\) with \((m, r) = 1\) is introspective (with respect to \(p\)) if \(\alpha^m \equiv \sigma_m(\alpha) \bmod p \mathbb Z[\zeta]\), with \(\sigma_m\) the Galois map given by \(\zeta \rightarrow \zeta^m\); introspection is multiplicative with respect to both components. Let \(A\) be the multiplicative group generated by \(\{a + \zeta : 1 \leq a \leq \ell \} \subset \mathbb Z[\zeta]\) and \( I = \{ p^i \cdot n^j : …
Mathematics Subject Classification ID: 11Y11
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 11A51
zbMATH DE Number: 2157791
zbMATH Keywords: historical breakthrough
zbMATH Keywords: solution of the complexity theoretical question PRIMES
zbMATH Keywords: distinguishing prime numbers from composites
zbMATH Keywords: deterministic polynomial time
MaRDI profile type: Publication
full work available at URL: annals.2004.160.781
OpenAlex ID: W2159341052
Wikidata QID: Q27018082
DOI: 10.4007/ANNALS.2004.160.781
reviewed by: Preda Mihaĭlescu
description: scientific article; zbMATH DE number 2157791