# Reducing the Number of Qubits in Quantum Factoring

Clémence Chevignard, Pierre-Alain Fouque, André Schrottenloher

► To cite this version:

Clémence Chevignard, Pierre-Alain Fouque, André Schrottenloher. Reducing the Number of Qubits in Quantum Factoring. CRYPTO 2025 - Advances in Cryptology, Aug 2025, Santa Barbara, United States. pp.384-415, 10.1007/978-3-032-01878-6_13. hal-05436363

HAL Id: hal-05436363

https://inria.hal.science/hal-05436363v1

Submitted on 31 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Reducing the Number of Qubits in Quantum
Factoring *

Clémence Chevignard, Pierre-Alain Fouque, and André Schrottenloher

Univ Rennes, Inria, CNRS, IRISA
firstname.lastname@inria.fr

**Abstract.** This paper focuses on the optimization of the number of log-ical qubits in quantum algorithms for factoring and computing discrete logarithms in $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 ob-tain 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 $Z_N^*$ using only $d + o(\log N)$ qubits, where $d$ is the bit-size of the logarithm. Consequently we can fac-tor $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 imple-mented and tested it. For RSA factorization, we can reach a gate count $O(n^3)$ for a depth $O(n^2 \log^3 n)$, which then has to be multiplied by $O(\log n)$ (the number of measurement results required by Ekerå-Håstad). To factor an RSA-2048 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 (112-bit classical security) in a safe-prime group of 2048 bits, we estimate that 684 logical qubits would suffice, and 20 runs with $2^{32}$ Toffoli gates each.

**Keywords:** Quantum cryptanalysis, Shor's algorithm, Integer factoring, Discrete Logarithms, Residue number system.

# 1 Introduction

In 1994, Shor [34] introduced a polynomial-time quantum algorithm for factoring integers and computing Discrete Logarithms (DL). This remains to date one of the most powerful applications of quantum cryptanalysis, which caused the birth of post-quantum cryptography.

<footnote>* ©IACR 2025. This article is the full version of the paper submitted by the author(s) to the IACR and to Springer-Verlag in May 2025. The published version is available from the proceedings of CRYPTO 2025.</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1. Shor's quantum DL subroutine.</figcaption></figure>

Shor's algorithm for DL relies on a quantum period-finding subroutine represented in Figure 1, which finds the period of a function $f: \mathcal{G} \to \{0, 1\}^n$ for $(\mathcal{G}, +)$ any Abelian group where operations are efficiently computable.

Let $\mathcal{G}$ be a multiplicative generator of $\mathbb{Z}_N^*$. In order to find the DL of $\mathcal{A}$, one defines the function $f$ over $\mathbb{Z}^2$ by $f(x, y) = \mathcal{G}^x A^{-y} \mod N$. Obviously the pair $(\mathcal{D}, 1)$, where $\mathcal{D}$ is such that $\mathcal{A} = \mathcal{G}^\mathcal{D}$, is a period of $f$: one has $f(x+\mathcal{D}, y+1) = f(x, y)$ for all $(x, y)$.

The algorithm starts by initializing an *input register* $x$ of $m := m_1 + m_2$ bits and a *workspace register*. It then produces a uniform superposition in the *input* $x$ and computes $f$ in the *workspace*. It then performs a Quantum Fourier Transform (QFT) on the *input register* again. Upon measurement, only the value of the *input register* is used. A classical post-processing extracts the period (hence the DL) from one or more measurement outputs. The case of factoring is simpler: one just looks for the multiplicative order of a constant $\mathcal{A}$ modulo $N$, so the function is defined over $\mathbb{Z}$ by $f(x) = \mathcal{A}^x \mod N$.

For both factoring and DL, one needs only $m = O(\log N)$. Besides, both the Hadamard and Fourier transform can be performed in place and efficiently, meaning that the computational cost is mostly determined by the cost of the modular exponentiation circuit: computing $\mathcal{G}^x A^{-y} \mod N$. Like previous works, this is the part that we target. This operation can entirely be implemented using classical reversible logic, i.e., Toffoli, CNOT and NOT gates. This is what we do in this paper, although many previous works have also used “inherently quantum” arithmetic circuits based on the QFT and phase operations [9,24].

*Optimization of Space.* Since Shor's original paper, precisely estimating the cost of the algorithm has remained a crucial question. Many authors have designed circuits optimizing either its qubit or gate count [3,38,36,22,16].

For factoring, most of these works report a qubit count of $2n + 1$ or above, where $n = \log_2 N$ (see for example [16] for a comparison). The best count is from [38], where Zalka proposes a circuit with $1.5n$ qubits, and suggests that it could be reduced further. However, to the best of our knowledge, this circuit has not been benchmarked in practice.

All of the recent implementations use the semi-classical Fourier transform [20] to save the space used by the *input register*, by reducing it to a single qubit
<figure><img src="image_3.png" /><figcaption>**Fig. 2.** New factoring subroutine: “compressed Ekerå-Håstad”.</figcaption></figure>

which is repeatedly measured and reused. Thus, the space cost comes entirely
from modular exponentiation.

The goal of these optimizations is to reduce the physical resources required
to factor large RSA moduli. For example, in [19] Gidney and Ekerå used a
quantum circuit with around $3n$ logical qubits and $0.3n^3$ Toffoli gates. For RSA-
2048, they estimated that 20 million physical qubits would be necessary – but
only 8 hours of wall-clock time. Therefore, the number of qubits seems to be one
of the strongest constraints on the physical implementation of this algorithm.

*The Compression Technique.* May and Schlieper studied the behavior of Shor's
subroutine if the workspace register is reduced to a fraction of its size, down
to a single bit [25]. This means that the circuit does not implement $(x, y) \mapsto
G^x A^{-y} \mod N$ anymore, but $(x, y) \mapsto h(G^x A^{-y} \mod N)$ where $h$ is a good hash
function mapping $\mathbb{Z}_N^*$ to $\{0, 1\}^r$, where $r \ll n$ is a small constant. They showed
that if $h$ is picked from a universal hash function family, then the “compressed”
version of Shor's algorithm behaves similarly as the original one, and outputs
almost the same distribution of values for the input register.

Unfortunately, this can only improve the space complexity if $h(G^x A^{-y} \bmod N)$
can be implemented with less space than naively computing $G^x A^{-y}$, and then
$h$. This was left as an open question.

As noticed by May and Schlieper, the compression technique could be partic-
ularly useful in combination with the Ekerå-Håstad algorithm for short discrete
logarithms [15]. This variant of Shor’s algorithm uses multiple runs and a more
involved post-processing to minimize the input register size. It finds $d$-bit DLs
using $d + o(d)$ input qubits, and factors $n$-bit RSA moduli with $\frac{n}{2} + o(n)$ input
qubits. Therefore, a “compressed” variant could significantly reduce the total
number of qubits for both DL and factoring. Notice that this changes funda-
mentally the structure of the circuit, represented in Figure 2. The semi-classical
Fourier transform cannot be used anymore. The input register, of size $\frac{n}{2} + o(n)$,
must be kept along, and the workspace contains $o(n)$ qubits. On the positive
side, this means that no intermediate measurements need to be performed.

**Contributions.** In this paper, we introduce a dedicated method to compute directly this “compressed” result of the modular exponentiation step in Shor’s algorithm. More precisely, we compute the $r$ least significant bits of $G^x A^{-y} \bmod N$,
instead of the complete $n$-bit output. Our method is completely classical. We implemented it, and designed corresponding reversible logic circuits.

**Theorem (informal, see Theorem 2)** Let $m \le 2n$ be the total size of the input register and $r$ be a constant. For any constant $\varepsilon > 0$, there exists a reversible logical circuit for the operation $x, y \mapsto (G^x A^{-y} \mod N) \mod 2^r$. It succeeds with probability $1 - \varepsilon$ for inputs $x, y$ chosen uniformly at random. It uses $O(nm^2)$ gates, depth $O(nm \log^3 n)$ and $O(\log n + \frac{m}{\log n}) = o(n)$ ancilla qubits.

Equipped with this tool, we run the Ekerå-Håstad algorithm by replacing the function $(x, y) \mapsto (G^x A^{-y} \mod N)$ by $(x, y) \mapsto \beta \cdot ((G^x A^{-y} \mod N) \mod 2^r)$ for a randomly chosen mask $\beta$ (the role of $\beta$ is only technical here; it serves to randomize the compression function when running the theorem). We use a first heuristic which assumes that the function $(x, y) \mapsto G^x A^{-y} \mod N$ behaves randomly (apart from its periodicity).

**Heuristic 1.** When $N$ is selected at random, the function $f: x, y \mapsto G^x A^{-y} \mod N$ behaves statistically like a random periodic function $\{0, 1\}^m \to \mathbb{Z}_N^*$.

We stress that the function $f$ is in fact not random at all, since it is trivially malleable. This heuristic is merely a guarantee that the outputs of the function are independent of the inner workings of the period-finding subroutine. It prevents a pathological situation in which the outputs of $f$ having the same first $r$ bits would badly interfere, breaking down the algorithm. Similar heuristics are very common in classical cryptanalysis. For example, Pollard's rho method [28] assumes the randomness of the function $x \mapsto x^2 \mod N$ for some modulus $N$.

Under this heuristic, we prove that the distribution of outputs of the modified quantum subroutine is analogous to that of the uncompressed Ekerå-Håstad algorithm. More precisely, the analysis of Ekerå-Håstad [15] relies on the probability to measure some “good pairs” $(x, y)$ in the input register, which is shown to be at least $1/8$. We show:

**Theorem (informal, see Theorem 3)** Under Heuristic 1, using $r = 22$ bits for truncation, the modified Ekerå-Håstad subroutine outputs 0 with probability around $\frac{1}{2} + 0.01$ and outputs a good pair with probability at least $\frac{1}{16} - 0.01$.

Note that this situation differs from May and Schlieper's work, which assumes that a universal hash function family $Z_N^* \to \{0, 1\}^r$ is given, and one can sample a new function from this family at each call to the subroutine. In our case, we want to rely only on a single function computing $r$ bits of the output. The similarity with May and Schlieper's approach lies only in the random choice of mask $\beta$, which is important for the proof of Theorem 3.

*Probability of Error.* Like state-of-the-art implementations of quantum exponents [19], our circuit is not exact. Most of the error stems from the truncation of a sum, which is very similar to the principle of oblivious carry runways [17].
Essentially, the latter allows to compute a sum faster by reasoning independently on several windows of bits, which remain independent with high probability (unless a long carry propagation occurred, which is very unlikely). In our case, we only need to compute a small window of the output bits, and we succeed for the same reason. This will be detailed in Section 4. In order to prove the correctness of our algorithm, we formulate this as a heuristic.

**Heuristic 2.** For a given $N$, $G$ and $A$, our computation of $(G^x A^{-y} \mod N) \mod 2^r$ returns the correct result in all but a fraction $\varepsilon > 0$ of cases, where $\varepsilon$ is a constant that can be chosen arbitrarily small.

Using a sufficiently small constant $\varepsilon$, the quantum subroutine will proceed without being disrupted, and the entire algorithm will succeed. For a good trade-off, the total number of runs (i.e., measurements) in the Ekerå-Håstad algorithm should be around $O(\log n)$.

**Theorem (Informal)** *Under the two heuristics above, Algorithm 2 allows to factor a $n$-bit RSA modulus with a gate count in $O(n^3 \log n)$ (in $O(\log n)$ runs of a circuit of size $O(n^3)$), depth in $\tilde{O}(n^2)$ and $\frac{n}{2} + o(n)$ qubits.*

The case of discrete logarithms in $Z_p^*$, where $p$ is a large prime, is also interesting for us. Very often, the group size is taken sufficiently large to make the number field sieve computationally infeasible, while the DL bit-size $d$ remains quite small. The Ekerå-Håstad algorithm is particularly suited to this setting: the sub-routine has gate count $\tilde{O}(d^2 \log P)$ and uses $d + o(d) + O(\log P)$ qubits.

**Method.** Our method is inspired by results of circuit complexity and optimizations of circuit depth using Residue Number Systems (RNS)$^1$. An RNS represents a large number by a collection of residues modulo a set of small primes. In our case, the number that we represent is a *multi-product*, i.e., the product of multiple precomputed integers modulo $N$ corresponding to powers of a constant. Using the RNS, we find that the output bits that we wish to compute can be ultimately expressed as a large sum of integers over $O(\log n)$ bits. These integers are precomputed, and the bits which control the sum are computed on the fly by reducing the multi-product modulo the small primes of the RNS.

More precisely, we start from the well-known reduction of an exponentiation (with a fixed number and a variable exponent) to a controlled multi-product. Having precomputed powers of $G$ and $A$, the output of the exponentiation function can be computed as: $\prod_i A_i^{z_i} \mod N$ where the $A_i$ are powers of the form $G^{2^i}$ or $A^{2^j}$ and the $z_i$ are bits of $x$ or $y$ respectively. This is traditionally computed as a sequence of products by the $A_i$, controlled by the bits $z_i$; hence there are $m$ such products, where $m$ is the input register size defined above.

<footnote n="1">¹ A more detailed discussion on the relation between this question and circuit complexity is given in Section A.</footnote>
In our algorithm, we focus on the large number $\prod_i A_i^{z_i}$, which has the order of $mn$ bits, and represent it using the RNS. By the Chinese Remainder Theorem, this number can be expressed as a sum of residues modulo small primes, multiplied by large constants which can be precomputed$^2$. Essentially the computation of residues will dominate our algorithm: there are $O(nm/\log n)$ of them and they are of size $O(\log n)$ bits.

To compute the modular reduction of $(\prod_i A_i^{z_i}) \bmod N$ modulo $2^r$, we essentially need to compute the quotient $\lfloor \prod_i A_i^{z_i} / N \rfloor$ and reduce it modulo $2^r$. We re-express this using Barrett's reduction, replacing the division by $N$ by a multiplication followed by a binary shift. This shift complies with the reduction modulo $2^r$, and our problem becomes: to compute some bits of a large integer that has been expressed as a sum of $O(nm/\log n)$ integers.

Fortunately, the propagation of the carries in a sum is quite limited. In our case, we can expect carries to propagate only on about $O(\log(nm))$ bits. In other words, by taking a window of $O(\log(nm))$ bits, we can compute any bit of the sum with a large probability of success. More generally, we can compute $r$ bits of the exponentiation output using $r + O(\log nm)$ bits of intermediate storage.

In the case of factoring, one has $m = O(n)$ and the gate complexity of our circuit becomes $O(n^3)$, which is comparable to an implementation of Shor's algorithm with schoolbook multiplication. If a more efficient multiplication algorithm is used, then Shor's algorithm performs better. So does Regev's recent proposal [31]. In the case of short discrete logarithms of bit-size $d$ in a safe-prime group $Z_p^*$, we have $m = d$ by definition, which leads to a gate complexity $\tilde{O}(d^2 \log P)$. This is actually uncomparable with variants of Shor's algorithm and improves significantly over schoolbook multiplication.

**Output Compression.** As mentioned above, we combine the compression result of May and Schlieper [25] with the Ekerå-Håstad algorithm. However, May and Schlieper reason on average over compressing functions, while we can rely only on a single one (the truncation).

Fortunately, assuming the randomness of the exponentiation allows a reasoning quite close to the one of May and Schlieper. We compare the final quantum states between the uncompressed period-finding subroutine, and a compressed one in which the function $f$ is also composed with a random permutation of $Z_N^*$. We then prove that, on average over this random permutation, the probability to measure a given pair $(x, y)$ (or a fixed set of such pairs) does not deviate too much from half of the previous one. The *ad hoc* constant $r = 22$ follows essentially from the constant factors in the proof, and it could likely be optimized further.

*Results and Comparisons.* We implemented the main components of our algorithm in order to estimate its gate and qubit counts precisely. For RSA-2048, we estimate the Toffoli gate count at $2^{35.5}$ for a single circuit, for 1730 qubits

<footnote>$^2$ The sum needs also to be reduced modulo the product of all RNS primes; we omit this step here for ease of presentation.</footnote>
including ancillas. This can be compared to Gidney and Ekerå's estimations of $2^{31.3}$ Toffoli gates and 6144 qubits [19]. However, while their algorithm succeeds in a single run, our version of Ekerå-Håstad requires multiple runs: on average 40 for RSA-2048. This brings the total Toffoli gate count to $2^{40.9}$. For a safe-prime group $\mathbb{Z}_p^*$ where $P$ is a prime of 2048 bits, a DL instance where the logarithm has 224 bits should have 112 bits of classical security. Here our implementation uses 684 qubits, the circuit contains $2^{32.2}$ Toffoli gates and must be run 20 times. The code of our experiments is available at:

https://gitlab.inria.fr/capsule/quantum-factoring-less-qubits

