PRIMES is in P
From MaRDI portal
Publication:1772458
DOI10.4007/annals.2004.160.781zbMath1071.11070OpenAlexW2159341052WikidataQ27018082 ScholiaQ27018082MaRDI QIDQ1772458
Nitin Saxena, Manindra Agrawal, Neeraj Kayal
Publication date: 18 April 2005
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4007/annals.2004.160.781
deterministic polynomial timedistinguishing prime numbers from compositeshistorical breakthroughsolution of the complexity theoretical question PRIMES
Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Factorization; primality (11A51) Primality (11Y11)
Related Items (only showing first 100 items - show all)
TFNP: An Update ⋮ Generating random factored Gaussian integers, easily ⋮ Compositeness test with nodal curves ⋮ Finding elliptic curves with a subgroup of prescribed size ⋮ Optimal ancilla-free Pauli+V circuits for axial rotations ⋮ Polynomial Multiplication over Finite Fields in Time \( O(n \log n \) ⋮ Computational tameness of classical non-causal models ⋮ On the greatest prime factor of $p-1$ with effective constants ⋮ Sharpening ``Primes is in P for a large family of numbers ⋮ The geometry of Bayesian programming ⋮ It is easy to determine whether a given integer is prime ⋮ Unnamed Item ⋮ Ramanujan-Fourier series and the conjecture D of Hardy and Littlewood ⋮ Lower bounds on the orders of subgroups connected with Agrawal conjecture ⋮ Mechanisation of AKS Algorithm: Part 1 – The Main Theorem ⋮ Super-Perfect Zero-Knowledge Proofs ⋮ On a modification of the Lucas primality test ⋮ Certifying giant nonprimes ⋮ Computational Number Theory, Past, Present, and Future ⋮ Embedding divisor and semi-prime testability in \(f\)-vectors of polytopes ⋮ Algebraic algorithms for variants of subset sum ⋮ Locally verifiable signature and key aggregation ⋮ On some algebraic ways to calculate zeros of the Riemann zeta function ⋮ Algorithms for the Multiplication Table Problem ⋮ Deterministic factoring with oracles ⋮ On prime primitive roots of \(2^KP+1\) ⋮ Unnamed Item ⋮ Interactions of computational complexity theory and mathematics ⋮ Solving mean-payoff games via quasi dominions ⋮ A generalization of Miller’s primality theorem ⋮ A characterization of Sophie Germain primes ⋮ Unnamed Item ⋮ A Rigorous Security Proof for the Enhanced Version of Password-Protected Secret Sharing Scheme ⋮ The Monomial Ideal Membership Problem and Polynomial Identity Testing ⋮ Deterministic methods to find primes ⋮ Unnamed Item ⋮ Identifying the Matrix Ring: Algorithms for Quaternion Algebras and Quadratic Forms ⋮ Generating random factored ideals in number fields ⋮ On the Arithmetic Complexity of Euler Function ⋮ Recent Results on Polynomial Identity Testing ⋮ Notes on some new kinds of pseudoprimes ⋮ Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth ⋮ On taking square roots without quadratic nonresidues over finite fields ⋮ Solving Mean-Payoff Games via Quasi Dominions ⋮ Accelerating the CM method ⋮ Depth-4 Identity Testing and Noether’s Normalization Lemma ⋮ Testing numbers of the form N = 2kpm − 1 for primality ⋮ A deterministic version of Pollard’s $p-1$ algorithm ⋮ Sieving for Pseudosquares and Pseudocubes in Parallel Using Doubly-Focused Enumeration and Wheel Datastructures ⋮ The Lucas-Pratt primality tree ⋮ Efficient CM-constructions of elliptic curves over finite fields ⋮ Factoring and Testing Primes in Small Space ⋮ Unnamed Item ⋮ Computing prime harmonic sums ⋮ Faster integer multiplication using plain vanilla FFT primes ⋮ Unnamed Item ⋮ On the parameterized complexity of approximate counting ⋮ Von Neumann, Gödel and Complexity Theory ⋮ Optimal Las Vegas reduction from one-way set reconciliation to error correction ⋮ Two algorithms to find primes in patterns ⋮ Satisfiability of Algebraic Circuits over Sets of Natural Numbers ⋮ Quantum algorithms for algebraic problems ⋮ Complexity of inverting the Euler function ⋮ Generating Genus Two Hyperelliptic Curves over Large Characteristic Finite Fields ⋮ Some new kinds of pseudoprimes ⋮ Universality, Invariance, and the Foundations of Computational Complexity in the Light of the Quantum Computer ⋮ On Constructing 1-1 One-Way Functions ⋮ An 𝑂̃(log²(𝑁)) time primality test for generalized Cullen numbers ⋮ Unnamed Item ⋮ Cryptanalysis and improvements on some graph-based authentication schemes ⋮ Rank Vertex Cover as a Natural Problem for Algebraic Compression ⋮ Verifiable shuffles: a formal model and a Paillier-based three-round construction with provable security ⋮ Computing prime divisors in an interval ⋮ Emptiness Problems for Integer Circuits ⋮ Unnamed Item ⋮ Computing (and Life) Is All about Tradeoffs ⋮ Book Review: Inevitable randomness in discrete mathematics ⋮ Proving primality in essentially quartic random time ⋮ Modular exponentiation via the explicit Chinese remainder theorem ⋮ Implementing the asymptotically fast version of the elliptic curve primality proving algorithm ⋮ Factorization Tests and Algorithms Arising from Counting Modular Forms and Automorphic Representations ⋮ Unnamed Item ⋮ A String of Pearls: Proofs of Fermat's Little Theorem ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle ⋮ Primality test for numbers of the form (2p)2n+1 ⋮ Primes of the form 2p+1 ⋮ A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers ⋮ Prime divisors of sparse integers ⋮ On algorithms to find \(p\)-ordering ⋮ Subset sum ``cubes and the complexity of primality testing ⋮ Derandomizing restricted isometries via the Legendre symbol ⋮ Subexponential size hitting sets for bounded depth multilinear formulas ⋮ On the complexity of integer matrix multiplication ⋮ Even faster integer multiplication ⋮ Solving bivariate systems using rational univariate representations ⋮ A deterministic algorithm for the discrete logarithm problem in a semigroup ⋮ An algorithm for computing the factor ring of an ideal in Dedekind domain with finite rank ⋮ A short note on Merlin-Arthur protocols for subset sum ⋮ Formalizing an analytic proof of the prime number theorem ⋮ On the multiplicative order of the roots of \(bX^{q^r + 1} - aX^{q^r} + dX - c\)
This page was built for publication: PRIMES is in P
