Paper 2024/222
Reducing the Number of Qubits in Quantum Factoring
Abstract
This paper focuses on the optimization of the number of logical qubits in quantum algorithms for factoring and computing discrete logarithms in $\mathbb{Z}_N^*$. These algorithms contain an exponentiation circuit modulo $N$, which is responsible for most of their cost, both in qubits and operations. In this paper, we show that using only $o(\log N)$ work qubits, one can obtain the least significant bits of the modular exponentiation output. We combine this result with May and Schlieper's truncation technique (ToSC 2022) and the EkeråHåstad variant of Shor's algorithm (PQCrypto 2017) to solve the discrete logarithm problem in $\mathbb{Z}_N^*$ using only $d + o(\log N)$ qubits, where $d$ is the bitsize of the logarithm. Consequently we can factor $n$bit RSA moduli using $n/2 + o(n)$ qubits, while current envisioned implementations require about $2n$ qubits. Our algorithm uses a Residue Number System and succeeds with a parametrizable probability. Being completely classical, we have implemented and tested it. For RSA factorization, we can reach a gate count $\mathcal{O}(n^3)$ for a depth $\mathcal{O}(n^2 \log^3 n)$, which then has to be multiplied by $\mathcal{O}(\log n)$ (the number of measurement results required by EkeråHåstad). To factor an RSA2048 instance, we estimate that 1730 logical qubits and $2^{36}$ Toffoli gates will suffice for a single run, and the algorithm needs on average 40 runs. To solve a discrete logarithm instance of 224 bits (112bit classical security) in a safeprime group of 2048 bits, we estimate that 684 logical qubits would suffice, and 20 runs with $2^{32}$ Toffoli gates each.
Metadata
 Available format(s)
 Category
 Attacks and cryptanalysis
 Publication info
 Preprint.
 Keywords
 Quantum cryptanalysisShor's algorithmInteger factoringDiscrete LogarithmsResidue number system
 Contact author(s)

clemence chevignard @ inria fr
pierrealain fouque @ irisa fr
andre schrottenloher @ inria fr  History
 20240607: last of 2 revisions
 20240213: received
 See all versions
 Short URL
 https://ia.cr/2024/222
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/222, author = {Clémence Chevignard and PierreAlain Fouque and André Schrottenloher}, title = {Reducing the Number of Qubits in Quantum Factoring}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/222}, year = {2024}, url = {https://eprint.iacr.org/2024/222} }