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/9908022

Carmichael Numbers on a Quantum Computer

A. Carlini, Akio Hosoya

Published Aug 5, 1999• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.quant-ph/9908022

Related papers

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

A quantum algorithm for computing the Carmichael function

Juan Carlos García-Escartín

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.

arXiv:2111.02488•Nov 3, 2021•0 citations

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 describe a quantum version of the classical probabilistic algorithms à la Rabin. The quantum probabilistic algorithm is fully unitary and reversible, and can be used as a subroutine in larger quantum computations. As an example, we describe a polynomial time algorithm for counting the number of primes smaller than a given integer.

Kluwer Academic Publishers eBooks•Feb 24, 2006•5 citations

Quantum Algorithms for Modular Factorials

Yann Tal

We give a bounded-error quantum algorithm that, given a prime $p$, a divisor $q\mid(p-1)$, and an integer $0<n<p$, computes $n!\bmod p$ in expected time $\widetilde{O}(q^c+\sqrt{p/q})$ for some absolute constant $c\ge 1$. When $p-1$ has a divisor of size $q\approx p^{1/(2c+1)}$, this gives the exponent $c/(2c+1)<1/2$. To our knowledge, this is the first algorithm to break the exponent $1/2$ barrier for modular factorials under such a divisor promise. The main technical ingredient is a quantum algorithm that reconstructs the relevant Jacobi sum exactly in compact algebraic form, with polynomial dependence on $q$ and $\log p$. We further extend the same asymptotic bound to the computation of $n!\bmod p^2$, uniformly over $0\le n<p^2$. At $n=p-1$, this determines the Wilson quotient $\frac{(p-1)!+1}{p}\pmod p$. We conjecture that the condition $q\mid(p-1)$ is a technical limitation of the present method rather than an inherent obstruction, and that a uniform quantum algorithm exists for all primes.

quant-pharXiv:2607.29453•Aug 3, 2026•0 citations

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
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.
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.
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.
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 give a bounded-error quantum algorithm that, given a prime ppp, a divisor q∣(p−1)q\mid(p-1)q∣(p−1), and an integer 0<n<p0<n<p0<n<p, computes n! mod pn!\bmod pn!modp in expected time O~(qc+p/q)\widetilde{O}(q^c+\sqrt{p/q})O(qc+p/q​) for some absolute constant c≥1c\ge 1c≥1. When p−1p-1p−1 has a divisor of size q≈p1/(2c+1)q\approx p^{1/(2c+1)}q≈p1/(2c+1), this gives the exponent c/(2c+1)<1/2c/(2c+1)<1/2c/(2c+1)<1/2. To our knowledge, this is the first algorithm to break the exponent 1/21/21/2 barrier for modular factorials under such a divisor promise. The main technical ingredient is a quantum algorithm that reconstructs the relevant Jacobi sum exactly in compact algebraic form, with polynomial dependence on qqq and log⁡p\log plogp. We further extend the same asymptotic bound to the computation of n! mod p2n!\bmod p^2n!modp2, uniformly over 0≤n<p20\le n<p^20≤n<p2. At n=p−1n=p-1n=p−1, this determines the Wilson quotient (p−1)!+1p(modp)\frac{(p-1)!+1}{p}\pmod pp(p−1)!+1​(modp). We conjecture that the condition q∣(p−1)q\mid(p-1)q∣(p−1) is a technical limitation of the present method rather than an inherent obstruction, and that a uniform quantum algorithm exists for all primes.
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.