A quantum primality test with order finding
arXiv:1711.02616 · doi:10.26421/QIC17.13-14
Abstract
Determining whether a given integer is prime or composite is a basic task in number theory. We present a primality test based on quantum order finding and the converse of Fermat's theorem. For an integer , the test tries to find an element of the multiplicative group of integers modulo with order . If one is found, the number is known to be prime. During the test, we can also show most of the times is composite with certainty (and a witness) or, after unsuccessful attempts to find an element of order , declare it composite with high probability. The algorithm requires operations for a number with bits, which can be reduced to operations in the asymptotic limit if we use fast multiplication.
arXiv comment5 pages. Comments welcome
References in corpus (20)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Improved Simulation of Stabilizer Circuits
- A Theory of Quantum Error-Correcting Codes
- Quantum Networks for Elementary Arithmetic Operations
- Stabilizer Codes and Quantum Error Correction
- Instantaneous non-local computation of low T-depth quantum circuits
- The Heisenberg Representation of Quantum Computers
- Improved classical simulation of quantum circuits dominated by Clifford gates
- Efficient Networks for Quantum Factoring
- Fast Quantum Modular Exponentiation
- The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
- Quantum NP - A Survey
- Fast versions of Shor's quantum factoring algorithm
- Semidefinite programs for completely bounded norms
- The Quantum PCP Conjecture
- Further extensions of Clifford circuits and their classical simulation complexities
- 3-Local Hamiltonian is QMA-complete
- Quantum Probabilistic Subroutines and Problems in Number Theory
- Quantum Merlin-Arthur with noisy channel
- An Algorithm for Constructing Polynomial Systems Whose Solution Space Characterizes Quantum Circuits
Cited by in corpus (19)
- Advances in Quantum Cryptography
- Long-Distance Continuous-Variable Quantum Key Distribution over 202.81 km of Fiber
- Towards Large-scale Functional Verification of Universal Quantum Circuits
- Continuous-variable measurement-device-independent quantum key distribution: Composable security against coherent attacks
- Using and reusing coherence to realize quantum processes
- Probabilistic distillation of quantum coherence
- Codes and Protocols for Distilling , controlled-, and Toffoli Gates
- Quantifying the resource content of quantum channels: An operational approach
- Polarization attack on continuous-variable quantum key distribution
- Composable security analysis of continuous-variable measurement-device-independent quantum key distribution with squeezed states for coherent attacks
- Discrete Wigner Formalism for Qubits and Non-Contextuality of Clifford Gates on Qubit Stabilizer States
- Gaussian one-way thermal quantum cryptography with finite-size effects
- Quantifying coherence in terms of the pure-state coherence
- Quantum computational advantage with string order parameters of 1D symmetry-protected topological order
- Advantages and limitations of quantum routing
- Coherence manipulation with dephasing-covariant operations
- Cohering and decohering power of massive scalar fields under instantaneous interactions
- Continuous-variable nonlocality and contextuality
- The Interplay between Quantum Contextuality and Wigner Negativity