**Outline.** In Section 2, we provide basic preliminaries of notation, arithmetic and quantum and reversible circuits. Section 3 introduces Shor's algorithm in more detail, recalls the Ekerå-Håstad variant and the May-Schlieper compression technique. Our new algorithm for computing $(G^x A^{-y} \mod N) \mod 2^r$ is detailed in Section 4, purely as a classical reversible computation. Then, in Section 5, we give the complete factoring algorithm and prove our main result (Theorem 4). We give some details on our cost estimates in Section 6. In Section B, we give a proof of Theorem 3 and in Section C, we give tables of parameters and resource estimates for RSA moduli and DL instances in $\mathbb{Z}_p^*$.

# 2 Preliminaries

In this section, we give some useful notation and basic preliminaries of arithmetic and quantum algorithms.

## 2.1 Notation

Let $n \in \mathbb{N}$ be the complexity parameter, typically the bit-size of the RSA modulus $N$ we are trying to factor. From Section 4 onwards, we will work with integers of bit-size either polylogarithmic in $n$ (typically $O(\log n)$), which will be denoted by lowercase letters, or bit-size polynomial in $n$ (typically from $O(n)$ to $O(n^2)$ bits), for which we use uppercase. This emphasizes that the former take negligible space w.r.t. the latter.

We use $[A]_p$ to denote $A \mod p$, i.e., the remainder in the Euclidean division of $A$ by $p$. We use $(A)_i$ to denote the $i$-th bit of $A$, where bit 0 is the least significant bit, so that: $A = \sum_i (A)_i 2^i$. Finally, given $x \in \mathbb{R}$, $\{x\} := x - \lfloor x \rfloor$ denotes the fractional part of $x$.

## 2.2 Modular Reduction and RNS

At one point in our algorithm, we need to perform modular reduction of a large number by a large modulus. For this we use a specific form of Barrett reduction.
**Proposition 1.** Let $N$ be a fixed modulus. Let $A \in \mathbb{N}$ that is not a multiple of $N$, and $k \in \mathbb{N}$ such that $2^k \ge AN$. Then we have:

$$ \lfloor \frac{A}{N} \rfloor = \lfloor \frac{A \lfloor 2^k / N \rfloor}{2^k} \rfloor . \qquad (1) $$

*Proof.* The proof follows trivially from the fact that $x \ge \lfloor x \rfloor > x - 1$ for all $x$. First, we have $\lfloor \frac{A \lfloor 2^k / N \rfloor}{2^k} \rfloor \le \frac{A}{N}$, but also $\lfloor \frac{A \lfloor 2^k / N \rfloor}{2^k} \rfloor \le \lfloor \frac{A}{N} \rfloor$, since it's an integer. Next:

$$ \forall A < 2^k, \quad \lfloor \frac{A \lfloor 2^k / N \rfloor}{2^k} \rfloor > \frac{A \lfloor 2^k / N \rfloor}{2^k} - 1 > \frac{A}{N} - \frac{A}{2^k} - 1 \ge \lfloor \frac{A}{N} \rfloor - 2 . $$

This implies that the approximated quotient can be underestimated by at most 1. However, if we make the additional assumption that $A$ is not a multiple of $N$, then we have: $\frac{A}{N} \ge \lfloor \frac{A}{N} \rfloor + \frac{1}{N}$. Therefore:

$$ \lfloor \frac{A \lfloor 2^k / N \rfloor}{2^k} \rfloor > \lfloor \frac{A}{N} \rfloor + \frac{1}{N} - \frac{A}{2^k} - 1 . \qquad (2) $$

In particular, setting $2^k \ge AN$ gives us $\lfloor \frac{A \lfloor 2^k / N \rfloor}{2^k} \rfloor > \lfloor \frac{A}{N} \rfloor - 1$ which implies the equality. $\square$

*Residue Number System (RNS).* RNS are a well-known method of circuit optimization, typically used to obtain small-depth circuits. We emphasize that our goal here is orthogonal: to obtain circuits with potentially large depth but small memory.

A RNS uses a basis of $\ell$ prime moduli, which we denote by $\mathcal{P} := \{p_1, \dots, p_\ell\}$, and represents a large integer $A$ by its residues modulo the $p_i$. Indeed, let $M = \prod_{p \in \mathcal{P}} p$, then by the Chinese Remainder Theorem we know that there is a bijection:

$$ [A]_M \mapsto [A]_{p_1}, \dots, [A]_{p_\ell} \qquad (3) $$

Furthermore, this bijection can be effectively computed as follows. For each $p \in \mathcal{P}$, let $M_p = M/p$ and $w_p = (M_p)^{-1} \mod p$. Then for any $A < M$:

$$ A = \left\lfloor \sum_{p \in \mathcal{P}} [A]_p w_p M_p \right\rfloor_M . \qquad (4) $$

The Prime Number Theorem gives us the asymptotic behavior of the prime counting function $\pi(x)$ (the number of primes smaller than $x$): $\pi(x) \sim \frac{x}{\log x}$. This means that, asymptotically, $\pi(x) = \frac{x}{\log x} + o(\frac{x}{\log x})$ and the total number of primes between $x$ and $2x$ is of order $\frac{2x}{\log(2x)} - \frac{x}{\log x} = \mathcal{O}(\frac{x}{\log(x)})$.

A consequence of this fact is that for any integer $n$, there exists a set of $\mathcal{O}(\frac{n}{\log n})$ of primes of size $\mathcal{O}(\log n)$ bits, which can be used to represent numbers of $n$ bits.
**Lemma 1 (Consequence of the Prime Number Theorem).** For any integer $n \ge 29$, there exists a set of prime numbers $p_1, \dots, p_\ell$ such that $\forall i, p_i < n$ and $\prod_i p_i > 2^n$. Furthermore $\ell = O(n/\log n)$.

*Explicit CRT.* It seems to be folklore knowledge that the quotient in the Euclidean division by $M$, which appears during the recombination step, can also be computed from the residues with the following formula:

$$q_M := \left| \sum_{p \in \mathcal{P}} [A]_p \frac{w_p M_p}{M} \right| = \left| \sum_{p \in \mathcal{P}} [A]_p \frac{w_p}{p} \right|.$$

While early works [26] suggest to simply use floating-point arithmetic with sufficiently low rounding error, Bernstein [5,6] gives an explicit formula to compute the quotient with fixed-point arithmetic. We will follow very similar steps in Section 4.2. Although our formula differs slightly from Lemma 3.1 in [5] (and Theorem 2.2 in [6]), it would have been possible to use this Lemma immediately at this step.

## 2.3 Quantum Algorithms

We describe quantum algorithms using the quantum circuit model, and refer to [27] for a detailed definition including qubits, quantum states, the ket $|\cdot\rangle$ notation and the Euclidean distance $\|\cdot\|$. We emphasize that we study only *logical* quantum circuits. We do not analyze how the obtained circuits should be mapped to a physical architecture, with additional costs of routing and distillation of magic states for certain gates.

We analyze the costs of our circuits as follows. The *width* is the number of qubits required. This always includes *ancilla* qubits, which are qubits whose state is initialized to $|0\rangle$ and returned to $|0\rangle$ afterwards. The *depth* is the amount of time steps required to run the circuit if independent gates are applied in parallel. The *gate count* is the total number of gates. While this work is motivated by quantum algorithms, the circuits that we describe use only classical reversible logic, for which NOT, CNOT and Toffoli form a universal set of gates.

Finally, our factoring algorithm requires several measurement results: the same circuit is run multiple times (we use alternatively the terms of “multiple runs” or “multiple measurements” since these are the same for us). Similarly to Regev’s trade-off on quantum factoring [31], it is often considered more practical to separate a quantum computation into more sub-computations of smaller complexities, as long as the entire algorithm is sufficiently robust to errors.

## 3 Preliminaries on Shor’s Algorithm

This section gives background on Shor’s algorithm [34], the Ekerå-Håstad variant [15], the precise analysis of [10] and its compressed version [25].
## 3.1 Shor's Algorithm

Shor's algorithm is a quantum algorithm to solve the Abelian hidden period problem. Consider an Abelian group ($G, +$) where operations are efficiently computable. Let $f: G \to \{0, 1\}^n$ be a function such that $\forall x, f(x + R) = f(x)$ for some hidden period $R$. The goal is to find $R$.

This generic period-finding view can be specialized for the factoring and discrete logarithms (DL) cases. However, the Ekerå-Håstad algorithm reduces factoring to an instance of DL, which is why we focus on the DL case.

**Shor's Algorithm for DL.** We work in the multiplicative group $Z_N^*$, where $N$ is either the RSA semiprime to factor or a prime number. Let $G$ be a generator of $Z_N^*$ and let $n = \lceil \log_2 N \rceil$. Consider an element $A$ such that $A = G^D$, where $D$ is the unknown discrete logarithm.

We define the function $f$ on $Z^2$ as: $f(x, y) = G^x A^{-y} \mod N$. We can observe that $\forall x, y, f(x, y) = f(x+D, y+1)$, meaning that $f$ has a period $(D, 1)$. In fact, it has additional periods forming a two-dimensional lattice of $Z^2$. We can run Shor's algorithm in two scenarios. Either we start without prior information on this lattice (aside from the expected size of $D$), or we start by computing the order of $G$ and $A$ modulo $N$, allowing us to restrict $f$ to a finite group.

We define the following subroutine $Q_f^{\text{shor}}$:

1. Initialize an input register of size $m = m_1 + m_2$ and a workspace register of size $n$ (not including ancilla qubits): $|0^{m_1}\rangle|0^{m_2}\rangle|0^n\rangle$

2. Create a uniform superposition in the input register, using Hadamard gates:

$$ \frac{1}{\sqrt{2^m}} \sum_{x=0}^{2^{m_1}-1} \sum_{y=0}^{2^{m_2}-1} |x, y\rangle |0^n\rangle $$

3. Compute $f$ into the output register: $\frac{1}{\sqrt{2^m}} \sum_{x=0}^{2^{m_1}-1} \sum_{y=0}^{2^{m_2}-1} |x, y\rangle|f(x, y)\rangle$

4. Apply a Fourier transform $QFT_{2^{m_1}} \otimes QFT_{2^{m_2}}$ on the input register

5. Measure and return the value of the input register

**Shor's Algorithm for Order-finding and Factoring.** To find the multiplicative order $R$ of $A$ in $Z_N^*$, one simply defines the function $f(x) = A^x \mod N$. The final measurement outputs a value $x$ which is close to some multiple of $\frac{2^m}{R}$. By choosing $m$ large enough, $R$ can be found from a constant number of measurements using a classical post-processing based on continued fractions. Shor proposed $m = 2n$ [34], where $n$ is the bit-size of $N$.

If the order $R$ is even, one has: $A^R = 1 \mod N \implies (A^{R/2} - 1)(A^{R/2} + 1) = 1 \mod N$. Assuming that $A^{R/2} - 1 \neq 0 \mod N$, it suffices to compute a GCD between $A^{R/2} - 1$ and $N$ to find one of its prime factors (since we focus on RSA keys, this is enough for us). Shor proved that the probability of achieving such a split is at least $1 - 2^{1-k}$, when $N$ admits $k$ distinct odd prime factors, which is $\ge \frac{1}{2}$ for RSA integers.

**Shor's Algorithm for DL.** In the DL case, one may first find the order of the elements in $Z_N^*$, and restrict the function to a finite group: we will have roughly $m_1 = m_2 = n$ and the QFT operations become the QFT in this group. The post-processing operation becomes also much simpler.
*Multi-Product Subroutine.* Whichever the size of the input registers, the main computational cost in Shor's DL algorithm comes from implementing the exponentiation $f(x, y) := G^x A^{-y} \mod N$. Because $G$ and $A$ are constants, this can be simplified into a *multi-product* subroutine.

The pair of inputs: $x, y := \sum_{i=0}^{m_1-1} x_i 2^i, \sum_{i=0}^{m_2-1} y_i 2^i$ can be identified with a pair of $(m_1, m_2)$-bit strings, or a single $m$-bit string $(x_0, \dots, x_{m_1-1}, y_0, \dots, y_{m_2-1})$. The output can be rewritten as:

$$f(x, y) = G^{\sum_{i=0}^{m_1-1} x_i 2^i} A^{-\sum_{i=0}^{m_2-1} y_i 2^i} \mod N = \prod_{i=0}^{m_1-1} (G^{2^i})^{x_i} \prod_{i=0}^{m_2-1} (A^{-2^i})^{y_i} \mod N \\ = \left( \prod_{i=0}^{m_1-1} (G^{2^i} \mod N)^{x_i} \prod_{i=0}^{m_2-1} (A^{-2^i} \mod N)^{y_i} \right) \mod N,$$

where both $(A^{-2^i} \mod N)$ and $(G^{2^i} \mod N)$ can be precomputed in polynomial time. The implementation of $f$ is therefore reduced to a *multi-product* circuit:

$$z_0, \dots, z_{m-1} \mapsto \prod_{i=0}^{m-1} A_i^{z_i} \mod N, \qquad (5)$$

where the $A_i$ are either powers of $A$ or powers of $G$, and the $z_i$ are either bits of $x$ or $y$. This circuit is usually implemented by a sequence of $m$ controlled modular multiplications by the $A_i$. To date, no efficient circuit is known for performing such a multiplication using less than $2n$ qubits.

*Semiclassical Fourier Transform.* The *semiclassical Fourier transform* is a way to insert the measurement of each bit of the input register between the operations of the Fourier transform $QFT_{2^{m_1}} \times QFT_{2^{m_2}}$. In the multi-product, each bit of the input is used only once, as a control for a modular multiplication. In that case it is possible to measure it *before* initializing and using the next bit. This is why the input register can be replaced by a single qubit *if* we compute the multi-product sequentially.

## 3.2 Ekerå-Håstad Variant: Optimizing the Input Register Size

The Ekerå-Håstad algorithm [15] is a variant of Shor's which reduces the number of input qubits for computing short discrete logarithms. This optimization can be used in the integer factorization problem for RSA moduli, as we recall below.

Let $d \le n$ be an upper bound on the bit-size of the DL. The Ekerå-Håstad subroutine has the same definition as $Q_f^{\text{shor}}$ defined above, except that the number of input qubits is set appropriately. One uses $d + \ell$ qubits in the register for $x$ and $\ell$ qubits in the register for $y$, where $\ell := \lfloor \frac{d}{s} \rfloor$ is much smaller than $d$, and the ratio $s$ is chosen appropriately.

Different from Shor's algorithm, one runs the subroutine a total of $\mu > s$ times, followed by a lattice-based classical post-processing of the measurement
outputs. Such a procedure is presented and analyzed in detail in [10]. For the case where one wants to do a single run, a refined analysis is given in [13], but we are interested in increasing $s$ as much as possible to reduce the space, and therefore, we consider multiple runs.

In [10], Ekerå shows that the number of measurements necessary tends asymptotically to $s+1$ when $s$ is fixed and $n$ tends to infinity. More precisely, for the post-processing it should be enough to perform $s+1$ runs and solve an instance of the Closest Vector Problem in a lattice of dimension $s+c$, where $c$ is some constant, and $c=1$ is expected to be enough asymptotically. By using $s = O(\log d)$ we ensure that this post-processing can be performed in polynomial time in $d$, using a lattice sieving algorithm of complexity $2^{O(\log d)} = \text{poly}(d)$.

**Ekerå-Håstad for RSA Factorization.** This method yields an interesting optimization in the factorization of RSA semiprimes. Consider $N = P \times Q$ where $N$ is of bit-size $n$, but $P$ and $Q$ are both of bit-size $n/2$. Let $\tilde{P} = \frac{P-1}{2}$ and $\tilde{Q} = \frac{Q-1}{2}$. Select a random element $G$ invertible modulo $N$ and let $R$ be its order: $G^R = 1 \bmod N$. Then $R$ divides $2\tilde{P}\tilde{Q}/\gcd(\tilde{P}, \tilde{Q})$.

We define $f(N) = (N-1)/2 - 2^{n/2-1} = 2\tilde{P}\tilde{Q} + \tilde{P} + \tilde{Q} - 2^{n/2-1}$. Let $A := G^{f(N)} = G^D$ for some $D < R$. Then: $D = f(N) \bmod R = \tilde{P} + \tilde{Q} - 2^{n/2-1} \bmod R$. This means that the discrete logarithm $D$ is small: $n/2$ bits instead of $n$.

Therefore, by computing the discrete logarithm of $A$, one obtains $\tilde{P} + \tilde{Q} - 2^{n/2-1} \bmod R$, which we can assume to be equal to $\tilde{P} + \tilde{Q} - 2^{n/2-1}$, i.e., one obtains $P+Q$. Since $N = PQ$ is also known, we can deduce $P$ and $Q$.

This means that for factoring RSA moduli of $n$ bits, the input register can be made as small as $\frac{n}{2} + O(\frac{n}{\log n}) = \frac{n}{2} + o(n)$ if we use $s = O(\log n)$. Note that up to date, this method was not used as a space optimization, since the semiclassical Fourier transform already replaced the input register by a single qubit. However, it yields a quantum-classical trade-off and allows to optimize the number of gates.

### 3.3 Compressing the Subroutine

