A quantum primality test with order finding

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 $N$, the test tries to find an element of the multiplicative group of integers modulo $N$ with order $N-1$. If one is found, the number is known to be prime. During the test, we can also show most of the times $N$ is composite with certainty (and a witness) or, after $\log \log N$ unsuccessful attempts to find an element of order $N-1$, declare it composite with high probability. The algorithm requires $O((\log n{)}^2{n}^3)$ operations for a number $N$ with $n$ bits, which can be reduced to $O(\log \log n(\log n{)}^3{n}^2)$ operations in the asymptotic limit if we use fast multiplication.

5 pages. Comments welcome

References in corpus (5)

• Fast Quantum Modular Exponentiation
• Quantum NP - A Survey
• Semidefinite programs for completely bounded norms
• 3-Local Hamiltonian is QMA-complete
• Quantum Merlin-Arthur with noisy channel

Cited by in corpus (18)

• 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
• Using and reusing coherence to realize quantum processes
• Probabilistic distillation of quantum coherence
• Codes and Protocols for Distilling $T$, controlled-$S$, 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