A lower bound for primality

DOI10.1006/JCSS.2000.1725MaRDI QIDQ5943093zbMATH OpenOpenAlexFDO

Authors Eric Allender, Michael Saks, Igor E. Shparlinski

Publication date 19 May 2003

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcss.2000.1725

zbMATH Keywords

circuitlower boundprimality

Mathematics Subject Classification ID

Primality (11Y11) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Circuit and decision tree complexity of some number theoretic problems
• Primality and identity testing via Chinese remaindering
• Lower bounds for arithmetic problems
• Subset sum ``cubes and the complexity of primality testing
• scientific article; zbMATH DE number 522838

Cites work

• A Fast Monte-Carlo Test for Primality
• Circuits in bounded arithmetic. I
• Constant Depth Reducibility
• scientific article; zbMATH DE number 3131972 (Why is no real title available?)
• scientific article; zbMATH DE number 1304311 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 1559593 (Why is no real title available?)
• Infinite Sets of Primes with Fast Primality Tests and Quick Generation of Large Primes
• Lower bounds for arithmetic problems
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Non-uniform depth of polynomial time and space simulations.
• Number theoretic methods in cryptography. Complexity lower bounds
• On distinguishing prime numbers from composite numbers
• On tape bounds for single letter alphabet language processing
• On the Average Sensitivity of Testing Square-Free Numbers
• On the Number of Primes in an Arithmetic Progression
• On the Recognition of Primes by Automata
• One-way functions and circuit complexity
• Probabilistic algorithm for testing primality
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• Riemann's hypothesis and tests for primality
• The average sensitivity of square-freeness

Cited in

(10)

• Lower bounds for arithmetic problems
• Circuit and decision tree complexity of some number theoretic problems
• Subset sum ``cubes and the complexity of primality testing
• Communication complexity of some number theoretic functions
• scientific article; zbMATH DE number 6881611 (Why is no real title available?)
• A LOWER BOUND ON THE NUMBER OF PRIMES BETWEEN AND n
• A REMARK ON PRIMALITY TESTING AND DECIMAL EXPANSIONS
• scientific article; zbMATH DE number 6266501 (Why is no real title available?)
• A Low-Level Proof of Chebyshev's Pre-Prime Number Theorem
• On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1

This page was built for publication: A lower bound for primality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5943093)