May and Schlieper [25] studied the behavior of quantum period-finding algorithms, among which Shor's and Simon's [35], when the output of the function $f$ is post-processed by a hash function which reduces its size. They observed that the algorithm works almost in the same way, even if $h$ compresses the output down to a single bit. This is due to the following properties.

**Definition 1.** A hash function family $\mathcal{H}_t = \{h : \{0,1\}^n \to \{0,1\}^t\}$ is universal if for all $x, y \in \{0,1\}^n, x \neq y$, one has: $\Pr_{h \in \mathcal{H}_t} [h(x) = h(y)] = 2^{-t}$.

**Theorem 1 (Theorem 7 in [25].)** Let $f: \{0,1\}^m \to \{0,1\}^n$ and $\mathcal{H}_t$ be a universal hash function family. Let $Q_f^{\text{period}}$ be a quantum circuit that, before measurement, on input $|0^m\rangle|0^n\rangle$ yields a superposition:

$$|\Phi\rangle = \sum_{y \in \{0,1\}^m} \sum_{f(x) \in \text{Im}(f)} w_{y,f(x)} |y\rangle |f(x)\rangle \quad (6)$$
satisfying

$$ \forall y \neq 0, \quad \sum_{f(x) \in \mathrm{Im}(f)} w_{y, f(x)} = 0. \qquad (7) $$

Let $p(y)$, resp. $p_h(y)$, be the probability to measure $|y\rangle$, $y \neq 0$ in the m input qubits when applying $Q_f^{\text{period}}$, resp. $Q_{h \circ f}^{\text{period}}$ with h selected u.a.r. from $\mathcal{H}_t$. Then $p_h(y) = (1 - 2^{-t})p(y)$.

Equation 7 is called the cancellation criterion. This criterion is satisfied by the subroutine $Q_f^{\text{shor}}$, but more generally by quantum period-finding of the same family, like Simon's [35] and Ekerå-Håstad.

**Lemma 2 (Lemma 6 & 7 in [25]).** The $Q_f^{\text{shor}}$ subroutine satisfies the cancellation criterion (Equation 7).

When this property is satisfied, Theorem 1 shows that we can hash the output register. Measuring the input register then yields a similar distribution as before, where the probability to measure 0 increases (up to 1/2 when $t = 1$) and the other probabilities are rescaled accordingly. Measuring 0 reveals nothing about the period; we can just discard these results and do more measurements to succeed. However, how to compute $h \circ f$ in a space-efficient way (without essentially computing $f$, then $h$) was left as an open question in [25].

*New Compression Theorem.* May and Schlieper [25] remarked that the requirement of a universal hash function family may be relaxed in practice. However, with a single hash function, it seems difficult to show that $p_h(y)$ is close to $\frac{1}{2}p(y)$ for a given nonzero $y$; indeed, the proof of Theorem 1 largely relies on the fact that we can reason on average on the function $h$.

To adapt this strategy for our case, we prove a new “compression” result. We select a parameter $r > 0$. We compress the output of $f$ by truncating it to the first $r$ bits, then taking the dot-product with a random mask $\beta$. The mask is chosen uniformly at random from all non-zero bit-strings in $\{0, 1\}^r$ before each call to the compressed subroutine. Using $r = n$ and a mask $\beta$ of $n$ bits would bring us back to Theorem 1, as this would form a universal hash function family with one-bit output.

The heuristic that we need to use is Heuristic 1. Essentially, when considering an instance of the DL or factoring problem, the function $f$ behaves as a random periodic function $\{0, 1\}^m \to \mathbb{Z}_N^*$. When $r$ is a large enough constant, we prove in Section B that a similar property as Theorem 1 is obtained. That is, the distribution of outputs is similar to the one in the uncompressed algorithm, and its analysis can be reused.

## 3.4 Compressing with Approximate Arithmetic

It has been observed in previous works that Shor's algorithm does not require an exact modular exponentiation circuit. In fact, it is enough to return a good result with large probability on a random instance. Zalka first proposed such a
strategy in [37] and coined the term “deterministic errors”. Further, the *coset representation of modular integers* [38] is both approximate and inherently quantum, as it represents integers modulo *N* using a superposition. In [17], Gidney introduced the technique of *oblivious carry runways*. These techniques have been used in state-of-the-art resource estimates of quantum factoring [19].

In our case, we will have an erroneous circuit computing a “compressed” version of the output, and we need multiple measurements. From now on, we write $h$ instead of $h \circ f$ for the “compression” of $f$ which truncates it to $r$ bits.

Instead of implementing $h$, we can only implement a function $h'$ such that $h'(x) = h(x)$ with probability $1-p$ only. We do not make any assumption as to how the errors are distributed among the inputs.

**Lemma 3.** Let $\mathcal{A}_i$ be an algorithm that uses a compressed period-finding subroutine with the ideal function $h$, makes $\mu$ measurements, post-processes the outputs, and succeeds with probability $p_i$. Let $\mathcal{A}_r$ be the same algorithm replacing $h$ by $h'$. Then $\mathcal{A}_r$ succeeds with probability at least: $p_r \ge p_i - 8\sqrt{\mu\sqrt{p}}$.

*Proof.* We start by bounding the difference between the “real” and “ideal” runs of compressed-period subroutine, using the Euclidean distance between quantum states before the last QFT operation and measurement. Indeed, if we define:

$$ |\psi_r\rangle = \frac{1}{2^{m/2}} \sum_{z=0}^{2^m-1} |z\rangle |h'(z)\rangle \quad \text{and} \quad |\psi_i\rangle = \frac{1}{2^{m/2}} \sum_{z=0}^{2^m-1} |z\rangle |h(z)\rangle, \\ \text{then:} \quad \| |\psi_e\rangle \|^2 := \| |\psi_r\rangle - |\psi_i\rangle \|^2 = (p2^m) \frac{4}{2^m} = 4p, \quad (8) $$

and, since the last QFT step is a unitary, it preserves the Euclidean distance:

$$ \|(I \otimes \text{QFT})(|\psi_r\rangle) - (I \otimes \text{QFT})(|\psi_i\rangle)\| = \| |\psi_r\rangle - |\psi_i\rangle \| = 2\sqrt{p}. \quad (9) $$

Since we perform $\mu$ measurements in total, we have $\mu$ copies of the subroutine, and we can bound the Euclidean distance between the real and ideal runs as follows:

$$ \|(\psi_r)\otimes\mu - (\psi_i)\otimes\mu\| = \sqrt{\mu}(2\sqrt{p}). \quad (10) $$

Therefore, the total variation distance between the probability distributions resulting from measuring the ideal and the real runs is bounded by: $4(2\sqrt{\mu\sqrt{p}})$ by Lemma 3.6 in [7]. The result of the “ideal” and “real” algorithm is a function of these measurement results. Therefore:

$$ |p_r - p_i| \le 4\sqrt{\mu}2\sqrt{p} \implies p_r \ge p_i - 8\sqrt{\mu\sqrt{p}}. \quad (11) $$

This concludes the proof. □
<table><caption>**Table 1.** Quantum space-optimized factoring algorithms. The input is an *n*-bit number. The gate count is for the entire algorithm, as ours (last lines) requires $O(\log n)$ independent runs. The difference between RSA and general integers comes from the variant of Shor's algorithm and post-processing that can be applied (see Section 5 for the general case).</caption><thead><tr><th>Algorithm</th><th>Qubits</th><th>Gates (Toffolis)</th></tr></thead><tbody><tr><td>[3,36,22,16,15]</td><td>2n + O(1)</td><td>O(n<sup>3</sup> log n)</td></tr><tr><td>[38]</td><td>1.5n + O(1)</td><td>O(n<sup>3</sup> log n)</td></tr><tr><td>[19]</td><td>3n + 0.002n log n</td><td>0.3n<sup>3</sup> + 0.0005n<sup>3</sup> log n</td></tr><tr><td>[24]</td><td>2n + O(log n)</td><td>O(n<sup>2.29</sup>)</td></tr><tr><td>This work (RSA)</td><td>n/2 + o(n)</td><td>O(n<sup>3</sup> log n)</td></tr><tr><td>This work (general integers)</td><td>n + o(n)</td><td>O(n<sup>3</sup> log n)</td></tr></tbody></table>

## 3.5 Overview of Related Works for Factoring

Since Shor's original paper, many authors have optimized the algorithm in terms of depth, gate count or qubit usage. Since we focus here on space requirements, we list in Table 1 the number of qubits required by different logical circuit implementations.

The complexity of implementing Shor's algorithm depends crucially on the multiplication circuit that is used. Since multiplication of *n*-bit integers can be done in $O(n \log n)$ bit operations [23], there exists a quantum circuit for multiplying *n*-bit integers using $O(n \log n)$ gates and qubits, and some of the gate counts given in the literature follow this asymptotic rule. However, when aiming for the space complexity, the multiplication circuits used have been mostly schoolbook multiplication (combined with advanced techniques such as windowed arithmetic [18] or coset representation of modular integers [38]) or QFT-based [9], requiring at least $O(n^2)$ gates. Recently, Kahanamoku-Meyer and Yao proposed a new efficient multiplication circuit requiring few ancillas [24], which performs better asymptotically and in practice.

Regev [31] introduced another quantum factoring algorithm which can be regarded as a multi-dimensional variant of Shor's, allowing to reduce the circuit size by a factor $O(\sqrt{n})$ at the expense of making $O(\sqrt{n})$ measurements. If schoolbook multiplication is used, this reduces the gate count of each run from $O(n^3)$ to $O(n^{5/2})$. Ragavan and Vaikuntanathan [30] showed how to implement this algorithm with $O(n)$ qubits. The algorithm was also extended to Discrete Logarithms in $\mathbb{Z}_p^*$ [14]. However, regarding space complexity, Regev's algorithm is worse than previous works, and [30] reports $12.32(1 + \varepsilon)n$ qubits (where $\varepsilon$ is a small heuristic constant). Whether our strategy can be applied here remains an open question.

## 4 Compressed Modular Multi-Product Circuit

In this section, we explain the core of our approach: a space-efficient circuit for computing a compressed modular multi-product.
We work in the group $Z_N^*$ and denote $n = \lceil \log_2 N \rceil$. Let $r$ be a constant which will be chosen appropriately later on. A modular exponentiation circuit as used in Shor's and Ekerå-Håstad's algorithms reduces to a modular multi-product, as explained in Section 3.1.

Let $m \le 2n$ and $A_0, \dots, A_{m-1}$ be arbitrary $n$-bit integers. Given an input $X$ identified as a bit-string $x_0, \dots, x_{m-1}$, we define: $A_X := \prod_{i=0}^{m-1} A_i^{x_i}$. Our circuit will compute $[[A_X]_N]_{2^r}$ using $O(nm^2)$ gates and $O(\log n + \frac{m}{\log n}) = o(n)$ ancilla space, for a total depth $O(nm \log^3 n)$ (Theorem 2). This space can even be reduced to $O(\log n)$, but the depth would increase to $O(nm^2)$.

This circuit fails on some inputs. However, under Heuristic 2 (detailed below), its probability of failure can be reduced to an arbitrary constant.

## 4.1 Main Idea: a Residue Number System (RNS)

We will use an RNS to represent the multi-product $A_X$, i.e., a number of at most $nm$ bits. Let $\mathcal{P} = \{p_1, \dots, p_\ell\}$ be the prime numbers for the RNS. By Lemma 1 we have $\ell = O(mn/\log(mn)) = O(mn/\log n)$ and $\forall p \in \mathcal{P}, p \le mn$. We let $w := \lceil \log_2 \max_{p \in \mathcal{P}} p \rceil$. The product $M := \prod_{p \in \mathcal{P}} p$ is upper bounded by: $M < 2^{nm}p_\ell \le 2^{nm+w}$. Indeed, by definition of the RNS, we have $\prod_{i=0}^{\ell-1} p_i < 2^{nm} \implies M < 2^{nm}p_\ell$. Thus $M$ can get bigger than $2^{nm}$ due to the last prime factor, but only by a small number of bits. Finally, we define: $\alpha := \lceil \log_2 (\sum_{p \in \mathcal{P}} p) \rceil$. In particular $\alpha \le w + \lceil \log_2 \ell \rceil$.

For all $p$, let $M_p = M/p$ (which is an integer) and $w_p = (M_p)^{-1} \mod p$, and notice that $M_p w_p < M$. Let us define:

$$A'_X := \sum_{p \in \mathcal{P}} \left[ \underbrace{A_X}_{w \text{ bits}} \right]_p \underbrace{M_p w_p}_{mn+w \text{ bits}} \le 2^{mn+w+\alpha}. \quad (12)$$

