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:2111.02488

A quantum algorithm for computing the Carmichael function

Juan Carlos García-Escartín

Published Nov 3, 2021• 0 citations
arXivHTMLPDF

Abstract

Quantum computers can solve many number theory problems efficiently. Using the efficient quantum algorithm for order finding as an oracle, this paper presents an algorithm that computes the Carmichael function for any integer $N$ with a probability as close to 1 as desired. The algorithm requires $O((\log n )^3n^3)$ quantum operations, or $O(\log\log n (\log n)^4 n^2)$ operations using fast multiplication. Verification, quantum optimizations and applications to RSA and primality tests are also discussed.

DOI
10.48550/arxiv.2111.02488

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

A quantum algorithm for computing multiplicative order of integers modulo a prime

Maheswara Rao Valluri

One of the challenging problems in number theory is to compute efficiently multiplicative order of integers modulo a prime. This problem was listed under open problems in the number theoretic complexity II proposed by Leonard M. Adleman and Kevin S.McCurley in 1994. This paper offers a polynomial-time quantum algorithm for computing the order k = min {x|x∈, ax ≡ 1(modp)}, if p∈ Primes and gcd(a,p) = 1, where a, p∈, and it requires 2 (1) 2 ((log p) +O )  quantum operations.

Journal of Discrete Mathematical Sciences and Cryptography•Jan 1, 2023•0 citations

Carmichael Numbers on a Quantum Computer

A. Carlini, Akio Hosoya

We present a quantum probabilistic algorithm which tests with a polynomial computational complexity whether a given composite number is of the Carmichael type. We also suggest a quantum algorithm which could verify a conjecture by Pomerance, Selfridge and Wagstaff concerning the asymptotic distribution of Carmichael numbers smaller than a given integer.

arXiv:quant-ph/9908022•Aug 5, 1999•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

On Computing

The order r of an element a in the multiplicative group (Z/nZ)*, denoted by order (a,n), or la(n) for short, plays a significant role in the period of certain pseudo-random number generators and is particularly important in Shor's quantum integer factorization algorithm, as well as in various cryptographic applications. In this paper, we present some numerical results and evidence of suitable a for which la(n) are small and relatively easy to obtain, in the light of quantum integer factorization. The results indicate that the higher the order, the larger of the number of a . Therefore, we propose a quantum algorithm for finding a in a2k≡1 (mod n) with k≥1, explicitly excluding the trivial solution a≡1 (mod n), based on Grover's search, but using fewer quantum bits. Moreover, the proposed algorithm achieves a success probability close to 1. As this type of n is commonly used as an RSA modulus, once such an a is found, RSA cryptographic system will be broken.

•Jun 24, 2026•0 citations

Quantum computation of prime number functions

José Ignacio Latorre, Germán Sierra

We propose a quantum circuit that creates a pure state corresponding to the quantum superposition of all prime numbers less than $2^n$, where $n$ is the number of qubits of the register. This Prime state can be built using Grover's algorithm, whose oracle is a quantum implementation of the classical Miller-Rabin primality test. The Prime state is highly entangled, and its entanglement measures encode number theoretical functions such as the distribution of twin primes or the Chebyshev bias. This algorithm can be further combined with the quantum Fourier transform to yield an estimate of the prime counting function, more efficiently than any classical algorithm and with an error below the bound that allows for the verification of the Riemann hypothesis. Arithmetic properties of prime numbers are then, in principle, amenable to experimental verifications on quantum systems.

Quantum Information and Computation•May 1, 2014•14 citations
Quantum computers can solve many number theory problems efficiently. Using the efficient quantum algorithm for order finding as an oracle, this paper presents an algorithm that computes the Carmichael function for any integer NNN with a probability as close to 1 as desired. The algorithm requires O((log⁡n)3n3)O((\log n )^3n^3)O((logn)3n3) quantum operations, or O(log⁡log⁡n(log⁡n)4n2)O(\log\log n (\log n)^4 n^2)O(loglogn(logn)4n2) operations using fast multiplication. Verification, quantum optimizations and applications to RSA and primality tests are also discussed.
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.
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.
The order r of an element a in the multiplicative group (Z/nZ)*, denoted by order (a,n), or la(n) for short, plays a significant role in the period of certain pseudo-random number generators and is particularly important in Shor's quantum integer factorization algorithm, as well as in various cryptographic applications. In this paper, we present some numerical results and evidence of suitable a for which la(n) are small and relatively easy to obtain, in the light of quantum integer factorization. The results indicate that the higher the order, the larger of the number of a . Therefore, we propose a quantum algorithm for finding a in a2k≡1 (mod n) with k≥1, explicitly excluding the trivial solution a≡1 (mod n), based on Grover's search, but using fewer quantum bits. Moreover, the proposed algorithm achieves a success probability close to 1. As this type of n is commonly used as an RSA modulus, once such an a is found, RSA cryptographic system will be broken.
We propose a quantum circuit that creates a pure state corresponding to the quantum superposition of all prime numbers less than 2n2^n2n, where nnn is the number of qubits of the register. This Prime state can be built using Grover's algorithm, whose oracle is a quantum implementation of the classical Miller-Rabin primality test. The Prime state is highly entangled, and its entanglement measures encode number theoretical functions such as the distribution of twin primes or the Chebyshev bias. This algorithm can be further combined with the quantum Fourier transform to yield an estimate of the prime counting function, more efficiently than any classical algorithm and with an error below the bound that allows for the verification of the Riemann hypothesis. Arithmetic properties of prime numbers are then, in principle, amenable to experimental verifications on quantum systems.