PRIMES is in P

By Manindra Agrawal, Neeraj Kayal, Nitin Saxena. 2004

1,210 citations recorded by the source corpus.

Subfields: Algebra and Number Theory, Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/59d55a802b47fdbdb3078f43e52f536d42a771a7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algebra and Number Theory

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Decision Theory with Resource-Bounded Agents (2013, background): “While primality testing is now known to be in polynomial time [1], and there are computationally-efficient randomized algorithms that that give the correct answer with extremely high probability [16, 23], we can assume that the agent has no access to a computer.”
An Uninstantiable Random-Oracle-Model Scheme for a Hybrid-Encryption Problem (2004, methodology): “implemented in polynomial-time based on standard facts from computational number theory, and even deterministically, given the existence of polynomial-time primality tests [ 1 ].”
The status of the P versus NP problem (2009, background): “In 2004 we discovered we don’t need randomness at all to efficiently determine if a number is prime [3].”
The Algorithm Design Manual (2020, background): “[AKS04] M. Agrawal, N. Kayal, and N. Saxena.”
Delegating computation: interactive proofs for muggles (2008, methodology): “Then, L has a public-coin interactive proof with perfect completeness and soundness 1/2 where: the prover’s running time is poly(S(n)); the verifier runs in time (n + d(n)) · With regard to the Mersenne Prime example, we note that current methods for verifying the output of polynomial time determini”
Quantum Computation and Information (2006, background): “NPol [76, 67] P ⊆ H H H H H H H H H H H H H H H H H H H H ⊆ X X t t t t t t t t t t t t t t t t t t t t t Primality [8] Figure 1.”
History of Interactive Theorem Proving (2014, background): “Though primality testing was much later established to be in P [Agrawal et al., 2004], Pratt’s result retains its interest as an effective way of certifying primality.”
Arithmetic Circuits: A survey of recent results and open questions (2010, methodology): “A partial list of algorithms include Cooley and Tukey’s FFT algorithm [38], fast matrix multiplication [39] (and the new algorithmic approach of [36, 37]), efficient polynomial factorization (see the surveys [72, 146] and the recent [84]) and the deterministic primality testing algorithm of [4].”
Quantum computing, postselection, and probabilistic polynomial-time (2004, background): “[10] succeeded with a quite (2)A few examples are primality testing in deterministic polynomial time [7], undirected graph connectivity in log-space [30], and inapproximability of the 3-SAT problem unless P = NP [32].”
How Language Model Hallucinations Can Snowball (2023, neutral): “Primality testing was shown to be in P (Agrawal et al., 2004) but cannot be in TC 0 unless it is also in L ; i.e., any n can be factored with O (log log n ) bits of overhead.”
Linear degree extractors and the inapproximability of max clique and chromatic number (2006, neutral): “Under Cramer’s conjecture, the deterministic primality test [1] implies that Prime(n) = poly(n).”
Measuring universal intelligence: Towards an anytime intelligence test (2010, background): “We now know it is a polynomial problem (it can be solved in polynomial time with respect to the number whose primality we want to check) [47].”
Modern Cryptography: Theory and Practice (2003, background): “EC_Multiply(P, 14) = EC_exp(P + P, 7) (in step 2) = [2]P + EC_Multiply([2]P + [2]P, 3) (in step 3) = [2]P + [4]P + EC_Multiply([4]P + [4]P, 1) (in step 3) = [2]P + [4]P + [8]P + EC_Multiply([8]P + [8]P, 0) (in step 3)”
Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds (2003, methodology): “[2] M. Agrawal, N. Kayal, and N. Saxena.”
I Don't Want to Think About it Now: Decision Theory with Costly Computation (2010, background): “References Agrawal, M., N. Keyal, and N. Saxena (2004).”
Advances in quantum cryptography (2019, neutral): “[25] M.”