Next Loria Security Seminar will take place on Tuesday, 15 April 2025 at 1pm at Loria.

André Schrottenloher (Univ Rennes, Inria, CNRS, IRISA) will give a presentation entitled “Reducing the Number of Qubits in Quantum Factoring“.

Shor’s algorithm (FOCS 1994) is arguably the most powerful application of quantum algorithms to cryptanalysis, as it solves the factoring and discrete logarithm problem in polynomial time. In the past 30 years, many authors have optimized its time complexity (the number of basic operations, also known as quantum gates) and memory footprint (the number of qubits). While quantum computers are still far from running Shor’s algorithm in practice, these fine-grained optimizations improve our understanding of the resources required to do so.

In this talk, I will present a new memory optimization in this algorithm. As in previous works, we focus on the modular exponentiation modulo N, which is its core component. We show that a logarithmic number of work qubits suffices to obtain the least significant bits of the output. We combine this result with May and Schlieper’s truncation technique (ToSC 2022) and the Ekera-Hastad variant of Shor’s algorithm (PQCrypto 2017) to solve the discrete logarithm problem in ℤ_N^* using only d + o(log N) qubits, where d is the bit-size of the logarithm. Consequently we can factor n-bit RSA moduli using n/2 + o(n) qubits, a quarter of the previous most optimized implementations.