Primality Test Via Quantum Factorization

1995/08/05 by H. F. Chau, Chau, H. F., Hoi‐Kwong Lo +2
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/9508005

Using REVTEX 3.0, AMS fonts required. Typos corrected. To appear in Int.J.Mod.Phys.C

openalex publication_date 1995/08/05 · arxiv created 1996/12/01 · arxiv updated 2016/09/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider a probabilistic quantum implementation of a variable of the Pocklington-Lehmer N-1 primality test using Shor's algorithm. O(log³ N loglog N logloglog N) 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.

Related

• 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 the Power of Quantum Computation
• Integer Factorization by Quantum Measurements
• Probability Analysis of a Quantum Computer