Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/9508005 · International Journal of Modern Physics C

Primality Test Via Quantum Factorization

H. F. Chau, Hoi‐Kwong Lo

Published Apr 1, 1997• 9 citations
arXivHTMLPDF

Abstract

We consider a probabilistic quantum implementation of a variation of the Pocklington–Lehmer N - 1 primality test using Shor's algorithm. O ( log 3 N log log N log log log 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.

DOI
10.1142/s0129183197000138

Related papers

A quantum primality test with order finding

A. Donís Vela, Juan Carlos García-Escartín

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.

arXiv:1711.02616•Quantum Information and Computation•Nov 1, 2018•4 citations

Taxonomy and Practical Evaluation of Primality Testing Algorithms

Anas Ahmad Abudaqa, Nujud Alyami, Mostefa Kara +2 more

Abstract Many modern asymmetric encryption methods rely on prime numbers, as they have distinctive properties. For instance, the security of RSA cryptosystem relies on the computational difficulty of factoring a large composite number in its prime factors, a problem that remains challenging for classical computers but potentially solvable using quantum algorithms. On the other hand, generating large prime numbers is also challenging due to their irregular distribution among integers, necessitat- ing the use of primality testing algorithms to verify candidate primes. In this paper, we intensively review and classify various classical and quantum algorithms for factorization and primality testing, highlighting their advantages, limitations, speed/accuracy tradeoffs, time complexities, along with a brief summary. Furthermore, we apply and compare these algorithms to gain practical insights and conduct a comprehensive performance comparison. The insights from this paper show that while quantum factoring algorithms, particularly Shor’s algorithm and its refinements, have introduced significant advancements over their classical counterparts, quantum primality testing algorithms have not demonstrated comparable advantages.

arXiv:2006.08444•Jun 15, 2020•1 citation

Quantum Versions of Classical Randomized Algorithms

A. Carlini, Akio Hosoya

We present a quantum version of the classical probabilistic algorithms a' la Rabin for the test of primality of a given integer. Our quantum algorithm is based on the use of Grover's unitary operator for searching an unstructured database and of Shor's Fourier transform for extracting the periodicity of a function, and their combined use in the quantum counting algorithm by Brassard et al. Our quantum probabilistic algorithm is fully unitary and reversible, and can be used as part of larger and more complicated quantum networks. Polynomial time algorithms for testing the primality of an integer, the ‘prime number theorem’ and a conjecture about the asymptotic number of representations of an even integer as a sum of two primes are also discussed.

Progress of Theoretical Physics Supplement•Jan 1, 2000•0 citations

Quantum probabilistic subroutines and problems in number theory

A. Carlini, Akio Hosoya

We present a quantum version of the classical probabilistic algorithms as studied by Rabin. The quantum algorithm is based on the essential use of Grover's operator for the quantum search of a database and of Shor's Fourier transform for extracting the periodicity of a function, and their combined use in the counting algorithm originally introduced by Brassard et al. One of the main features of our quantum probabilistic algorithm is its full unitarity and reversibility, which would make its use possible as part of larger and more complicated networks in quantum computers. As an example of this we describe polynomial time algorithms for studying some important problems in number theory, such as the test of the primality of an integer, the so called prime number theorem, and Hardy and Littlewood's conjecture about the asymptotic number of representations of an even integer as a sum of two primes.

arXiv:quant-ph/9907020•Physical Review A•Aug 18, 2000•11 citations

Prime Number Primality Testing via Quantum Lattice-Based Search

Jincheng Zhang

This paper introduces a novel quantum algorithm for efficient primality testing, aiming to surpass the limitations of classical methods through the application of lattice-based search. We detail the design of a quantum circuit that explores the prime number space, leveraging superposition and entanglement to achieve significantly reduced computational complexity. The core mechanism centers around quantum search, allowing for parallel exploration of the vast space of possible prime factors. We present a comprehensive analysis of the algorithm's performance, including a detailed mathematical justification of its efficiency gains compared to established techniques. The paper concludes with a discussion of the potential implications of this quantum approach for cryptography and other applications requiring prime number verification.

•Aug 31, 2026•0 citations

Implementation of Shor’s Quantum Factoring Algorithm Using ProjectQ Framework

Adjie Wahyu Wicaksono, Arya Wicaksana

