Primality Test Via Quantum Factorization

DOI10.1142/S0129183197000138MaRDI QIDQ4488254zbMATH OpenFDO

Authors

Publication date 5 July 2000

Published in International Journal of Modern Physics C (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/9508005

zbMATH Keywords

Pocklington-Lehmer primality testprobabilistic quantum implementationShor's algorithm

Mathematics Subject Classification ID

Factorization; primality (11A51) Primality (11Y11) Quantum computation (81P68)

Abstract: We consider a probabilistic quantum implementation of a variable of the Pocklington-Lehmer $N-1$ primality test using Shor's algorithm. O($lo{g}^{3}NloglogNlogloglogN$) elementary q-bit operations are required to determine the primality of a number $N$, making it (asymptotically) the fastest known primality test. Thus, the potential power of quantum mechanical computers is once again revealed.

Recommendations

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• ON COMPUTATIONAL COMPLEXITY OF QUANTUM ALGORITHM FOR FACTORING
• Factorization of integers
• scientific article; zbMATH DE number 579167

Cites work

• A New Proof of the Quantum Noiseless Coding Theorem
• A universal two-bit gate for quantum computation
• Fast multiplication of large numbers
• Logical Reversibility of Computation
• On distinguishing prime numbers from composite numbers
• Quantum computational networks
• Quantum cryptography using any two nonorthogonal states
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Realizable Universal Quantum Logic Gates
• Riemann's hypothesis and tests for primality

Cited in

(1)

• Prime witnesses in the Shor algorithm and the Miller-Rabin algorithm

This page was built for publication: Primality Test Via Quantum Factorization

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