A lower bound for primality
From MaRDI portal
The main result of the paper is that primality testing, gcd computation and square-free computation is not in \(AC^0\), that is, can not be accomplished by constant depth, polynomial-size circuits of AND, OR and NOT gates. The technique used by the authors is to reduce the functions that have circuit lower bound known to divisibility and then, using a randomized reduction, to primality testing.
Recommendations
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)