Prime number factorization is a problem in computer science where the solution to that problem takes super-polynomial time classically. Shor’s quantum factoring algorithm is able to solve the problem in polynomial time by harnessing the power of quantum computing. The implementation of the quantum algorithm itself is not detailed by Shor in his paper. In this paper, an approach and experiment to implement Shor’s quantum factoring algorithm are proposed. The implementation is done using Python and a quantum computer simulator from ProjectQ. The testing and evaluation are completed in two computers with different hardware specifications. User time of the implementation is measured in comparison with other quantum computer simulators: ProjectQ and Quantum Computing Playground. This comparison was done to show the performance of Shor’s algorithm when simulated using different hardware. There is a 33% improvement in the execution time (user time) between the two computers with the accuracy of prime factorization in this implementation is inversely proportional to the number of qubits used. Further improvements upon the program that has been developed for this paper is its accuracy in terms of finding the factors of a number and the number of qubits used, as previously mentioned.

International Journal of Engineering and Advanced Technology•Nov 22, 2019•4 citations
We consider a probabilistic quantum implementation of a variation of the Pocklington–Lehmer N - 1 primality test using Shor's algorithm. O ( log 3 N log log N log log log 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.
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.
Abstract Many modern asymmetric encryption methods rely on prime numbers, as they have distinctive properties. For instance, the security of RSA cryptosystem relies on the computational difficulty of factoring a large composite number in its prime factors, a problem that remains challenging for classical computers but potentially solvable using quantum algorithms. On the other hand, generating large prime numbers is also challenging due to their irregular distribution among integers, necessitat- ing the use of primality testing algorithms to verify candidate primes. In this paper, we intensively review and classify various classical and quantum algorithms for factorization and primality testing, highlighting their advantages, limitations, speed/accuracy tradeoffs, time complexities, along with a brief summary. Furthermore, we apply and compare these algorithms to gain practical insights and conduct a comprehensive performance comparison. The insights from this paper show that while quantum factoring algorithms, particularly Shor’s algorithm and its refinements, have introduced significant advancements over their classical counterparts, quantum primality testing algorithms have not demonstrated comparable advantages.
We present a quantum version of the classical probabilistic algorithms a' la Rabin for the test of primality of a given integer. Our quantum algorithm is based on the use of Grover's unitary operator for searching an unstructured database and of Shor's Fourier transform for extracting the periodicity of a function, and their combined use in the quantum counting algorithm by Brassard et al. Our quantum probabilistic algorithm is fully unitary and reversible, and can be used as part of larger and more complicated quantum networks. Polynomial time algorithms for testing the primality of an integer, the ‘prime number theorem’ and a conjecture about the asymptotic number of representations of an even integer as a sum of two primes are also discussed.
We present a quantum version of the classical probabilistic algorithms as studied by Rabin. The quantum algorithm is based on the essential use of Grover's operator for the quantum search of a database and of Shor's Fourier transform for extracting the periodicity of a function, and their combined use in the counting algorithm originally introduced by Brassard et al. One of the main features of our quantum probabilistic algorithm is its full unitarity and reversibility, which would make its use possible as part of larger and more complicated networks in quantum computers. As an example of this we describe polynomial time algorithms for studying some important problems in number theory, such as the test of the primality of an integer, the so called prime number theorem, and Hardy and Littlewood's conjecture about the asymptotic number of representations of an even integer as a sum of two primes.
This paper introduces a novel quantum algorithm for efficient primality testing, aiming to surpass the limitations of classical methods through the application of lattice-based search. We detail the design of a quantum circuit that explores the prime number space, leveraging superposition and entanglement to achieve significantly reduced computational complexity. The core mechanism centers around quantum search, allowing for parallel exploration of the vast space of possible prime factors. We present a comprehensive analysis of the algorithm's performance, including a detailed mathematical justification of its efficiency gains compared to established techniques. The paper concludes with a discussion of the potential implications of this quantum approach for cryptography and other applications requiring prime number verification.
Prime number factorization is a problem in computer science where the solution to that problem takes super-polynomial time classically. Shor’s quantum factoring algorithm is able to solve the problem in polynomial time by harnessing the power of quantum computing. The implementation of the quantum algorithm itself is not detailed by Shor in his paper. In this paper, an approach and experiment to implement Shor’s quantum factoring algorithm are proposed. The implementation is done using Python and a quantum computer simulator from ProjectQ. The testing and evaluation are completed in two computers with different hardware specifications. User time of the implementation is measured in comparison with other quantum computer simulators: ProjectQ and Quantum Computing Playground. This comparison was done to show the performance of Shor’s algorithm when simulated using different hardware. There is a 33% improvement in the execution time (user time) between the two computers with the accuracy of prime factorization in this implementation is inversely proportional to the number of qubits used. Further improvements upon the program that has been developed for this paper is its accuracy in terms of finding the factors of a number and the number of qubits used, as previously mentioned.