From there, we need to perform two layers of modular reduction: modulo $M$ and modulo $N$, as we have: $[A_X]_N = [[A'_X]_M]_N$. We define two quantities which are the quotients of both Euclidean divisions:

$$\left\{ \begin{array}{l} q_M := \lfloor A'_X / M \rfloor = \left\lfloor \frac{\sum_{p \in \mathcal{P}} [A_X]_p M_p w_p}{M} \right\rfloor \\ Q_N := \lfloor [A'_X]_M / N \rfloor = \left\lfloor \frac{\left( \sum_{p \in \mathcal{P}} [A_X]_p M_p w_p \right) - q_M M}{N} \right\rfloor \end{array} \right. \quad (13)$$

We notice here that $q_M$ is a small number, which is why we used a lowercase letter for the notation. Indeed, we have: $A'_X \le 2^{mn+w+\alpha}$ and $M \ge 2^{nm}$ by definition of the RNS, thus $q_M < 2^{w+\alpha} = \text{poly}(mn)$.

Finally, we can express our end result as:

$$ \begin{aligned} [[[A'_X]_M]_N]_{2^r} &= [(A'_X - q_M M) - Q_N N]_{2^r} \\ &= [A'_X]_{2^r} - [q_M]_{2^r} [M]_{2^r} - [Q_N]_{2^r} [N]_{2^r} \mod 2^r . \end{aligned} $$
We observe that $[A'_{X}]_{2^r}$ can be computed as:

$$[A'_{X}]_{2^r} = \sum_{p} [[A_{X}]_{p}]_{2^r} [M_{p}w_{p}]_{2^r} \mod 2^r,$$

using a series of multiplications and additions modulo $2^r$. This cost is insignificant as $r$ is a small constant ($r = 22$ will be used in Section 5). Besides, $[M]_{2^r}$ and $[N]_{2^r}$ are constants.

It can be also noticed that in this expression, $[A'_{X}]_{2^r} - [q_M]_{2^r} [M]_{2^r}$ is equal to zero with large probability. This is because $A_X$ is a multi-product of random integers, half of which are multiples of 2. As $r$ is typically much smaller than $m/2$, we have that $[A_X]$ is often divisible by $2^r$, thus $[A_X]_{2^r}$ is zero.

Next, we will see how we compute $q_M$, then $[q_M]_{2^r}$ and $[Q_N]_{2^r}$. For this, we will make two successive approximations. The first one requires $X$ to have bounded Hamming weight, which is ensured with high probability if $X$ is selected uniformly at random. The second one is probabilistic, and its probability of success is a tunable parameter in our algorithm.

The Hamming Weight Constraint on $X$. The success of our algorithm depends on the Hamming weight of $X$. We have the following.

**Lemma 4.** When $X \in \{0, 1\}^m$ is chosen u.a.r., the following holds with probability $1 - 2 \exp(-\frac{4}{6}m^{1/3})$:

$$hw(X) \le \frac{m}{2} + m^{2/3} \quad \text{and} \quad A_X \le N^{\frac{m}{2} + m^{2/3}}. \qquad (14)$$

*Proof.* Since we just need to count the 1-coordinates of $X$, we use a multiplicative Chernoff bound:

$$\Pr \left( \left| hw(X) - \frac{m}{2} \right| \ge 2m^{-1/3} \times \frac{m}{2} \right) \le 2 \exp \left( -(2m^{-1/3})^2 \frac{m}{6} \right) \\ \Rightarrow \Pr \left( \left| hw(X) - \frac{m}{2} \right| \ge m^{2/3} \right) \le 2 \exp \left( -\frac{4}{6}m^{1/3} \right).$$

The second inequality is a direct implication. □

<figure><img src="image_4.png" /></figure>

An immediate consequence of this fact is that we do not need our RNS to represent $nm$-bit numbers, but only $n(\frac{m}{2} + m^{2/3})$-bit numbers. To be more precise, we modify our definition as follows: we let $\mathcal{P} = \{p_1, \dots, p_\ell\}$ be $O(mn/\log n)$ prime numbers such that $M = \prod_{p \in \mathcal{P}} p \ge 2^{n(\frac{m}{2} + 2m^{2/3})}$. The additional factor $2^{nm^{2/3}}$ has a reason which will be explained below.

## 4.2 Reduction Modulo M and First Approximation

We will now see how we compute $q_M$. Recall its definition:

$$q_M := \left\lfloor \frac{\sum_{p \in \mathcal{P}} [A_X]_p w_p M_p}{M} \right\rfloor = \left\lfloor \sum_{p \in \mathcal{P}} [A_X]_p \frac{w_p}{p} \right\rfloor. \qquad (15)$$
Here $p, w_p, [A_X]_p$ and eventually $q_M$ are all small numbers (bit-size logarithmic in $n$), so intuitively we may compute this sum directly by approximating $\frac{1}{p}$ by $\frac{1}{2^u} \lfloor 2^u/p \rfloor$, where $u = \mathcal{O}(\log n)$ is chosen appropriately.

We note that the following Lemma is essentially a variant of the Explicit CRT, where we also allow a small probability of failure, which is asymptotically negligible in $n$. This result in itself is not new, see for example [5,6]. It would be possible here to use the previous Explicit CRT from [5,6], and it would just induce a small change in the formula for $q_M$.

**Lemma 5.** Let $u = \lfloor \log_2 \sum_{p \in \mathcal{P}} p^2 \rfloor$. Asymptotically in $n$, with probability 1 – negl($n$), the following holds:

$$q_M = \left\lfloor \frac{1}{2^u} \left( \sum_{p \in \mathcal{P}} [A_X]_p w_p \lfloor 2^u/p \rfloor \right) \right\rfloor + 1 . \quad (16)$$

*Proof.* Recall that we chose our RNS product $M$ such that $M \ge 2^{n(\frac{m}{2}+2m^{2/3})}$, but with high probability we have $A_X \le 2^{n(\frac{m}{2}+m^{2/3})}$. As a consequence: $0 < \frac{A_X}{M} \le 2^{-nm^{2/3}}$. and:

$$\left\{ \sum_{p \in \mathcal{P}} [A_X]_p \frac{w_p}{p} \right\} = \frac{A_X}{M} \le 2^{-nm^{2/3}}.$$

By choosing $u = \lfloor \log_2 \sum_{p \in \mathcal{P}} p^2 \rfloor$ as in the statement of the lemma, we have $2^u > \sum_{p \in \mathcal{P}} p^2$. Then we have the following inequalities (for $p \ne 2$):

$$\frac{2^u}{p} \ge \lfloor \frac{2^u}{p} \rfloor + \frac{1}{p} \quad \text{and} \quad \lfloor \frac{2^u}{p} \rfloor \ge \frac{2^u}{p} - 1 . \quad (17)$$

On the one hand, we have:

$$\left( \sum_{p \in \mathcal{P}} [A_X]_p \frac{w_p}{p} \right) - \left( \sum_{p \in \mathcal{P}} [A_X]_p \frac{w_p}{2^u} \right) \le \frac{1}{2^u} \left( \sum_{p \in \mathcal{P}} [A_X]_p w_p \lfloor 2^u/p \rfloor \right) . \quad (18)$$

Therefore, our choice of $u$ ensures that:

$$q_M - 1 \ge \left\lfloor \frac{1}{2^u} \left( \sum_{p \in \mathcal{P}} [A_X]_p w_p \lfloor 2^u/p \rfloor \right) \right\rfloor . \quad (19)$$

On the other hand:

$$\frac{1}{2^u} \left( \sum_{p \in \mathcal{P}} [A_X]_p w_p \lfloor 2^u/p \rfloor \right) \le \left( \sum_{p \in \mathcal{P}} [A_X]_p \frac{w_p}{p} \right) (1 - 2^{-u}) . \quad (20)$$
Asymptotically in $n$, we have seen that the fractional part of $\sum_{p \in \mathcal{P}} [A_X]_p \frac{w_p}{p}$ is
very small. With the value of $u$ chosen, we have $u = \text{polylog}(n)$, and so:

$$
\left\{ \sum_{p \in \mathcal{P}} [A_X]_p \frac{w_p}{p} \right\} < 2^{-u} \left( \sum_{p \in \mathcal{P}} [A_X]_p \frac{w_p}{p} \right) . \qquad (21)
$$

Indeed, $w_p \ge 1$ for all $p$, and for at least one $p \in P$ we have $[A_X]_p \ge 1$ (otherwise $A_X$ would be divisible by all primes, which is impossible since it is smaller than $M$). This means that: $\sum_{p \in \mathcal{P}} [A_X]_p \frac{w_p}{p} \ge 1/\mathcal{O}(mn)$, due to the bound on the primes. Furthermore by choosing $u = \text{polylog}(n)$ we have (asymptotically) $2^{-u}/\mathcal{O}(mn) < 2^{-nm^{2/3}}$, ensuring that the result holds.

Consequently this inequality entails:

$$
\frac{1}{2^u} \left( \sum_{p \in \mathcal{P}} [A_X]_p w_p \lfloor 2^u / p \rfloor \right) < \sum_{p \in \mathcal{P}} [A_X]_p \frac{w_p}{p} - \left\{ \sum_{p \in \mathcal{P}} [A_X]_p \frac{w_p}{p} \right\} = q_M, \quad (22)
$$

which completes our proof.

□

At this point, we notice that $q_M$ can be computed on the fly (by computing
the $[A_X]_p$) using low space. The value of $q_M$ is important both for having $[q_M]_{2^r}$,
but also because it appears in $Q_N$. We can now turn ourselves towards the second
step, i.e., the computation of $[Q_N]_{2^r}$.

Remark 1. Strictly speaking, this first approximation is not necessary. We could choose an RNS representing $n(m+1)$-bit numbers, and the computation of $q_M$ by Equation 16 would then work with certainty for all inputs $X$. However, this source of errors is negligible, and the gain in practice is significant enough to justify taking a smaller RNS.

4.3 Reduction Modulo N and Second Approximation

For the computation of $[Q_N]_{2^r}$, we will use Barrett reduction. We introduce a
parameter $t_N$ to satisfy the condition of Proposition 1, i.e., $2^{t_N} \ge A_X N$, so we
can choose $t_N = \lfloor n(\frac{m}{2} + m^{2/3}) \rfloor + n$. We also remark that:

**Lemma 6.** For any choice of $X$, $A_X$ is not a multiple of $N$.

This follows from the fact that all numbers in the multi-product are powers
of A, which is (assumed to be) prime with N. Therefore, Proposition 1 applies
and Q_N has the expression:

$$
Q_N = \left\lfloor \frac{1}{2^{t_N}} \left( \sum_{p \in \mathcal{P}} [A_X]_p M_p w_p \lfloor 2^{t_N} / N \rfloor - q_M M \lfloor 2^{t_N} / N \rfloor \right) \right\rfloor . \quad (23)
$$
We have:

$$[Q_N]_{2^r} = \left( \sum_{p \in \mathcal{P}} [A_X]_p M_p w_p \lfloor 2^{t_N}/N \rfloor - q_M M \lfloor 2^{t_N}/N \rfloor \right) \gg t_N \mod 2^r, \quad (24)$$

where $\gg$ is a bit-shift, i.e., we need to compute the bits at positions $t_N + 1$ to $t_N + r$ in the previous equation. We will use the fact that $q_M$ is known to us at this point. For convenience, we replace the difference by a sum, since we work modulo $2^{t_N+r}$:

$$[Q_N]_{2^r} = \left( \sum_{p \in \mathcal{P}} [A_X]_p M_p w_p \lfloor 2^{t_N}/N \rfloor + q_M (2^{t_N+r} - M \lfloor 2^{t_N}/N \rfloor) \right) \gg t_N \mod 2^r .$$

Intuitively, there is no need to compute the entire sum, as the least significant bits only have a very small influence on the bits from $t_N + 1$ to $t_N + r$. To view this, we first decompose the modular residues $[A_X]_p$ and $q_M$ on individual bits, and express $[Q_N]_{2^r}$ as a large sum:

$$[Q_N]_{2^r} = \left( \sum_{p \in \mathcal{P}} \sum_i ([A_X]_p)_i 2^i M_p w_p \lfloor 2^{t_N}/N \rfloor + \sum_i (q_M)_i 2^i (2^{t_N+r} - M \lfloor 2^{t_N}/N \rfloor) \right) \gg t_N \mod 2^r .$$

Therefore we can see $[Q_N]_{2^r}$ as a sum of $\le \sum_{p \in \mathcal{P}} [\log_2 p] + [\log_2 q_M]$ integers. How many depends on the current values of $[A_X]_p$ and $q_M$ (but we prefer to overestimate). These integers behave as if they were drawn uniformly at random$^3$.

We introduce a parameter $u'$ and approximate $[Q_N]_{2^r}$ by truncating these integers to $u'$ bits, and taking the bits $u' + 1$ to $u' + r$ in the sum:

$$[Q_N]_{2^r} \approx \left( \sum_{p \in \mathcal{P}} \sum_i \left( ([A_X]_p)_i \lfloor 2^i M_p w_p \lfloor 2^{t_N}/N \rfloor / 2^{t_N - u'} \rfloor + \sum_i (q_M)_i \lfloor 2^i (2^{t_N+r} - M \lfloor 2^{t_N}/N \rfloor) / 2^{t_N - u'} \rfloor \right) \gg u' \mod 2^r . \quad (25)$$

The amount of precision we need is related to the number of integers we are summing. In a sum of $t$ random integers we need a precision of at least $\lfloor \log_2 t \rfloor$ bits to succeed with constant probability. The reason is the same as in *oblivious carry runways* [17]. When truncating with $\lfloor \log_2 t \rfloor + \nu$ bits, the probability that carries propagate all the way from the truncated part of the integers to the wanted bit (and the bit is flipped as a result) is $2^{-\nu}$.

<footnote>$^3$ This is not exactly the case because they have some zero LSBs, but since we are looking at the bits $t_N + 1$ to $t_N + r$, which are quite far in the sum, the LSBs are insignificant.</footnote>
This is what happens if the integers are drawn at random. This is not the case for us, as these integers are precomputed cofactors depending on the RNS. Experimentally, we observe that this property remains satisfied, and formulate it as a heuristic.

Heuristic 3. When choosing $u' = [\log_2(\sum_{p \in \mathcal{P}} [\log_2 p]) + [\log_2 q_M])] + \nu$, for random inputs $X$, Equation 25 is an equality with probability $\ge 1 - 2^{-\nu}$.

In fact, this heuristic is the only one underlying Heuristic 2. Indeed, all errors come from the computation of $q_M$ and $[Q_N]_{2^r}$. The first approximation is not heuristic: the $X$ in $A_X$ is required to have bounded Hamming weight, which happens with high probability in our case, according to Lemma 4. If Heuristic 3 is true, then Heuristic 2 is also true: the probability of error can be brought down an arbitrary constant, at a low cost.

## 4.4 Summary

Thanks to the approximations, both $q_M$ and $[Q_N]_{2^r}$ are computed with $o(n)$ space. More precisely, let $\gg$ be a bitwise right-shift, then we have:

$$ \begin{aligned} q_M = & \left( \left( \sum_{p \in \mathcal{P}} [A_X]_p \underbrace{w_p \lfloor 2^u / p \rfloor}_{\text{Precomputed}} \right) \gg u \right) + 1 \\ [Q_N]_{2^r} = & \left( \sum_{p \in \mathcal{P}} \sum_i ([A_X]_p)_i \underbrace{\left[ \lfloor 2^i M_p w_p \lfloor 2^{t_N}/N \rfloor / 2^{t_N-u'} \rfloor \right]_{2^{u'+r}}}_{\le 2^{u'+r} \text{ and precomputed}} \right. \\ & \left. + \sum_i (q_M)_i \underbrace{\left[ \lfloor 2^i (2^{t_N+r} - M \lfloor 2^{t_N}/N \rfloor) / 2^{t_N-u'} \rfloor \right]_{2^{u'+r}}}_{\le 2^{u'+r} \text{ and precomputed}} \right) \gg u' \end{aligned} \quad (26) $$

Therefore, we only need to compute large (controlled) sums of precomputed integers (which we call cofactors), depending on the bits of $[A_X]_p$ and $q_M$. Since $r$ is a constant, $u = \mathcal{O}(\log(mn))$, $q_M = \text{poly}(mn)$ and $u' = \mathcal{O}(\log(mn))$, the amount of temporary storage for $q_M$ and $Q_N$ is in $\mathcal{O}(\log(mn)) = \mathcal{O}(\log n)$. The cofactors are the following:

$$ \left\{ \begin{aligned} B_p &:= [M_p w_p]_{2^r} \\ C_{p,i} &:= [2^i w_p \lfloor 2^u / p \rfloor]_{2^{u+\lfloor \log_2 q_M \rfloor+1}} \\ D_{0,i} &:= \left\lfloor \frac{2^i (2^{t_N+r} - M \lfloor 2^{t_N}/N \rfloor)}{2^{t_N-u'}} \right\rfloor_{2^{u'+r}} \\ D_{p,i} &:= \left\lfloor \frac{2^i M_p w_p \lfloor 2^{t_N}/N \rfloor}{2^{t_N-u'}} \right\rfloor_{2^{u'+r}} \end{aligned} \right. \quad (27) $$

We summarize the resulting algorithm as Algorithm 1, with a layout close to how it will be implemented as a quantum circuit.

Under the heuristics above, we can prove our main result.
<caption>**Algorithm 1** Approximate multi-product algorithm.</caption>

**Input:** $X$
**Output:** $[[A_X]_N]_{2^r}$
**Precomputed:** cofactors $B_p, C_{p,i}, D_{0,i}, D_{p,i}$
1: $qM \leftarrow 0$ \quad $\triangleright$ value of $q_M$ ($\mathcal{O}(\log n)$ bits)
2: $QN \leftarrow 0$ \quad $\triangleright$ value of $[Q_N]_{2^r}$ ($\mathcal{O}(\log n)$ bits)
3: $Res \leftarrow 0$ \quad $\triangleright$ value of the result ($r$ bits)
4: **for all** $p$ in the RNS do
5: &nbsp;&nbsp;&nbsp;&nbsp;$x \leftarrow [A_X]_p$ \quad $\triangleright$ using the subroutine
6: &nbsp;&nbsp;&nbsp;&nbsp;$x := x_0 + 2x_1 + \dots$
7: &nbsp;&nbsp;&nbsp;&nbsp;**for all** $0 \le i \le \lceil \log_2 p \rceil$ **do**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $x_i = 1$ **then**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$qM \leftarrow qM + C_{p,i}$ \quad $\triangleright$ The computation is done on $u + \lceil \log_2 q_M \rceil + 1$ bits
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$QN \leftarrow QN + D_{p,i}$ \quad $\triangleright$ The computation is done on $u' + r$ bits
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end if**
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end for**
13: $Res \leftarrow Res + [x]_{2^r} B_p$ \quad $\triangleright$ Modulo $2^r$
14: **end for**
15: $qM \leftarrow (qM \gg u) + 1$
16: $Res \leftarrow Res - [qM]_{2^r} [M]_{2^r}$
17: $q_M := b_0 + 2b_1 + \dots$
18: **for all** $0 \le i \le \lceil \log_2 q_M \rceil$ **do**
19: &nbsp;&nbsp;&nbsp;&nbsp;**If** $b_i = 1$ **then** $QN \leftarrow QN + D_{0,i}$
20: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
21: $QN \leftarrow QN \gg u'$
22: $Res \leftarrow Res - [QN]_{2^r} [N]_{2^r}$
23: **Return Res**

**Theorem 2.** Assume that $m \le 2n$ and $r$ is a constant. For any constant $\varepsilon > 0$, there exists a reversible logical circuit for compressed multi-product which, on input $(X, 0)$ (where $X$ is represented on a register of size $m$, and $0$ is an ancilla register), returns $(X, [[A_X]_N]_{2^r})$, and succeeds with probability $1 - \varepsilon$ for inputs $X$ chosen uniformly at random, under Heuristic 3. It uses $\mathcal{O}(nm^2)$ gates, depth $\mathcal{O}(nm \log^3 n)$ and $\mathcal{O}(\log n + \frac{m}{\log n})$ ancillas.

*Proof.* The circuit layout follows Algorithm 1. We set the parameters $u$ and $u'$ so that the probability of success of the circuit is sufficient.

Throughout the computation we maintain a register for $q_M$, a register for the result (of $r$ bits) and a register for $Q_N$. Each time a new residue is computed, we perform $\mathcal{O}(\log n)$ controlled additions by constants in the registers for $q_M$ and $Q_N$. We also sum $[[A_X]_p]_{2^r} [M_p w_p]_{2^r}$ in the result register.

By Lemma 1, there are $\mathcal{O}((nm)/\log n)$ primes and we compute each residue only once. For each residue, we use the multi-product circuit of Lemma 8, which requires $\frac{m}{\log n}$ ancilla qubits to reach a low depth.
Once the whole sum for $q_M$ has been computed, we shift it by $u$ bits and increment. We have obtained $q_M$. At this point the result register also contains $[A'_X]_{2^r}$, and after subtracting $[qM]_{2^r} [M]_{2^r}$ it contains $[A'_X - q_M M]_{2^r}$.

We use the bits of $q_M$ to complete the sum for $Q_N$, by making new controlled additions for each one with their own precomputed cofactors. This step is computationally negligible with respect to the other additions that we just performed.

When we have finished the sum for $Q_N$, we select its bits at position $u' + 1$ to $u' + r$, which give $[Q_N]_{2^r}$. We subtract $[Q_N]_{2^r} [N]_{2^r}$ from the result register, which gives the result of the algorithm.

Then, we erase the accumulator registers by recomputing the residues and performing a series of controlled subtractions or additions.

Since the accumulator registers are also of size $O(\log n)$, the circuit uses $O(\log n)$ working bits in addition of those required for the RNS residues. The gate count is dominated by the computation of the residues, which we do using Lemma 8. $\square$

## 4.5 Modular Multi-Product in the RNS

The main problem with the computation of $[A_X]_p$ is its sequentiality. Indeed, if we follow the blueprint of modular multi-product in Shor's algorithm, we do a sequence of $m$ controlled modular multiplications by $[A_i]_p$. This takes depth $\tilde{O}(m)$, and gates are applied only on a work register of size $O(\log p) = O(\log n)$, while the control qubits remain idle for the most part.

In the following, since we work at low scales, the asymptotic formulas that we give assume the use of schoolbook addition and multiplication circuits: on $\log n$ bits, addition costs $O(\log n)$ gates and depth, and multiplication costs $O(\log^2 n)$ gates and depth.

Our first improvement on the naive multi-product is to replace the controlled modular multiplications by a sequence of controlled additions.

**Lemma 7.** Let $a_0, \dots, a_{m-1} \in \mathbb{Z}_p$, and $p$ be a prime, with $m \le 2n$ and $p = O(mn)$. There exists a circuit performing the multi-product modulo $p$:

$$ |x_0, \dots, x_{m-1}\rangle |0\rangle \mapsto |x_0, \dots, x_{m-1}\rangle \left[ \prod_i a_i^{x_i} \right]_p , $$

using $O(m \log n)$ gates, $O(m \log n)$ depth and $O(\log n)$ ancilla qubits.

*Proof.* First of all, we set aside the $a_i$ which are zero (modulo $p$). If one of the corresponding bits $x_i$ is 1, then the result is 0. The remainder of this proof considers for simplicity that all the $a_i$ are nonzero.

We choose a generator $g$ of $\mathbb{Z}_p^*$ and precompute the discrete logarithms of the $a_i$ modulo $p$. Let $\alpha_i \le p - 1$ be such that: $a_i \equiv g^{\alpha_i} \mod p$. Then we have:

$$ \prod_i a_i^{x_i} \equiv g^{\sum_{i=0}^{m-1} x_i \alpha_i} \mod p. \qquad (28) $$
We first compute $\sum_{i=0}^{m-1} x_i \alpha_i$, which is smaller than $m(p-1) = O(m^2n)$. Then, we use a $O(\log n)$-bit exponentiation circuit modulo $p$: we precompute the $g^2$ mod $p$, we read off the $O(\log n)$ bits of $\sum_{i=0}^{m-1} x_i \alpha_i$, and perform $O(\log n)$ modular multiplications in gate count: $O(\log^3 n)$. Only $O(\log n)$ ancilla space is needed for these two operations. □

Next, we can trade depth for memory during the computation of the sum.

**Lemma 8.** There exists a quantum circuit for the multi-product modulo $p$ that uses $O(m \log n)$ gates, $O(\frac{m}{\log n})$ ancilla qubits and depth $O(\log^4 n)$.

*Proof.* We change the way we compute $\sum_{i=0}^{m-1} x_i \alpha_i$, as follows. We select a parameter $2 < k \le m$ and separate the numbers into $k$ groups. We compute the sum of each group using an addition tree. As there are $(m/k)$ numbers to add, the tree has depth $\log_2(m/k)$. We need $O(\frac{m}{k} \log n)$ ancilla qubits to write all its nodes (starting from the first numbers), and $O(\frac{m}{k} \log n)$ gates to compute all of them. The result of each smaller sum is added into an accumulator register, which contains the result of the whole sum. Since there are $k$ groups, the total depth is: $O(k \times \log(m/k) \times \log n) = O(k(\log n)^2)$ and the total gate count is: $O(m \log n)$. By selecting $k = (\log n)^2$, we achieve a space in $O(\frac{m}{\log n})$ and a depth $O((\log n)^4)$ (which becomes dominating), for the same gate count. □

We obtained better results with the following optimization, even though it increases slightly the asymptotic gate count.

**Lemma 9.** There exists a circuit for the multi-product mod $p$ using $O(m \log^2 n)$ gates, $O(m \frac{\log \log n}{\log n}) = o(m)$ ancilla qubits and depth $O(\log^3 n)$.

*Proof.* We write the binary representation of $\alpha_i: \forall i, \alpha_i = \sum_k (\alpha_i)_k 2^k$. Then:

$$ \sum_{i=0}^{m-1} x_i \alpha_i = \sum_{k} \left( \sum_{i=0}^{m-1} x_i (\alpha_i)_k \right) 2^k . \qquad (29) $$

A strategy to compute the sum in $O(\log n)$ steps follows: we initialize a $O(\log n)$-qubit accumulator. At each step, we compute $\sum_{i=0}^{m-1} (\alpha_i)_k$, shift the value by $k$ bits and add it to our accumulator.

We now focus on the computation of $\sum_{i=0}^{m-1} x_i (\alpha_i)_k$ for a fixed $k$. Since $(\alpha_i)_k$ are precomputed values, this is equivalent to computing $\sum_{i \in I} x_i$ for a fixed subset $I \subseteq \{0, \dots, m-1\}$. To do this with a minimal use of ancillas, we adopt the following strategy.

We separate the bits of $I$ (less than $m$) into groups of size $k = O(\log n)$. To each of these groups, we append an ancillary register of $O(\log \log n)$ qubits. We use a sequence of $\log n$ in-place incrementor circuits to sum the bits into this register one by one. Then, we sum these ancillary registers two by two. Each
time we sum two registers, we use an addition circuit and append two more qubits for the inevitable carries. The total ancilla space is therefore:

$$ \frac{m}{k} \log k + \frac{m}{k} \left( 1 + \frac{1}{2} + \dots \right) = \mathcal{O}\left( m \frac{\log \log n}{\log n} \right). $$

The first step (local and sequential) uses $\frac{m}{\log n} \times \log n \times \log n = \mathcal{O}(m \log n)$ gates and depth $\mathcal{O}(\log^2 n)$. The second step (global and parallel) needs depth $\mathcal{O}(\log \frac{m}{k} \times \log n) = \mathcal{O}(\log^2 n)$ as well under the same assumption, and uses $\mathcal{O}(m)$ gates.

Finally, we need to do this $\mathcal{O}(\log n)$ times. The gate count increases to $\mathcal{O}(m \log^2 n)$ and the total depth is $\mathcal{O}(\log^3 n)$, which is the same as the modular exponentiation circuit. □

# 5 Space-efficient Quantum Factoring and Discrete Logarithms

In this section, we put together the three ingredients of our algorithm: 1. the Ekerå-Håstad algorithm; 2. our new compression result; 3. the compressed multi-product circuit. This gives us an “explicit” compressed Ekerå-Håstad algorithm (Algorithm 2). We prove its correctness under heuristics (Theorem 2), first for factoring, and then we extend to short discrete logarithms (Corollary 1).

## 5.1 New Compressed Subroutine

An important ingredient in our analysis is that we do not directly compress the multi-product output to one bit. In order to rely only on Heuristic 1 (the modular multi-product is roughly a random periodic function), we truncate the multi-product to $r$ bits first, and then we take the dot-product with randomly chosen masks $\beta$. As the mask is chosen before running the quantum algorithm, this only modifies a few gates in the specification of the circuit, and this has negligible impact on its computational resources$^4$.

The analysis of the Ekerå-Håstad algorithm [15] relies on the probability to measure a “good” output $y$. We show that this probability is only halved, and that half of the measurement results are 0 (which is discarded). This also tells that the size of $Y$ at Step 12 is essentially the same as before, and that the post-processing routine runs unchanged. The proof of Theorem 3 (deferred to Section B) relies on concentration inequalities, leveraging the fact that we have many possible choices of $\beta$, and so the deviation of a probability of measurement from its average can be bounded.

**Theorem 3.** Under Heuristic 1, with probability 0.99 over the choice of $N$, at Step 8 in Algorithm 2:

* the probability to measure 0 is at most $\frac{1}{2} + 0.01$ plus half of the probability to measure 0 in the uncompressed Ekerå-Håstad subroutine

* the probability to measure a “good” $y$ is at least $\frac{1}{16} - 0.01$

<footnote>$^4$ In fact, we conjecture that it should be possible to get rid entirely of this mask $\beta$.</footnote>
**Algorithm 2** New space-efficient quantum factoring for RSA integers. In the DL case, *A* is an input of the algorithm and it stops when *D* is output.

**Input:** *N*

**Output:** *P*, *Q* st. *P* × *Q* = *N*

**Parameters:** $n = \lceil \log_2 N \rceil$, $s, \mu, m = \frac{n}{2} + 2 \lceil \frac{n}{2s} \rceil$, $r = 22$

▷ Classical steps

1. Select a random number $G < N$ invertible modulo $N$

2. Let $A = G^{(N-1)/2 - 2^{n/2-1}}$

3. Precompute $G^{2^i}$ for $0 \le i < \frac{n}{2} + \lceil \frac{n}{2s} \rceil$ and $A^{2^j}$ for $0 \le j < \lceil \frac{n}{2s} \rceil$

4. Setup Algorithm 1 so that its probability of error $p$ satisfies: $8\sqrt{4\mu\sqrt{p}} < 0.08$

5. Precompute the cofactors required by Algorithm 1 and define the multi-product circuit for $A_0, \dots, A_{m-1} = G^{2^0}, \dots, G^{2(\frac{n}{2} + \lceil \frac{n}{2s} \rceil - 1)}, A^{-2^0}, \dots, A^{-2(\lceil \frac{n}{2s} \rceil - 1)}$

▷ Quantum subroutines

$Y \leftarrow \emptyset$

6. **while** $|Y| < \mu$ **do**

7. Select a random non-zero mask $\beta$ of $r$ bits

8. Run the “compressed Ekerå-Håstad” sub-routine with the following compression of the multi-product circuit:

$$ (x_0, \dots, x_{m-1}) \mapsto \beta \cdot \left( \prod A_i^{x_i} \mod N \mod 2^r \right) $$

9. Measure $y$

10. **If** $y \neq 0$, $Y \leftarrow Y \cup \{y\}$

11. **end while**

▷ Classical post-processing

12. Run the Ekerå-Håstad post-processing routine on *Y*

13. Let *D* be the discrete logarithm of *A*. From $D = \frac{P-1}{2} + \frac{Q-1}{2} - 2^{n/2-1}$, deduce $P+Q$.

14. Deduce *P* and *Q*

15. **Return** *P*, *Q*

## 5.2 Complete Algorithm

We can now prove our result for factoring.

**Theorem 4.** Under Heuristic 1 and Heuristic 2, if the Ekerå-Håstad algorithm running with parameters $s$ and $\mu$ succeeds with probability $> 0.99$, then Algorithm 2 succeeds with probability $> 0.9$. If $n$ is the bit-size of the RSA modulus, each sub-routine runs with a gate count $O(n^3)$, depth in $O(n^2 \log^3 n)$ and $\frac{n}{2} + o(n)$ qubits. Using $s = O(\log n)$, the entire algorithm runs with an average gate count $O(n^3 \log n)$ and $\frac{n}{2} + O(\frac{n}{\log n})$ qubits. The classical computation is polynomial in $n$.

*Proof.* The complexity of the algorithm is immediately deduced from Theorem 2 and [10]. For the correctness, we prove it in two steps.

Consider first a version of Algorithm 2 in which we have replaced our multi-product circuit by a circuit that computes exactly $\beta \cdot ((G^x A^{-y} \mod N) \mod 2^r)$,
where $\beta$ is the r-bit mask that has been selected uniformly at random. Then by Theorem 3, under Heuristic 1, this version offers the guarantee of measuring the same number of “good” outputs if we eliminate the “0” outputs, which appear in proportion 1/2.

For a given $\mu$, the probability to measure new zeroes (not those which would have already been output by the uncompressed subroutine) is 1/2. Thus, we need on average $2\mu$ iterations of the compressed subroutine to obtain $\mu$ non-zero measurement outputs. Furthermore, the probability that more than $4\mu$ runs are necessary is small. Indeed, assume that we make $4\mu$ runs, they will contain $2\mu$ non-zero results on average. By a Chernoff bound, the probability that they contain less than $\mu$ non-zero results is bounded by $\exp(-(1/2)^2 2\mu/2)$. Starting with $\mu = 20$, this is smaller than 0.007, so the probability of success is greater than 0.993. We use this bound to set the success probability of our circuit in Step 4. The measurement results follow the distribution expected by Ekerå-Håstad, so we can run the classical post-processing unchanged and factor $N$.

In a second step, we replace the computation of $(G^x A^{-y} \mod N)$ mod $2^r$ by our circuit, which introduces errors. Under Heuristic 2, we can make the probability of error arbitrarily low. In fact, we can ensure the constraint $8\sqrt{4\mu}\sqrt{p} < 0.08$ where $\mu$ is as large as $O(\log n)$, as this requires $O(\log \log n)$ additional space only in Heuristic 3.

We can then use Lemma 3. We have established that the “ideal” version of the algorithm succeeds with probability $\ge 0.99 - 0.007$. As there are $4\mu$ measurements at most, the new probability of success is lower bounded by: $0.99 - 0.007 - 8\sqrt{4\mu}\sqrt{p} \ge 0.99 - 0.007 - 0.08 \ge 0.9$. $\square$

*Case of General Integers.* In the case of general integers, our method can reduce the space to $n + o(n)$ as follows$^5$.

First, one uses the classical reduction from [11], which factors an integer $N$ completely given the order of a random element $G$ in $Z_N^*$. To solve this order-finding problem, one uses Seifert's variant of Shor's algorithm [33] combined with the analysis of App. A in [12]. At this point, the input register length is of $m + \lfloor m/s \rfloor$ where $m \le n$ is an upper bound on the bit-length of the order of $G$, and about $s$ runs are required to find the entire order.

## 5.3 Application to Discrete Logarithms

Although the factorization of RSA moduli is the most prominent application, our method gives a stronger advantage for computing Discrete Logarithms with short exponents in safe-prime groups.

When $P$ is a prime and $Q = (P - 1)/2$ is also prime, a safe-prime group is a (cyclic) subgroup of $Z_P^*$ of order $Q$, where the computational Diffie-Hellman problem is expected to be hard. Usually $\log_2 P$ is large, but the exponent can be made quite small. Indeed, subexponential classical algorithms for discrete logarithms depend on the entire group size; when the discrete logarithm is of

<footnote>$^5$ The details that follow here were explained to us by Martin Ekerå.</footnote>
size $d \ll \log_2 P$, the best classical algorithms run in $O(2^{d/2})$. As an example, for $\log_2 P = 2048$, $d = 224$ is sufficient to offer 112 bits of security.

Since the exponentiation in $Z_p^*$ also reduces to computing a modular multi-product, the proof of Theorem 2 carries through.

**Corollary 1.** Consider a Discrete Logarithm instance in $Z_p^*$, of bit-size $d$. Under Heuristic 1 and Heuristic 2, if the Ekerå-Håstad algorithm running with parameters $s$ and $\mu$ succeeds with probability > 0.99, then Algorithm 2 succeeds with probability > 0.9. Each sub-routine runs with a gate count $\tilde{O}(d^2 \log P)$, and $d+o(d) + O(\log P)$ qubits. The classical computation time is polynomial.

As a comparison, solving this short discrete logarithm problem would have previously required to compute $d$ multiplications in $Z_p^*$. The total gate count would be $O(d \log^2 P)$ using schoolbook multiplications or $O((d(\log P))^{1.29})$ using the circuits of [24].

# 6 Applications

In this section, we estimate the resources required by our algorithm for factoring RSA moduli and computing short discrete logarithms. In both cases, we reuse parameters for the Ekerå-Håstad subroutine (input register size and number of measurements) given by Ekerå in [10].

Note that the optimizations made in [10] are stronger than in [15], as Ekerå simulates a discretized histogram of measurement outputs, and does not only use the “good” ones. Formally, our compression theorem (Theorem 3) does not prove that the entire histogram is preserved and rescaled after compression, as we only considered the set of “good” outputs. However, we could generalize this theorem using multiple sets of outputs; if necessary, we could increase $r$ slightly, which has a minor consequence on the number of qubits. As a consequence we believe that this approach is sound.

Since Algorithm 1 is a classical algorithm, we first implemented and tested it with the RSA-2048 instance of the RSA factoring challenge. Our implementation is quite slow, and computes a random output in about one second on a desktop computer. This allowed us to verify the correctness of our algorithm and of Heuristic 3 for failure probabilities around $2^{-6}$.

## 6.1 Quantum Implementation of Modular Multi-Product

We used the Qiskit library [29] to implement the computation of $[A_X]_p$ for a prime $p$ in the RNS (the most costly component of Algorithm 1), following the blueprint of Lemma 9. Our implementation is optimized for RSA-2048 and might certainly be improved by considering other trade-offs between gate count, depth and qubits.

Given a list $a_0 = [A_0]_p, \dots, a_{m-1} = [A_{m-1}]_p$ of precomputed values, we construct the circuit that on input $(x_0, \dots, x_{m-1})$ returns the multi-product $[\prod a_i^{x_i}]_p$. We first precompute the discrete logarithms of the $a_i$ relative to a
generator $g$ of $Z_p^*$, in order to reduce to a multi-sum $\sum_i (x_i \alpha_i)$. After computing the multi-sum, we compute an exponentiation of $g$ by $\sum_i (x_i \alpha_i)$ modulo $p$.

The multi-sum is implemented with the strategy of Lemma 9, which reduces it to several multi-bit sums which compute the Hamming weight of a bit-string. The inputs are divided in groups of 15 bits, and a 4-bit incrementor circuit is used to update each group. The results are summed using a tree of adders.

Since $p$ is typically of 19 to 24 bits, the modular exponentiation that follows can be implemented using windowed arithmetic. We cut the exponent $x$ into three parts: $x = x_1 + 2^7 x_2 + 2^{14} x_3$, and we compute $[g^{x_1}]_p, [(g^{2^7})^{x_2}]_p$ and $[(g^{2^{14}})^{x_3}]_p$ using the table lookup circuit of [1]. Afterwards, we do non-modular multiplications and Euclidean divisions to reduce modulo $p$.

While the exact costs of the modular multi-product depend on the $a_i$ and on $p$, we observed that the variations are quite small at these scales; the total counts reported are averaged over 20 to 30 random instances.

*Number of Qubits.* The number of qubits required by the multi-sum circuit varies depending on the $\alpha_i$, since the multi-bit sums span only the bits of the $d_i$ that are “1” at specific positions. When $m \ge 1000$ (RSA instances) the probability that an $m$-bit string has Hamming weight bigger than $1.3m/2$ is lower than $\exp(-0.3^2/(2+0.3) \times m/2)$ using a multiplicative Chernoff bound, which is smaller than $\exp(-19.6)$. This ensures that this case never happens for all multi-bit sums used throughout Algorithm 1. Therefore, when estimating the number of qubits (which needs to be an upper bound over all RNS primes), we consider that the multi-bit sums will have $0.65m$ inputs at most. When $m < 500$ (discrete logarithm instances), we simply considered that the multi-bit-sums would have $m$ inputs at most.

*Full Quantum Circuit.* The quantum circuit follows the layout given in Algorithm 1. We need to keep track of the “accumulator” registers $qM (u+\lfloor\log_2 qM\rfloor+1$ qubits), QN $(u'+r$ qubits) and of the Result register ($r$ qubits). For each prime of the RNS, we will compute a modular multi-product, update the accumulators (with negligible cost), and then uncompute it. When we have computed Result, we uncompute $qM$ and QN. This means that the number of multi-product circuits is 4 times the number of primes in the RNS.

## 6.2 Parametrizations and Gate Counts

In Section C we give the parameters of Algorithm 2 for several RSA and DL instances, and corresponding resource estimates. We detail here the cases of RSA-2048 and a 224-bit DL in a safe-prime group of 2048 bits.

For RSA-2048, following Table 3 in [10], $s = 17$ and $\mu = 20$ measurement results are enough to ensure 0.99 success probability for the post-processing. This yields $m = 1146$. There are 72 199 primes in the RNS, allowing to represent numbers of $1146 \times 2048$ bits. A probability of failure $p = 2^{-20}$ for the circuit satisfies the condition $8\sqrt{4\mu}\sqrt{p} < 0.08$, which ensures a total success probability of at least 0.9 for Algorithm 2. To achieve $p = 2^{-20}$, we will use $\nu = 20$ additional
bits for Heuristic 3 (truncation of the sum), the remaining sources of errors being
negligible. From the constraints in Section 4, we obtain that the register for $q_M$
will be of size 115 bits, the one for $Q_N$ of size 63 bits, and the result has 22
qubits. Thus the circuit contains at least $115 + 63 + 22 = 200$ ancillas.

Our implementation of multi-product contains in addition 384 ancillas, and takes $2^{17.4}$ Toffoli gates. The full circuit contains 1730 qubits including 584 workspace ancillas, and $2^{35.54}$ Toffoli gates. We need 40 measurements on average, i.e., a total of $2^{40.87}$ Toffolis (almost a thousand times bigger than [19]).

For the 224-bit DL instance, following Table 2 in [10], an input register of 224 bits is enough, and we need 10 measurements. There are 16 526 primes in the RNS, as we need to represent numbers of 224 × 2048 bits only. The sizes of $q_M$ and $Q_N$ are marginally smaller. Our multi-product circuit requires 206 ancillas, and the full circuit has 684 qubits. The Toffoli count is also significantly smaller, at $2^{31.58}$, for a total $2^{35.9}$ when we multiply it by the 20 average measurement results.

*DL if the Group Order is Known.* If the order of the subgroup for the short DL instance is known, one can use Shor's algorithm directly, as suggested in [19]. Our compression technique is directly applicable to Shor's algorithm; only two measurement results are required on average instead of one, so we only need to run the circuit twice. The input register size is increased to *2d*, but the total number of gates decreases significantly.

# 7 Conclusion

In this paper, we reduced the number of logical qubits for quantum factoring and discrete logarithms in $\mathbb{Z}_N^*$, at $d+o(d)+o(\log N)$ when $d$ is the bit-size of the DL. This allows to factor $n$-bit RSA moduli with $\frac{n}{2}+o(n)$ qubits. In particular, for RSA-2048, we could propose a circuit with 1730 qubits. As a comparison, a state-of-the-art quantum circuit for computing elliptic curve discrete logarithms (ECDLP) given in [21] requires 2124 qubits for a 256-bit instance, though the gate count is much smaller.

This result follows from a purely classical algorithm, based on the RNS, which realizes the compression initially proposed by May and Schlieper [25] for the Ekerå-Håstad algorithm [15,10]. The correctness of this algorithm depends on two heuristics. The first one, which is related to the distribution of the outputs of an exponentiation modulo $N$, could certainly be simplified, and we leave this as an interesting open question. In fact, it was suggested by a reviewer that one could make the value of $G$ vary and average over it, allowing to retrieve a family of functions instead of a single one. This could bring us back closer to the compression result of May and Schlieper.

For the case of factoring, our arithmetic circuit contains $O(n^3)$ gates. While the constant factor in the $O$ is small according to our estimates, it remains higher than state-of-the-art benchmarks for quantum factoring [19]. The difference for a single run is of a factor $2^5$, and multiple runs are required in our
case. However, we believe that our initial gate count estimates could be followed
by more advanced optimizations, similarly to the improvements undergone by
Shor's algorithm in the last decades.

Finally, another prominent target of Shor's algorithm is the discrete loga-
rithm problem on elliptic curves. Unfortunately, the approach that we used in
this paper uses specific tools of integer arithmetic (the RNS, Chinese remain-
dering) which simply do not exist in elliptic curve groups. Whether there is
another way to compress their workspace register (while keeping the circuit size
polynomial in n) is an interesting open question.

**Acknowledgments.** The authors would like to express their gratitude to Martin Ekerå for many insightful comments and remarks, which improved significantly the first version of this paper. We thank Paul Kirchner and anonymous reviewers for helpful comments.

We also thank Daniel J. Bernstein for pointing us to the references [5,6]
for the Explicit CRT. A.S. wants to thank Xavier Bonnetain for discussions on
Shor's algorithm. This work has been supported by the French Agence Nationale
de la Recherche through the France 2030 program under grant agreement No.
ANR-22-PETQ-0008 PQ-TLS.

References

1. Babbush, R., Gidney, C., Berry, D.W., Wiebe, N., McClean, J., Paler, A., Fowler, A., Neven, H.: Encoding electronic spectra in quantum circuits with linear t complexity. Physical Review X 8(4), 041015 (2018). https://doi.org/10.1103/PhysRevX.8.041015

2. Beame, P., Cook, S.A., Hoover, H.J.: Log depth circuits for division and related problems. SIAM J. Comput. 15(4), 994–1003 (1986). https://doi.org/10.1137/0215070

3. Beauregard, S.: Circuit for Shor's algorithm using $2n + 3$ qubits. arXiv preprint quant-ph/0205095 (2002)

4. Bennett, C.H.: Time/space trade-offs for reversible computation. SIAM J. Comput. 18(4), 766–776 (1989). https://doi.org/10.1137/0218053

5. Bernstein, D.J.: Multidigit modular multiplication with the explicit chinese remainder theorem. Chapter 4 in “Detecting perfect powers in essentially linear time and other studies in computational number theory”, Ph.D. dissertation, University of California at Berkeley (1995), https://cr.yp.to/papers/mmeprt-19950518-retypeset20220326.pdf

6. Bernstein, D.J., Sorenson, J.P.: Modular exponentiation via the explicit chinese remainder theorem. Math. Comput. 76(257), 443–454 (2007). https://doi.org/10.1090/S0025-5718-06-01849-7

7. Bernstein, E., Vazirani, U.V.: Quantum complexity theory. SIAM J. Comput. 26(5), 1411–1473 (1997)

8. Cleve, R., Watrous, J.: Fast parallel circuits for the quantum fourier transform. In: FOCS. pp. 526–536. IEEE Computer Society (2000). https://doi.org/10.1109/SFCS.2000.892140
9. Draper, T.G.: Addition on a quantum computer. arXiv preprint quant-ph/0008033 (2000)

10. Ekerå, M.: On post-processing in the quantum algorithm for computing short discrete logarithms. Des. Codes Cryptogr. 88(11), 2313-2335 (2020). https://doi.org/10.1007/S10623-020-00783-2

11. Ekerå, M.: On completely factoring any integer efficiently in a single run of an order-finding algorithm. Quantum Inf. Process. 20(6), 205 (2021). https://doi.org/10.1007/S11128-021-03069-1, https://doi.org/10.1007/s11128-021-03069-1

12. Ekerå, M.: Quantum algorithms for computing general discrete logarithms and orders with tradeoffs. J. Math. Cryptol. 15(1), 359-407 (2021). https://doi.org/10.1515/JMC-2020-0006, https://doi.org/10.1515/jmc-2020-0006

13. Ekerå, M.: On the success probability of the quantum algorithm for the short DLP. CoRR abs/2309.01754 (2023). https://doi.org/10.48550/ARXIV.2309.01754, https://doi.org/10.48550/arXiv.2309.01754

14. Ekerå, M., Gärtner, J.: Extending regev's factoring algorithm to compute discrete logarithms pp. 211-242 (2024)

15. Ekerå, M., Hästad, J.: Quantum algorithms for computing short discrete logarithms and factoring RSA integers. In: PQCrypto. Lecture Notes in Computer Science, vol. 10346, pp. 347-363. Springer (2017). https://doi.org/10.1007/978-3-319-59879-6\_20

16. Gidney, C.: Factoring with $n+2$ clean qubits and $n-1$ dirty qubits. arXiv preprint arXiv:1706.07884 (2017)

17. Gidney, C.: Approximate encoded permutations and piecewise quantum adders. arXiv preprint arXiv:1905.08488 (2019)

18. Gidney, C.: Windowed quantum arithmetic. arXiv preprint arXiv:1905.07682 (2019)

19. Gidney, C., Ekerå, M.: How to factor 2048 bit rsa integers in 8 hours using 20 million noisy qubits. Quantum 5, 433 (2021). https://doi.org/10.22331/q-2021-04-15-433

20. Griffiths, R.B., Niu, C.S.: Semiclassical fourier transform for quantum computation. Physical Review Letters 76(17), 3228 (1996). https://doi.org/10.1103/PhysRevLett.76.3228

21. Häner, T., Jaques, S., Naehrig, M., Roetteler, M., Soeken, M.: Improved quantum circuits for elliptic curve discrete logarithms. In: PQCrypto. Lecture Notes in Computer Science, vol. 12100, pp. 425-444. Springer (2020). https://doi.org/10.1007/978-3-030-44223-1\_23

22. Häner, T., Roetteler, M., Svore, K.M.: Factoring using $2n + 2$ qubits with toffoli based modular multiplication. arXiv preprint arXiv:1611.07995 (2016)

23. Harvey, D., Van Der Hoeven, J.: Integer multiplication in time $O(n \log n)$. Annals of Mathematics 193(2), 563-617 (2021)

24. Kahanamoku-Meyer, G.D., Yao, N.Y.: Fast quantum integer multiplication with zero ancillas (2024)

25. May, A., Schlieper, L.: Quantum period finding is compression robust. IACR Trans. Symmetric Cryptol. 2022(1), 183-211 (2022). https://doi.org/10.46586/TOSC.V2022.II.183-211

26. Montgomery, P.L., Silverman, R.D.: An FFT extension to the $p-1$ factoring algorithm. Mathematics of Computation 54(190), 839-854 (1990)

27. Nielsen, M.A., Chuang, I.: Quantum computation and quantum information (2002)

28. Pollard, J.M.: A monte carlo method for factorization. BIT Numerical Mathematics 15, 331-334 (1975). https://doi.org/10.1007/bf01933667
29. Qiskit contributors: Qiskit: An open-source framework for quantum computing (2023). https://doi.org/10.5281/zenodo.2573505

30. Ragavan, S., Vaikuntanathan, V.: Space-efficient and noise-robust quantum factoring [14925], 107–140 (2024). https://doi.org/10.1007/978-3-031-68391-6_4, https://doi.org/10.1007/978-3-031-68391-6_4

31. Regev, O.: An efficient quantum factoring algorithm. CoRR abs/2308.06572 (2023)

32. Rötteler, M., Steinwandt, R.: A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth $o(\log^2 n)$. Quantum Inf. Comput. 14(9-10), 888–900 (2014). https://doi.org/10.26421/QIC14.9-10-11

33. Seifert, J.: Using fewer qubits in shor's factorization algorithm via simultaneous diophantine approximation. In: CT-RSA. Lecture Notes in Computer Science, vol. 2020, pp. 319–327. Springer (2001). https://doi.org/10.1007/3-540-45353-9_24

34. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997). https://doi.org/10.1137/S0097539795293172

35. Simon, D.R.: On the power of quantum computation. SIAM J. Comput. 26(5), 1474–1483 (1997)

36. Takahashi, Y., Kunihiro, N.: A quantum circuit for Shor's factoring algorithm using $2n + 2$ qubits. Quantum Information & Computation 6(2), 184–192 (2006)

37. Zalka, C.: Fast versions of Shor's quantum factoring algorithm. arXiv preprint quant-ph/9806084 (1998)

38. Zalka, C.: Shor's algorithm with fewer (pure) qubits. arXiv preprint quant-ph/0601097 (2006)

# Appendix

## A Relation with Circuit Complexity

Computing the “compressed” modular exponentiation ($a^x \bmod N$) mod $2^r$ in $o(n)$ space can be done by combining several results of circuit complexity in a black-box way, although this does not seem to have been noticed before in the context of Shor’s algorithm. However, this may lead to a large polynomial, which will be useless in practice: a dedicated analysis is required to bring this polynomial down to a reasonable $O(n^3)$.

Since $a$ is a constant, modular exponentiation by $x$ can be first reduced to a “multi-product” of $n$ integers. In [2] Beame, Cook and Hoover showed how to perform a product of $n$ integers in logarithmic depth, as well as modular reduction: this was the basis of Cleve and Watrous’ log-depth algorithm for factoring, which also introduced a log-depth implementation of the Quantum Fourier Transform [8]. These techniques use the RNS.

Since the circuit for multi-product has depth $O(\log n)$, any output bit can be written as the root node in a binary tree of size $n^{O(\log n)} = \text{poly}(n)$, where the leaves are the input bits (in our case, the control bits for the exponentiation in Shor's algorithm) and each node specifies a Boolean operation. All the nodes in the tree (and a fortiori the root) can be computed in time $\text{poly}(n)$ and
using $O(\log n)$ space using a depth-first exploration. Using Bennett's time-space tradeoff [4], we can make this computation reversible, it will still run in time poly($n$) and using space $O(\log^2 n)$. This applies as well to discrete logarithms in $\mathbb{Z}_p^*$, which essentially rely on the same circuit.

In particular, since any output bit can be produced in time poly($n$), we can also produce all of them in sequence in time poly($n$). An interesting consequence is that we can use the May-Schlieper compression technique [25] as follows.

**Theorem 5.** There exists a quantum algorithm factoring RSA moduli using $\frac{n}{2} + o(n)$ qubits and poly($n$) gates.

*Proof.* We use Theorem 1, combined with [15] (see Section 3.2). We use the following hash function family:

$$ \{x \mapsto \beta \cdot x, \beta \in \{0, 1\}^n\} . $$

Before running each compressed circuit, we select $\beta$ uniformly at random, and hard-code it into the circuit. This means that we need to compute $O(\log n)$ bits of the output (at certain positions depending on $\beta$) and XOR them. Obviously this can be done in $O(\log n)$ depth, so the whole circuit takes poly($n$) gates. $\square$

While we are interested in computing multi-products, which are more relevant to quantum factoring, we note that the RNS was also used for the case of modular exponentiation by Bernstein and Sorenson [6]. These results, which concern depth optimizations on parallel machines, also rely on the explicit Chinese Remainder Theorem.

Regarding discrete logarithms on elliptic curves, one can already notice that the best depth available in the literature is $O(\log^2 n)$ [32], which leads this generic compression to a superpolynomial complexity $2^{O(\log^2 n)} = n^{O(\log n)}$. The main difference with discrete logarithm in $\mathbb{Z}_p^*$ seems to be the availability of the RNS. For this reason, achieving a polynomial-time workspace compression for the case of elliptic curves remains an open question.

## B Proof of Theorem 3

As recalled in Section 3.3, May and Schlieper [25] proved that if a quantum period-finding subroutine has the cancellation property, then compressing this subroutine with a universal hash function family only rescales the distribution of measurement outputs $y$ (when measuring the input register). In this section, we prove an alternative theorem that allows to rely only on Heuristic 1, i.e., on the randomness of the output of the modular multi-product circuit. Here $r$ will be a well-chosen constant.

**Fixed Function Analysis.** In the case of Ekerå-Håstad, let us first consider the uncompressed subroutine, where the function $f$ is defined by $f(x_1, x_2) =$
$G^{x_1} A^{-x_2} \mod N$. Like in [25], we define $w_{y,f(x)}$ as the amplitudes in the output of the subroutine $Q_f^{\text{period}}$:

$$ \sum_{y \in \{0,1\}^m} \sum_{f(x) \in \text{Im}(f)} w_{y,f(x)} |y\rangle |f(x)\rangle . \qquad (30) $$

By a change of variable $z = f(x)$ we can rewrite this state as:

$$ \sum_{y \in \{0,1\}^m} \sum_{z \in \{0,1\}^n} w_{y,z} |y\rangle |z\rangle . \qquad (31) $$

The cancellation property is satisfied:

$$ \forall y \neq 0, \quad \sum_{z \in \{0,1\}^n} w_{y,z} = 0 . \qquad (32) $$

The probability to measure a given $y$ in the non-compressed state (Equation 31) is:

$$ p_N(y) := \sum_{z \in \{0,1\}^n} |w_{y,z}|^2 . \qquad (33) $$

Here the subscript $N$ in $p_N(y)$ indicates that this quantity depends only on $N$, since the definition of the function $f$ depends only on $N$ (we assume that there is a canonical choice of $G$). So far, we have considered the actual uncompressed algorithm, whose correctness follows from the analysis of [15,10]. The amplitudes $w_{y,z}$ (where we omit the subscript $N$) are those of this algorithm.

**Randomizing the Function (Uncompressed).** We introduce now a modification in the function. We compose $f$ with a random permutation of $Z_N^*$, which is extended to $\{0,1\}^n$, and denoted as $h$. This modifies the output state into:

$$ \sum_{y \in \{0,1\}^m} \sum_{f(x) \in \text{Im}(f)} w_{y,f(x)} |y\rangle |h(f(x))\rangle = \sum_{y \in \{0,1\}^m} \sum_{z \in \{0,1\}^n} w_{y,z} |y\rangle |h(z)\rangle . \qquad (34) $$

We define as $p_{N,h}(y)$ the probability to measure $y$ in this state. Then we can notice that for any $h$, $p_{N,h}(y) = p_N(y)$.

**Compressing the Function.** We introduce now a compression of the function. We take the dot-product of the output with a mask $\beta' = \beta|0^{n-r}$ where $\beta$ is a non-zero $r$-bit mask. The compressed subroutine will now produce the output:

$$ \sum_{y \in \{0,1\}^m} \left( \sum_{z \in \{0,1\}^n} w_{y,z} |y\rangle |0\rangle + \sum_{(\beta|0^{n-r}) \cdot h(z)=1} w_{y,z} |y\rangle |1\rangle \right) . \qquad (35) $$
Again, notice that $w_{y,z}$ have a fixed definition which is from the original Ekerå-Håstad algorithm, while $h$ is a varying random permutation. The probability to obtain a given $y$ when measuring the state in Equation 35 is:

$$p'_{N,h}(y) := \frac{1}{2^r-1} \sum_{\beta \neq 0} \left( \left| \sum_{(\beta|0^{n-r}) \cdot h(z)=0} w_{y,z} \right|^2 + \left| \sum_{(\beta|0^{n-r}) \cdot h(z)=1} w_{y,z} \right|^2 \right) . \quad (36)$$

While $p'_{N,h}(y)$ depends on $N$ and $h$, we also introduce $p'_{N}(y)$, which is the probability to measure $y$ when running the compressed subroutine with $f$ only (i.e., in our algorithm).

In the following, we prove that $p'_{N,h}(y)$ is very close to $\frac{1}{2}p_N(y)$ when $h$ is chosen uniformly at random. Intuitively, the role of $h$ is to partition randomly the terms $w_{y,z}$ into the two subsets $(\beta|0^{n-r}) \cdot h(z) = 0$ or $(\beta|0^{n-r}) \cdot h(z) = 1$.

**Lemma 10.** Let $N$ be fixed, let $y \neq 0$ be fixed, and $h$ be a uniformly random permutation of $\mathbb{Z}_N^*$. For any $k > 0$:

$$\mathrm{Pr}_h \left( \left| \frac{1}{2} p_N(y) - p'_{N,h}(y) \right| \ge \frac{kp_N(y)}{\sqrt{(2^r-1)}} \right) \le \frac{1}{k^2}. \quad (37)$$

*Proof.* We first notice that, by the cancellation property:

$$\left| \sum_z w_{y,z} \right|^2 = 0 = \sum_z |w_{y,z}|^2 + \sum_{z \neq z' \in \{0,1\}^n} w_{y,z} \overline{w_{y,z'}} . \quad (38)$$

Let $h_\beta := (\beta|0^{n-r}) \cdot h$ for any $\beta \neq 0$. By developing $p'_{N,h}(y)$ we have:

$$\begin{align*}
p'_{N,h}(y) &= \frac{1}{2^r-1} \sum_{\beta \neq 0} \left( \sum_{z \in \{0,1\}^n} |w_{y,z}|^2 + \sum_{\substack{z \neq z' \\ z,z' \in h_\beta^{-1}(0)}} w_{y,z} \overline{w_{y,z'}} + \sum_{\substack{z \neq z' \\ z,z' \in h_\beta^{-1}(1)}} w_{y,z} \overline{w_{y,z'}} \right) \\
&= \frac{1}{2^r-1} \sum_{\beta \neq 0} \left( \frac{1}{2} p(y) + \frac{1}{2} \sum_{z \in \{0,1\}^n} |w_{y,z}|^2 \right. \\
&\qquad \left. + \sum_{\substack{z \neq z' \\ z,z' \in h_\beta^{-1}(0)}} w_{y,z} \overline{w_{y,z'}} + \sum_{\substack{z \neq z' \\ z,z' \in h_\beta^{-1}(1)}} w_{y,z} \overline{w_{y,z'}} \right) \\
&= \frac{1}{2} p_N(y) + \frac{1}{2(2^r-1)} \sum_{\beta \neq 0} \left( \sum_{\substack{z \neq z' \\ z,z' \in h_\beta^{-1}(0)}} w_{y,z} \overline{w_{y,z'}} + \sum_{\substack{z \neq z' \\ z,z' \in h_\beta^{-1}(1)}} w_{y,z} \overline{w_{y,z'}} \right. \\
&\qquad \left. - \sum_{\substack{z \in h_\beta^{-1}(0) \\ z' \in h_\beta^{-1}(1)}} w_{y,z} \overline{w_{y,z'}} - \sum_{\substack{z \in h_\beta^{-1}(1) \\ z' \in h_\beta^{-1}(0)}} w_{y,z} \overline{w_{y,z'}} \right) .
\end{align*}$$
We will now introduce the following random variables ($y$ and $N$ being fixed, the randomness here is the choice of $h$): $X_{\beta,z} = h_{\beta}(z)$. Observe that for any pair $z, z'$ with $z \neq z'$: $(-1)^{X_{\beta,z}+X_{\beta,z'}}$ takes the value 1 if $z$ and $z'$ have the same image by $h_{\beta}$ and -1 otherwise. This allows us to rewrite nicely the expression of $p'_{N,h}$:

$$p'_{N,h}(y) = \frac{1}{2} p_N(y) + \frac{1}{2(2^r - 1)} \sum_{\substack{\beta \neq 0 \\ z, z' \in \{0,1\}^n \\ z \neq z'}} \left( \sum_{\substack{z, z' \in \{0,1\}^n \\ z \neq z'}} (-1)^{X_{\beta,z} + X_{\beta,z'}} w_{y,z} \overline{w_{y,z'}} \right) . \quad (39)$$

Define $V_y := p'_{N,h}(y) - \frac{1}{2}p_N(y)$. In the proof of Theorem 7 in [25], this additional term would be 0. This is not the case here; however we will still manage to bound it. First of all, let us rewrite $V_y$ as a sum of real terms, by putting together the pairs $z, z'$ and $z', z$: we will now have a sum over unordered pairs of $\{0, 1\}^n$:

$$V_y = \frac{1}{(2^r - 1)} \sum_{\substack{\beta \neq 0 \\ \text{unordered pairs}}} \left( \sum_{z, z' \in \{0,1\}^n} (-1)^{X_{\beta,z} + X_{\beta,z'}} \mathrm{Re}(w_{y,z} \overline{w_{y,z'}}) \right) . \quad (40)$$

Let $Y_{\beta,z,z'} = (-1)^{X_{\beta,z}+X_{\beta,z'}}$. We have the following properties:

1. For any $(\beta, z, z')$, $\mathbb{E}_h [Y_{\beta,z,z'}] = 0$

2. For any $(\beta_1, z_1, z'_1) \neq (\beta_2, z_2, z'_2)$, $Y_{\beta_1,z_1,z'_1}$ and $Y_{\beta_2,z_2,z'_2}$ are independent

The first one is easy to prove. The second is more technical, as we have to consider different cases. First, if $\beta_1 \neq \beta_2$, then $h_{\beta_1}$ and $h_{\beta_2}$ are independent random functions, so the random variables $Y_{\beta_1,z_1,z'_1}$ and $Y_{\beta_2,z_2,z'_2}$ become independent as well. Second, even if $\beta_1 = \beta_2$, if the pairs are disjoint, then the variables $X_{\beta_1,z_1}, X_{\beta_1,z'_1}, X_{\beta_2,z_2}, X_{\beta_2,z'_2}$ are all pairwise independent, which gives the property. The remaining case is when $\beta_1 = \beta_2$ and the pairs share an element: w.l.o.g., we can write the variables as: $(-1)^{X_{\beta,z_1}+X_{\beta,z_2}}$ and $(-1)^{X_{\beta,z_2}+X_{\beta,z_3}}$. Then, the probability to obtain any pair $\{-1, 1\}$ is still $\frac{1}{4}$.

In particular, even in the latter case, $\mathbb{E}_h [Y_{\beta_1,z_1,z_2} Y_{\beta_2,z_2,z_3}] = \mathbb{E}_h [Y_{\beta_1,z_1,z_3}] = 0$.

Thanks to this pairwise independence of the variables in the sum, we can now compute the variance of $V_y$:

$$\begin{align*}
\mathrm{Var}_h(V_y) &= \sum_{\beta,z,z'} \mathrm{Var}_h \left( \frac{1}{(2^{r-1})} Y_{\beta,z,z'} \mathrm{Re}(w_{y,z} \overline{w_{y,z'}}) \right) \\
&= \frac{1}{(2^{r-1})^2} \sum_{\beta,z,z'} (\mathrm{Re}(w_{y,z} \overline{w_{y,z'}}))^2 \\
&\le \frac{1}{(2^{r-1})} \sum_{\substack{z,z' \in \{0,1\}^n \\ \text{unordered pairs}}} |w_{y,z} \overline{w_{y,z'}}|^2 \\
&\le \frac{1}{(2^{r-1})} \sum_{z,z' \in \{0,1\}^n} |w_{y,z} \overline{w_{y,z'}}|^2 \le \frac{p(y)^2}{(2^{r-1})} .
\end{align*}$$
We can apply Chebyshev's inequality:

$$ \forall k > 0, \mathrm{Pr}_h \left( |V_y| \ge \frac{p_N(y)k}{\sqrt{(2^r - 1)}} \right) \le \frac{1}{k^2}. \quad (41) $$

This finishes the proof of the lemma. □

This inequality indicates that, at fixed $N$, when running the algorithm with $h \circ f$ instead of $f$, we can expect the compression to work: the probability to measure a fixed $y$ will be close to half of the probability to measure it in the uncompressed algorithm. Our next result extends this to any set $\mathcal{Y}$ of non-zero outputs.

**Lemma 11.** Fix $N$. Consider any non-empty set $\mathcal{Y} \subseteq \{0, 1\}^m \setminus \{(0, 0, \dots, 0)\}$, and $h$ be a uniformly random permutation of $\mathbb{Z}_N^*$. For any $k > 0$:

$$ \mathrm{Pr}_h \left( \left| \frac{1}{2} p_N(\mathcal{Y}) - p'_{N,h}(\mathcal{Y}) \right| \ge \frac{kp_N(\mathcal{Y})}{\sqrt{(2^r - 1)}} \right) \le \frac{1}{k^2}. \quad (42) $$

*Proof.* Since the probability to measure $\mathcal{Y}$ can be obtained by: $p_N(\mathcal{Y}) = \sum_{y \in \mathcal{Y}} p_N(y)$ and $p'_{N,h}(\mathcal{Y}) = \sum_{y \in \mathcal{Y}} p'_{N,h}(y)$, the proof of Lemma 10 can be modified by replacing the terms $w_{y,z} \overline{w}_{y,z'}$ by their sums over $\mathcal{Y}$. In particular, we define:

$$ V_{\mathcal{Y}} := \sum_{y \in \mathcal{Y}} \left( p'_{N,h}(y) - \frac{1}{2} p_N(y) \right). \quad (43) $$

And we have:

$$ \begin{align*} V_{\mathcal{Y}} &= \frac{1}{2^r - 1} \sum_{\substack{\beta \neq 0 \\ z, z' \in \{0,1\}^n \\ \text{unordered pairs}}} \sum_{\text{unordered pairs}} Y_{\beta, z, z'} \left( \sum_{y \in \mathcal{Y}} \mathrm{Re}(w_{y,z} \overline{w_{y,z'}}) \right) \\ &\implies \mathrm{Var}_h(V_{\mathcal{Y}}) = \frac{1}{2^r - 1} \sum_{\substack{z, z' \in \{0,1\}^n \\ \text{unordered pairs}}} \left( \sum_{y \in \mathcal{Y}} \mathrm{Re}(w_{y,z} \overline{w_{y,z'}}) \right)^2 \\ &\le \frac{1}{2^r - 1} \sum_{\substack{z, z' \in \{0,1\}^n \\ \text{unordered pairs}}} \left( \sum_{y \in \mathcal{Y}} |w_{y,z}| |w_{y,z'}| \right)^2. \end{align*} $$

In order to bound this, we use the Cauchy-Schwarz inequality, leading to:

$$ \begin{align*} \mathrm{Var}_h(V_{\mathcal{Y}}) &\le \frac{1}{2^r - 1} \sum_{\substack{z, z' \in \{0,1\}^n \\ \text{unordered pairs}}} \left( \sum_{y \in \mathcal{Y}} |w_{y,z}|^2 \right) \left( \sum_{y \in \mathcal{Y}} |w_{y,z'}|^2 \right) \\ &\le \frac{1}{2^r - 1} \left( \sum_z \sum_{y \in \mathcal{Y}} |w_{y,z}|^2 \right)^2 = \frac{p_N(\mathcal{Y})^2}{2^r - 1}. \end{align*} $$
This finishes the proof of the lemma.

□

As a corollary, by taking $\mathcal{Y}$ to contain all $y$ except 0, we can see that the probability to measure 0 will be close to $\frac{1}{2}$.

**Proving the Theorem.** Following the analysis of the uncompressed Ekerå-Håstad subroutine [15], one can define a set of “good” outputs $\mathcal{Y}$ and the probability to measure a “good” $y$ is greater than $2^{-3}$. The definition of this set depends only on the discrete logarithm, not on $N$ and $f$.

Our goal is essentially to show that the compressed version also measures good outputs, and that we need only twice as many measurements on average.

**Lemma 12 (From [15]).** Fix $N$. Let $\mathcal{Y}$ be the set of “good” outputs and $p_N(y)$ be defined as above. We have:

$$p_N(\mathcal{Y}) := \sum_{y \in \mathcal{Y}} p_N(y) \ge 2^{-3}.$$

Furthermore, we measure 0 with negligible probability.

**Theorem 6.** Let $r = 22$. Under Heuristic 1, with total probability 0.99 over the choice of $N$, when running our compressed Ekerå-Håstad subroutine:

* we measure 0 with probability at most $\frac{1}{2} + 0.01$

* we measure a “good” $y$ with probability at least $\frac{1}{16} - 0.01$

*Proof.* Let $\mathcal{Y}$ be the set of “good” outputs (which is fixed if the DL is fixed).

Fix $N$. We do a union bound on the result of Lemma 11, considering both $\mathcal{Y}$ and the set of all nonzero outputs. When $h$ is chosen at random, with probability at least $1 - 2/k^2$ over $h$, the following holds:

$$\left\{ \begin{array}{l} \left| \frac{1}{2} p_N(\mathcal{Y}) - p'_{N,h}(\mathcal{Y}) \right| \le \frac{k}{\sqrt{2^r - 1}} \\ \left| p'_{N,h}(0) - \frac{1}{2}(1 + p_N(0)) \right| \le \frac{k}{\sqrt{2^r - 1}} \end{array} \right. \implies \begin{array}{l} p'_{N,h}(\mathcal{Y}) \ge \frac{1}{2} p_N(\mathcal{Y}) - \frac{k}{\sqrt{2^r - 1}} \\ p_{N,h}(0) \le \frac{1}{2}(1 + p_N(0)) + \frac{k}{\sqrt{2^r - 1}} \end{array} \quad (44)$$

We choose $k = 2^4$ so that $1 - 2/k^2 \ge 0.99$. By choosing $r = 22$ we obtain that $2^4/\sqrt{2^r - 1} \le 0.01$. This proves that:

$$\Pr_{N,h} \left( \left\{ \begin{array}{l} p'_{N,h}(\mathcal{Y}) \ge \frac{1}{16} - 0.01 \\ p'_{N,h}(0) \le \frac{1}{2} + 0.01 \end{array} \right\} \ge 0.99 . \right) \quad (45)$$

So far we have studied the behavior of the compressed algorithm running with $h \circ f$, using the behavior of the uncompressed algorithm running with $f$ (which was supposed to work). The last step is to relate this to the compressed algorithm running with $f$. Here, we will use Heuristic 1.

Under Heuristic 1, when $N$ is chosen at random, the function $f$ is a random periodic function. So the two situations are statistically equivalent:
* Selecting $N$ at random, $h$ at random and running the compressed subroutine with $f$;

* Selecting $N$ at random, $h$ at random and running the compressed subroutine with $h \circ f$.

In particular, the distributions of $(p'_{N,h}(\mathcal{Y}), p'_{N,h}(0))$ and $(p'_{N}(\mathcal{Y}), p'_{N}(0))$ when both $h$ and $N$ are random are identical, and:

$$ \Pr_N \left( \left\{ \begin{array}{l} p'_{N}(\mathcal{Y}) \geq \frac{1}{16} - 0.01 \\ p'_{N}(0) \leq \frac{1}{2} + 0.01 \end{array} \right\} = \Pr_{N,h} \left( \left\{ \begin{array}{l} p'_{N,h}(\mathcal{Y}) \geq \frac{1}{16} - 0.01 \\ p'_{N,h}(0) \leq \frac{1}{2} + 0.01 \end{array} \right\} \geq 0.99 . \right) $$

□

The enhanced analysis in [10], which we reuse for our benchmarks, considers a more complicated situation in which the possible measurement results $y$ are not only “good” or “not good”. However, it is possible to classify them into a number of groups $\mathcal{Y}_i$, and estimate the success of the algorithm based on the probability to fall into one of these groups. In particular, a generalized version of Theorem 3 can show that if the number of groups is small enough, the probability to fall into each of them is close to half of the previous one.

While this does not prove rigorously that the distribution follows exactly the one simulated in [10], discretizing the histogram of the distribution is already what Ekerå does for simulating the output. Therefore, we believe that this simplification is sound.
# C Parameters and Gate Counts

## C.1 Application to RSA Factorization

The parameters of our algorithm and the corresponding costs are given in Table 2 and Table 3. Recall that:

* $s = O(\log n)$ is the parameter for Ekerå-Håstad

* $r = 22$ is the size of the result that the circuit computes

* $m$ is the bit-size of the input register for the multi-product

* $\nu$ is the number of bits in the truncation of the sum (Heuristic 3), so that the probability of success is $\ge 1 - 2^{-\nu}$

* $u$ is the precision of the fixed-point approximation of $\frac{1}{p}$ in the computation of $q_M$

* $u'$ is the expected number of bits for carry propagation in the computation of $Q_N$

* $d$ is the bit-size of the discrete logarithm (for DL instances)

## C.2 Application to Discrete Logarithms

The parameters and counts for Discrete Logarithms are given in Table 4 and Table 5.
<table><caption>**Table 2.** Parameters for Algorithm 1, for different RSA moduli, for a probability of success > 0.9. The number of measurements for the Ekerå-Håstad algorithm is taken from Table 3 in [10], and then multiplied by 2 (“us”) for the average number of measurements in Algorithm 2.</caption><thead><tr><th>RSA bit-size</th><th>2048</th><th>3072</th><th>4096</th><th>6144</th><th>8192</th></tr></thead><tbody><tr><td>s, l = ⌊n/2s⌋</td><td>17, 61</td><td>21, 74</td><td>24, 86</td><td>31, 100</td><td>34, 121</td></tr><tr><td>m = n/2 + 2l</td><td>1146</td><td>1684</td><td>2220</td><td>3272</td><td>4338</td></tr><tr><td>Measurements: Ekerå, us (average)</td><td>20, 40</td><td>24, 48</td><td>27, 54</td><td>34, 68</td><td>37, 74</td></tr><tr><td>ν</td><td>20</td><td>20</td><td>21</td><td>21</td><td>21</td></tr><tr><td>Number of primes in the RNS</td><td>72 199</td><td>150 475</td><td>253 632</td><td>527 641</td><td>892 693</td></tr><tr><td>Maximal bit-size of<br>primes in the RNS</td><td>21</td><td>22</td><td>22</td><td>23</td><td>24</td></tr><tr><td>u</td><td>57</td><td>60</td><td>62</td><td>65</td><td>67</td></tr><tr><td>u'</td><td>41</td><td>42</td><td>44</td><td>45</td><td>46</td></tr><tr><td>log<sub>2</sub> q<sub>M</sub></td><td>57</td><td>60</td><td>61</td><td>64</td><td>67</td></tr><tr><td>Size of q<sub>M</sub> register</td><td>115</td><td>121</td><td>124</td><td>130</td><td>135</td></tr><tr><td>log<sub>2</sub> q<sub>M</sub> + u + 1</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>Size of Q<sub>N</sub> register = u' + r</td><td>63</td><td>64</td><td>66</td><td>67</td><td>68</td></tr><tr><td>Size of result register = r</td><td>22</td><td>22</td><td>22</td><td>22</td><td>22</td></tr></tbody></table>

<table><caption>**Table 3.** Estimated qubit count, gate counts and depth for a single modular multi-product circuit, a full circuit for Algorithm 1, and our full Algorithm 2, for RSA moduli. The latter takes into account the number of runs that must be performed in the compressed Ekerå-Håstad algorithm, on average, given in Table 2.</caption><thead><tr><th>n</th><th></th><th>Qubits (incl. ancilla)</th><th>Toffoli</th><th>CNOT</th><th>X</th><th>Depth</th></tr></thead><tbody><tr><td rowspan="3">2048</td><td>Single multi-product</td><td>1530 (384)</td><td>2<sup>17.4</sup></td><td>2<sup>16.97</sup></td><td>2<sup>11.07</sup></td><td>2<sup>15.22</sup></td></tr><tr><td>Full circuit</td><td>1730 (584)</td><td>2<sup>35.54</sup></td><td>2<sup>35.11</sup></td><td>2<sup>29.21</sup></td><td>2<sup>33.36</sup></td></tr><tr><td>Full algorithm</td><td>1730 (584)</td><td>2<sup>40.87</sup></td><td>2<sup>40.43</sup></td><td>2<sup>34.53</sup></td><td></td></tr><tr><td rowspan="3">3072</td><td>Single multi-product</td><td>2208 (524)</td><td>2<sup>17.91</sup></td><td>2<sup>17.43</sup></td><td>2<sup>11.07</sup></td><td>2<sup>15.23</sup></td></tr><tr><td>Full circuit</td><td>2415 (731)</td><td>2<sup>37.11</sup></td><td>2<sup>36.63</sup></td><td>2<sup>30.27</sup></td><td>2<sup>34.43</sup></td></tr><tr><td>Full algorithm</td><td>2415 (731)</td><td>2<sup>42.7</sup></td><td>2<sup>42.21</sup></td><td>2<sup>35.85</sup></td><td></td></tr><tr><td rowspan="3">4096</td><td>Single multi-product</td><td>2886 (666)</td><td>2<sup>18.28</sup></td><td>2<sup>17.77</sup></td><td>2<sup>11.07</sup></td><td>2<sup>15.31</sup></td></tr><tr><td>Full circuit</td><td>3096 (876)</td><td>2<sup>38.23</sup></td><td>2<sup>37.72</sup></td><td>2<sup>31.02</sup></td><td>2<sup>35.26</sup></td></tr><tr><td>Full algorithm</td><td>3096 (876)</td><td>2<sup>43.99</sup></td><td>2<sup>43.48</sup></td><td>2<sup>36.78</sup></td><td></td></tr><tr><td rowspan="3">6144</td><td>Single multi-product</td><td>4211 (939)</td><td>2<sup>18.8</sup></td><td>2<sup>18.27</sup></td><td>2<sup>11.07</sup></td><td>2<sup>15.31</sup></td></tr><tr><td>Full circuit</td><td>4430 (1158)</td><td>2<sup>39.81</sup></td><td>2<sup>39.28</sup></td><td>2<sup>32.08</sup></td><td>2<sup>36.32</sup></td></tr><tr><td>Full algorithm</td><td>4430 (1158)</td><td>2<sup>45.9</sup></td><td>2<sup>45.36</sup></td><td>2<sup>38.17</sup></td><td></td></tr><tr><td rowspan="3">8192</td><td>Single multi-product</td><td>5556 (1218)</td><td>2<sup>19.21</sup></td><td>2<sup>18.66</sup></td><td>2<sup>11.06</sup></td><td>2<sup>15.39</sup></td></tr><tr><td>Full circuit</td><td>5781 (1443)</td><td>2<sup>40.97</sup></td><td>2<sup>40.42</sup></td><td>2<sup>32.83</sup></td><td>2<sup>37.16</sup></td></tr><tr><td>Full algorithm</td><td>5781 (1443)</td><td>2<sup>47.18</sup></td><td>2<sup>46.63</sup></td><td>2<sup>39.04</sup></td><td></td></tr></tbody></table>
<table><caption>**Table 4.** Parameters for Algorithm 1, for discrete logarithms, for a probability of success > 0.9. The number of measurements for the Ekerå-Håstad algorithm is taken from Table 2 in [10], and then multiplied by 2 ("us") for the average number of measurements in Algorithm 2.</caption><thead><tr><th>[log<sub>2</sub> p], d</th><th>2048, 224</th><th>3072, 256</th><th>4096, 304</th><th>6144, 352</th><th>8192, 400</th></tr></thead><tbody><tr><td>s, ℓ = ⌊d/s⌋</td><td>7, 32</td><td>8, 32</td><td>9, 34</td><td>10, 36</td><td>11, 37</td></tr><tr><td>m = d + 2ℓ</td><td>288</td><td>320</td><td>372</td><td>424</td><td>474</td></tr><tr><td>Measurements: Ekerå, us (average)</td><td>10, 20</td><td>11, 22</td><td>12, 24</td><td>13, 26</td><td>14, 28</td></tr><tr><td>ν</td><td>19</td><td>19</td><td>19</td><td>19</td><td>20</td></tr><tr><td>Number of primes in the RNS</td><td>20 744</td><td>33 792</td><td>51 050</td><td>84 690</td><td>122 828</td></tr><tr><td>Maximal bit-size of<br>primes in the RNS</td><td>20</td><td>20</td><td>20</td><td>21</td><td>21</td></tr><tr><td>u</td><td>53</td><td>54</td><td>56</td><td>57</td><td>59</td></tr><tr><td>u'</td><td>38</td><td>39</td><td>39</td><td>40</td><td>42</td></tr><tr><td>[log<sub>2</sub> q<sub>M</sub>]</td><td>53</td><td>54</td><td>55</td><td>58</td><td>58</td></tr><tr><td>Size of q<sub>M</sub> register<br>= ⌊log<sub>2</sub> q<sub>M</sub>⌋ + u + 1</td><td>107</td><td>109</td><td>112</td><td>116</td><td>118</td></tr><tr><td>Size of Q<sub>N</sub> register = u' + r</td><td>60</td><td>61</td><td>61</td><td>62</td><td>64</td></tr><tr><td>Size of result register = r</td><td>22</td><td>22</td><td>22</td><td>22</td><td>22</td></tr></tbody></table>

<table><caption>**Table 5.** Estimated qubit count, gate counts and depth for a single modular multi-product circuit, a full circuit for Algorithm 1, and our full Algorithm 2, for Discrete Logarithm instances. The latter takes into account the number of runs that must be performed in the compressed Ekerå-Håstad algorithm, on average, given in Table 2.</caption><thead><tr><th>n (d)</th><th></th><th>Qubits (incl. ancilla)</th><th>Toffoli</th><th>CNOT</th><th>X</th><th>Depth</th></tr></thead><tbody><tr><td rowspan="3">2048 (224)</td><td>Single multi-product</td><td>495 (207)</td><td>2<sup>15.81</sup></td><td>2<sup>15.65</sup></td><td>2<sup>11.07</sup></td><td>2<sup>15.05</sup></td></tr><tr><td>Full circuit</td><td>684 (396)</td><td>2<sup>32.15</sup></td><td>2<sup>31.99</sup></td><td>2<sup>27.41</sup></td><td>2<sup>31.4</sup></td></tr><tr><td>Full algorithm</td><td>684 (396)</td><td>2<sup>36.47</sup></td><td>2<sup>36.31</sup></td><td>2<sup>31.73</sup></td><td></td></tr><tr><td rowspan="3">3072 (256)</td><td>Single multi-product</td><td>527 (207)</td><td>2<sup>15.92</sup></td><td>2<sup>15.73</sup></td><td>2<sup>11.07</sup></td><td>2<sup>15.06</sup></td></tr><tr><td>Full circuit</td><td>719 (399)</td><td>2<sup>32.96</sup></td><td>2<sup>32.78</sup></td><td>2<sup>28.11</sup></td><td>2<sup>32.11</sup></td></tr><tr><td>Full algorithm</td><td>719 (399)</td><td>2<sup>37.42</sup></td><td>2<sup>37.24</sup></td><td>2<sup>32.57</sup></td><td></td></tr><tr><td rowspan="3">4096 (304)</td><td>Single multi-product</td><td>579 (207)</td><td>2<sup>16.07</sup></td><td>2<sup>15.85</sup></td><td>2<sup>11.07</sup></td><td>2<sup>15.06</sup></td></tr><tr><td>Full circuit</td><td>774 (402)</td><td>2<sup>33.71</sup></td><td>2<sup>33.49</sup></td><td>2<sup>28.71</sup></td><td>2<sup>32.7</sup></td></tr><tr><td>Full algorithm</td><td>774 (402)</td><td>2<sup>38.3</sup></td><td>2<sup>38.07</sup></td><td>2<sup>33.29</sup></td><td></td></tr><tr><td rowspan="3">6144 (352)</td><td>Single multi-product</td><td>631 (207)</td><td>2<sup>16.21</sup></td><td>2<sup>15.96</sup></td><td>2<sup>11.08</sup></td><td>2<sup>15.06</sup></td></tr><tr><td>Full circuit</td><td>831 (407)</td><td>2<sup>34.58</sup></td><td>2<sup>34.33</sup></td><td>2<sup>29.45</sup></td><td>2<sup>33.43</sup></td></tr><tr><td>Full algorithm</td><td>831 (407)</td><td>2<sup>39.28</sup></td><td>2<sup>39.03</sup></td><td>2<sup>34.15</sup></td><td></td></tr><tr><td rowspan="3">8192 (400)</td><td>Single multi-product</td><td>681 (207)</td><td>2<sup>16.34</sup></td><td>2<sup>16.06</sup></td><td>2<sup>11.07</sup></td><td>2<sup>15.09</sup></td></tr><tr><td>Full circuit</td><td>885 (411)</td><td>2<sup>35.25</sup></td><td>2<sup>34.97</sup></td><td>2<sup>29.97</sup></td><td>2<sup>34.0</sup></td></tr><tr><td>Full algorithm</td><td>885 (411)</td><td>2<sup>40.05</sup></td><td>2<sup>39.77</sup></td><td>2<sup>34.78</sup></td><td></td></tr></tbody></table>