Élie Gouzien
email: elie.gouzien@cea.fr

Nicolas Sangouard

Factoring 2 048-bit RSA Integers in 177 Days with 13 436 Qubits and a Multimode Memory

We analyze the performance of a quantum computer architecture combining a small processor and a storage unit. By focusing on integer factorization, we show a reduction by several orders of magnitude of the number of processing qubits compared with a standard architecture using a planar grid of qubits with nearest-neighbor connectivity. This is achieved by taking advantage of a temporally and spatially multiplexed memory to store the qubit states between processing steps. Concretely, for a characteristic physical gate error rate of 10 -3 , a processor cycle time of 1 microsecond, factoring a 2 048-bit RSA integer is shown to be possible in 177 days with 3D gauge color codes assuming a threshold of 0.75 % with a processor made with 13 436 physical qubits and a memory that can store 28 million spatial modes and 45 temporal modes with 2 hours' storage time. By inserting additional error-correction steps, storage times of 1 second are shown to be sufficient at the cost of increasing the run-time by about 23 %. Shorter run-times (and storage times) are achievable by increasing the number of qubits in the processing unit. We suggest realizing such an architecture using a microwave interface between a processor made with superconducting qubits and a multiplexed memory using the principle of photon echo in solids doped with rare-earth ions.

Introduction -Superconducting qubits form building blocks of one of the most advanced platforms for realizing quantum computers [START_REF] Kjaergaard | Superconducting Qubits: Current State of Play[END_REF][START_REF] Lamata | Digital-analog quantum simulations with superconducting circuits[END_REF]. The standard architecture consists of laying superconducting qubits in a 2D grid and computing using only neighboring interactions. Recent estimations showed however that fault-tolerant realizations of various quantum algorithms with this architecture would require millions of physical qubits [START_REF] Gidney | How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits[END_REF][START_REF] Sanders | Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization[END_REF][START_REF] Lee | Even More Efficient Quantum Computations of Chemistry Through Tensor Hypercontraction[END_REF]. These performance analyses naturally raise the question of an architecture better exploiting the potential of superconducting qubits.

In developing a quantum architecture we have much to learn from classical architectures. Realizations using trapped ions for example combine processing with storage units [START_REF] Kielpinski | Architecture for a large-scale ion-trap quantum computer[END_REF]. The authors of Ref. [START_REF] Thaker | Quantum Memory Hierarchies: Efficient Designs to Match Available Parallelism in Quantum Computing[END_REF] realized that key quantum algorithms are mostly sequential meaning that we may only need a small computing block for all the qubits in the storage unit in this architecture. Ongoing experimental efforts aim at exploiting this idea to reduce the number of superconducting qubits in the standard approach to quantum computing by adding a quantum memory implemented with spins or atoms [START_REF] Xiang | Hybrid quantum circuits: Superconducting circuits interacting with other quantum systems[END_REF][START_REF] Kurizki | Quantum technologies with hybrid systems[END_REF][START_REF] Grezes | Towards a spin-ensemble quantum memory for superconducting qubits[END_REF]. A detailed analysis of the performance of this hybrid architecture is however missing.

We here report on such an analysis by considering a quantum memory that can store multiple spatial transverse and temporal modes. The memory can be thought of as a qubit register in which the address of each qubit is identified by a temporal and a spatial index. When a given qubit needs to be processed, its state is released and mapped into the processor by means of a microwave field in a temporal and spatial mode corresponding to the qubit address. When the processing is done, the qubit state is mapped back to the memory and stored until another processing operation is needed.

More precisely, we use 3D error-correction codes [START_REF] Bombín | Exact topological quantum order in D = 3 and beyond: Branyons and brane-net condensates[END_REF] in which the address of each (dressed) logical qubit is encoded into a 3D structure of physical addresses, two dimensions being encoded in space and one in time (see Figure 1). Error-correction and logical gates are applied by sequentially releasing physical qubits corresponding to different "horizontal" slices (with different temporal indexes) and by processing each slice (with the same temporal indexes) simultaneously.

We assess the performance of this architecture through a version of Shor's algorithm [START_REF] Shor | Algorithms for quantum computation: discrete logarithms and factoring[END_REF] proposed by Ekerå and Håstad [START_REF] Ekerå | Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers[END_REF]. The algorithm is a threat for widely used cryptosystems based either on the factorization [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF] or the discrete logarithm problem [START_REF] Diffie | New directions in cryptography[END_REF]16]. It can also be considered as a certification tool to check the proper functioning of an actual quantum computer as its outcome can be verified efficiently. Last but not least, the cost of its implementation has been evaluated using plausible physical assumptions for a large scale processor with a standard 2D grid of superconducting qubits (a characteristic physical gate error rate of 10 -3 , a surface code cycle time of 1 µs, and a reaction time of 10 µs): it was estimated that it should be possible to factor a 2 048-bit integer, typically used in the Rivest-Shamir-Adleman (RSA) cryptosystem, in 8 hours with 20 million qubits [START_REF] Gidney | How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits[END_REF].

By taking this estimation as a reference, we estimate the cost of implementing the same version of Shor's algorithm in terms of physical processing qubit number, . Quantum computer architecture using a processor made with a 2D grid of qubits and a memory operating as a qubit register where the address of each qubit is specified by a temporal and spatial index. Only (dressed) logical qubits are represented; additional ancillary qubits are used for measuring the operators for error correction. multimode capacity, memory storage time, and run-time. Our evaluation is given in the case where the processor is made with two (dressed) logical qubit slices. Under the assumptions used in Ref. [START_REF] Gidney | How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits[END_REF] for the gate error rate and the cycle time, we show that it should be possible to factor a 2 048-bit RSA integer in 177 days using a multimode memory with a storage time of about 2 hours and a processor including 13 436 physical qubits-a reduction by more than 3 orders of magnitude of the number of physical qubits, as compared to the standard architecture without memory [START_REF] Gidney | How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits[END_REF], at the cost of a ≈ 500 times longer run-time. By inserting additional error-correction steps, we show that the storage time can be significantly reduced at the cost of a slight increase of run-time. We also explain how shorter run-times and storage times are achievable at the cost of increasing the number of qubits in the processing unit. We propose a realization of such an architecture using a microwave interface between a processor made with superconducting qubits and a multiplexed memory using the principle of photon echo in solids doped with rare-earth ions embedded in cavities.

Principles of (a variant of ) Shor's algorithm -Consider the factorization of N = p × q, the product of two prime numbers of similar sizes, p and q. We note n the number of bits involved in the binary representation of N , that is 2 n-1 ≤ N < 2 n . While no efficient classical factorization algorithm is known, Shor's algorithm and its variants factor N with a polynomial complexity into n [START_REF] Shor | Algorithms for quantum computation: discrete logarithms and factoring[END_REF][START_REF] Ekerå | Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers[END_REF][START_REF] Shor | Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[END_REF][START_REF] Ekerå | Modifying Shor's algorithm to compute short discrete logarithms[END_REF][START_REF] Ekerå | On post-processing in the quantum algorithm for computing short discrete logarithms[END_REF][START_REF] Ekerå | Quantum algorithms for computing general discrete logarithms and orders with tradeoffs[END_REF].

The version of Shor's factorization algorithm proposed by Ekerå and Håstad [START_REF] Ekerå | Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers[END_REF] starts by randomly selecting an integer g in the multiplicative group of inte-gers modulo N , Z * N , and defining h = g (N -1)/2 . As the order of Z * N is φ(N ) = (p -1)(q -1), we have h = g (pq-p-q+1)/2 g (p+q-2)/2 ≡ g (p+q-2)/2 mod N where the last equivalence is the result of the Chinese remainder theorem. Under the assumption that the order r of g (the smallest non-negative integer such that g r ≡ 1 mod N ) satisfies r > (p + q -2)/2, computing the discrete logarithm of h modulo N , as detailed later, yields l = (p + q -2)/2. For large N , the assumption is verified with a high probability [START_REF] Ekerå | Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers[END_REF]. Using N = pq and l = (p + q -2)/2, where N and l are both known, p and q are recovered by choosing one solution of the equation N = p(2l + 2 -p), and then exploiting q = 2l + 2 -p.

The discrete logarithm is computed in three steps. First, the exponentiation (e 1 , e 2 ) → g e1 h -e2 is applied once on two quantum registers prepared in a superposition of every possible value of e 1 and e 2 , respectively. Two quantum Fourier transforms are then applied independently to the two registers before being measured. Finally, a classical postprocessing extracts the discrete logarithm l of h modulo N from the measurement results. Because the measurements are performed directly after the Fourier transform, the cost of exponentiation largely dominates the cost of Ekerå and Håstad's algorithm (see Appendix A).

Number of gates -

The modular exponentiation needed in Ekerå and Håstad's algorithm, i.e., the operation |e |1 → |e |g e mod N , with the input e and the output g e mod N encoded on n e and n bits, respectively, can be decomposed into n e multiplications, each being decomposed into 2n controlled additions of integers of typical size n and one controlled swap between two registers of size n, giving a total number of 2n e n (n e ) controlled additions (swaps between registers, respectively) (see Appendix B for details). Each modular addition is obtained with a standard adder circuit at the cost of a specific representation-the coset representation (see Appendix C)-adding m additional qubits to the register. A controlled swap operation between two qubits can be performed using two controlled NOTs (CNOTs) and one Toffoli gate. Hence, the total cost for controlled swaps operating on two registers using n + m qubits is of 2(n + m) CNOTs and n + m Toffoli gates (see Appendix B). For the controlled addition, we can use a semi-classical adder whose mean cost for integers of size n + m is of 5.5(n + m) -9 CNOTs and 2(n + m) -1 Toffoli gates (see Appendix B). Given the number of gates in controlled addition and swap operations, the number of additions and swaps in the multiplication, and the number of multiplications in the modular exponentiation, the cost of factorization can easily be estimated (see Appendix B). This cost can however be reduced using windowed arithmetic circuits [START_REF] Gidney | Windowed quantum arithmetic[END_REF]. The basic idea consists of grouping the bits of e by blocks (each includ-ing w e bits) for controlling each multiplication, hence reducing the number of these multiplications. Similarly, for each multiplication input bits are grouped (in blocks including w m bits) to reduce the number of additions composing it. As detailed in Appendix D, the cost of exponentiation is dominated in this case by 2 ne(n+m)n wewm 1qubit gates, [2 we+wm n + 12(n + m)] ne(n+m) wewm CNOTs, and 4 ne(n+m) 2 wewm Toffoli gates. We emphasize that this is a first order estimation. In the code used to compute the required resources and find optimal parameters, the complete formulae have been used [22].

Error correction -The error correction is achieved using 3D gauge color codes, a family of subsystem codes [START_REF] Bombín | Exact topological quantum order in D = 3 and beyond: Branyons and brane-net condensates[END_REF]. A first code admits a transversal implementation of CNOT and Hadamard gates while a second code accepts a transversal implementation of the non-Clifford T gate. Switching between the two codes gives a universal set of gates without the need for state distillation [START_REF] Bombín | Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes[END_REF], contrary to standard ways of operating the surface code [START_REF] Campbell | Roads towards fault-tolerant universal quantum computation[END_REF].

The two codes are based on a shared geometrical structure: a large tetrahedron constructed from elementary tetrahedrons (see Appendix E for details). A physical qubit is attributed to each elementary tetrahedron. As in any subsystem codes, the stabilized subspace is split into a tensorial product of the (bare) logical and gauge qubits (the dressed logical qubit includes the bare logical qubit and gauge qubits). A set of operators-generators of gauge operators-are measured, each being the product of (up to six) X (or Z) operators associated to qubits corresponding to tetrahedrons sharing the same edge. From these measurements, the values of stabilizers of the two codes are deduced. In the code used for implementing H and CNOT gates, the stabilizers are defined from the vertices, i.e., the product of X (or Z) operators associated to qubits corresponding to tetrahedrons sharing the same vertex. In the code used for implementing T gates, the stabilizers are defined from the vertices for X operators and from the edges for Z operators. The value of an operator represented by a vertex is classically recovered by multiplying the measurement results of combinations of specific edges ending at the given vertex. Several combinations are possible giving redundancies that can be exploited to achieve fault-tolerant error correction with only one run of measurements [START_REF] Bombín | Single-Shot Fault-Tolerant Quantum Error Correction[END_REF]. The structure of codes in which the stabilized subsystem is the tensor product of the gauge and (bare) logical subsystems guarantees that measurements of gauge operators do not reveal the value of the (bare) logical qubit (see Appendix E).

To account for the additional resource needed to implement these codes, we use an estimation of the residual error probability on one logical qubit given in [26, eq. (4)]

p logical = A exp α log p p th d β (1)
where A ≈ 0.033, α ≈ 0.516, β ≈ 0.822, p is the error probability per physical qubit, d the code distance which is related to the number of physical qubits per logical qubits (see below) and p th the fault-tolerance threshold.

While the circuit-level threshold is unknown, we choose p th = 0.75 % as a working hypothesis and give in Appendix E 4 the run-time and the resource as a function of the code threshold.

Architecture -For simplicity, the tetrahedral structure of the error correction (see Appendix E) can be included into a large cube in which physical qubits are now represented by elementary cubes (see Figure 1). The large cubes are stored into the memory and loaded by slices into the processor when they need to be processed. We size the processor such that one slice of two large cubes can be loaded simultaneously, which is convenient to perform 2-qubit gates efficiently. Each gate is immediately followed by an error-correction round on the processed qubits. This is done by reloading again each slice sequentially in the processor and by measuring the gauge generators (before recovering classically the code stabilizers), each of them using up to six 2-qubit gates, one auxiliary qubit and one measurement of this auxiliary [START_REF] Bombín | Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes[END_REF][START_REF] Devitt | Quantum error correction for beginners[END_REF]. Note that the codes of interest are 3D local and the auxiliary qubits only need to keep coherence for the time of loading and measuring two successive slices for successfully performing a stabilizer measurement. Once the syndromes are obtained and the errors are detected, the correction of these errors is delayed and merged with the next operation applied on the qubit to be corrected. Further note that all-to-all connectivity between the logical qubits is achieved if each physical address in the memory can be mapped to three physical qubits in the processor: two for the 2-qubit gates (depending on whether the physical qubit is the logical control or target qubits) and one for the error correction. For achieving a code distance d the number of physical qubits in the processor is n qubits = 2 × 2 × 3d 2 +2d-3 2 , corresponding to two logical qubit slices (see Appendix E) and including the ancillary qubits (essentially one per physical qubit) needed for stabilizer measurements. For a code distance d, we approximate the time it takes to perform one (1-qubit or 2-qubit) logical gate by 2(d -2)t c where t c is the cycle time of the 2D processor (time to load one qubit slice; to measure the stabilizers, which is longer than the gate operation; and to reload the slice into the memory) and the factor 2 comes from the fact that the gate is immediately followed by an error-correction round.

Cost evaluation -To evaluate the resources required for integer factorization, we consider the total number of gates involved in the logical circuit. The total runtime for one attempt is obtained by multiplying the gate number by the time it takes to perform one gate, while the success probability is deduced from the logical error probability [Eq. ( 1)]. Following Ref. [START_REF] Gidney | How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits[END_REF], we consider a cycle time of t c = 1 µs and a mean error per physical qubit and per gate of p = 10 -3 . Note that the mean error per gate now includes errors during reading of and writing into the memory.

The cost evaluation is finally obtained by optimizing the two window parameters w m and w e , the coset representation padding m and the code distance d in order to minimize the volume t exp × n qubits . t exp = t ps is the average time to obtain the result (several attempts might be necessary), with t the computation time per attempt and p s the success probability.

Results -The required resources to factor a n-bit RSA integer are presented in Figure 2 and discussed in Appendix F. Our estimation suggests that the factorization of a 2 048-bit integer corresponding to the most common RSA key size would be possible in about 177 days with a processor having only 13 436 qubits. Concerning the memory, we made the hypothesis of an error per cycle of p = 10 -3 , including the reading and writing error. As previously discussed, we need a memory for which each mode can be mapped to three different qubits of the processor. We estimated the maximum time between storage and readout of the same qubit to be less than 2 hours. A memory with a storage time of at least 2 hours is however not necessary as error-correction steps can be implemented periodically at the cost of increasing the run-time. Error correction of all the qubits stored in the memory is estimated to take 186 ms with a processor having 13 436 bits, meaning that the storage time simply needs to be longer than 186 ms. Applying a correction every second for example would increase the run-time by about 23 %. Note also that both the run-time and storage time can be reduced by increasing the size of the processor (see Appendix F). We also estimated that 28 million spatial modes and 45 temporal modes need to be stored. Note that the number of stored modes does not enter in the volume and is thus not optimized (see Appendix G). Note also that qubit addresses in the memory can be identified by temporal indexes only at the cost of longer run-time when photon-echo type protocols are used, cf., below for a concrete example.

Implementation -Our proposal provides a viable solution to get rid of the individual control of millions of qubits but the challenge now relies on the realization of an efficient multimode quantum memory. As shown in Ref. [START_REF] Afzelius | Proposal for a coherent quantum memory for propagating microwave photons[END_REF], such a memory could be implemented using a solid-state spin ensemble ( N spins with an inhomogeneous spectral broadening Γ), resonantly coupled (with single spin coupling rate g) to a frequency tunable single-mode microwave resonator (of length L and with damping rate κ to an external transmission line). The resonator serves to enhance microwave absorption and re-emission by the spins. In particular, unit efficiency absorption of a microwave field can be realized if the finesse F of the resonator matches the single-path absorption αL of spins F = (αL)

-1 , i.e., if the cooperativity [START_REF] Afzelius | Impedance-matched cavity quantum memory[END_REF]. Once absorbed, the microwave field can be re-emitted by time reversing the inhomogeneous dephasing using a spin echo technique [START_REF] Chanelière | Quantum Optical Memory Protocols in Atomic Ensembles[END_REF]. Detuning the resonator off and on resonance at the right time, the spin coherence is recovered, leading to a noisefree, unit re-emission probability of the stored photon if C = 1 [START_REF] Afzelius | Proposal for a coherent quantum memory for propagating microwave photons[END_REF]. In the regime κ g √ N Γ, the memory bandwidth is given by 4Γ [START_REF] Afzelius | Proposal for a coherent quantum memory for propagating microwave photons[END_REF], meaning that any input with a spectrum, say, ten times thinner i.e., 4Γ/10 can be stored with close to unit efficiency. Furthermore, the time duration during which an optical coherence can be preserved is limited by the inverse of the homogeneous linewidth γ h [START_REF] Afzelius | Proposal for a coherent quantum memory for propagating microwave photons[END_REF]. Assuming that the storage efficiency is unchanged if the storage time is hundred times shorter than γ -1 h , this means that the number of temporal modes that can be stored with almost unit efficiencies is roughly given by Γ/(250γ h ). Interestingly, a well-identified temporal mode can be released while keeping all the other modes in the memory by appropriately detuning the resonator off and on resonance with the spins at the cost of introducing a dead time between two readouts of half the duration of the stored train of pulses on average.

C = g 2 N κΓ = αL × F = 1
To give an idea of what could be realized in a near future, we estimate that it should be possible to factor 35 in about 1 min using the exact algorithm presented here (with windowed arithmetic and 3D color codes) and a setup combining a memory for storing 38 logical qubits (3 002 spatial modes and 5 temporal modes) and a pro-cessor with 316 physical qubits (we estimate that more than 60 000 qubits would be needed with a standard 2D grid and surface code). If instead of using a spatially and temporally multiplexed memory, the qubits are stored in the same spatial mode and are identified by (6 650) temporal addresses only, we evaluate the same factorization to be possible in about 1 day using a memory bandwidth 4Γ = 2π × 48 MHz and taking into account the corresponding dead time between two memory readouts. In this case, error correction of all the qubits stored in the memory is estimated to take 132 ms meaning the storage time needs to be longer than 132 ms. For a memory bandwidth 4Γ = 2π × 120 MHz, the same factorization would take 9 hours, and error correction is estimated to take 53 ms. As discussed in Appendix H, these requirements can realistically be met with a realization of the memory protocol described before combining a solid doped with rare-earth and a superconducting microwave resonator [START_REF] Bushev | Ultralow-power spectroscopy of a rare-earth spin ensemble using a superconducting resonator[END_REF][START_REF] Staudt | Coupling of an erbium spin ensemble to a superconducting resonator[END_REF][START_REF] Probst | Anisotropic Rare-Earth Spin Ensemble Strongly Coupled to a Superconducting Resonator[END_REF].

Conclusion -

We have shown that the use of a quantum memory for quantum computing is appealing as unprocessed qubits can be loaded into the memory which significantly reduces the size of the processor compared with standard architectures where all qubits are kept in the processor. All-to-all connectivity between logical qubits is reached if each address in the memory can be mapped to only 3 qubits in the processor. The use of a memory allows one to exploit a 3D code on a 2D processor. If we allow each memory mode to be mapped to any qubit in the processor, all-to-all connectivity between physical qubits can be obtained, hence offering many opportunities for error correction and for implementing algorithms with gates operating between non-neighboring qubits.

We acknowledge M. Afzelius, J.-D. Bancal, P. Bertet, E. Flurin, P. Sekatski, X. Valcarce and J. Zivy for stimulating discussions and/or for critically reviewing the manuscript. We acknowledge funding by the Institut de Physique Théorique (IPhT), Commissariat à l' Énergie Atomique et aux Energies Alternatives (CEA) and the Region Île-de-France in the framework of DIM SIRTEQ.

Appendix A: Semi-classical Fourier transform

We here discuss the semi-classical Fourier transform presented in [START_REF] Griffiths | Semiclassical Fourier Transform for Quantum Computation[END_REF] and show that its cost is negligible. The standard way to perform the Fourier transform on n e qubits is shown in Figure 3a: it requires a sequence of one Hadamard and controlled phase gates for each qubit. In Shor's algorithm as well as in Ekerå and Håstad's version of Shor's algorithm, the qubits are measured right after the Fourier transform, hence explaining the measurements of each qubit at the end of gate sequences in Figure 3a. The simple rearrangement presented in Figure 3b shows that the measurement can be performed right after the Hadamard provided that the following phase gates are classically controlled by the result of this measurement, see Figure 3c. In this case, the successive classically controlled phase gates operating on the same qubit can be merged together, leading to a circuit with one phase gate, one Hadamard gate and one measurement per qubit. When this semi-classical Fourier transform operates on a register made with n e qubits (the number of bits of the exponent), its cost is linear in n e and is thus negligible compared to the cubic complexity of the exponentiation.

The modular exponentiation needed in Ekerå and Håstad's algorithm, i.e., the operation |e |1 → |e |g e mod N , with the input e and the output g e mod N encoded on n e and n bits respectively, can be implemented from controlled modular additions as we show now. For simplicity, we omit the modulo in this paragraph.

Let e ne-1 . . . e i . . . e 0 be the binary form of e. The exponentiation can first be seen as a sequence of multiplications

g e = ne-1 i=1 g 2 i ei = ne-1 i=1 g 2 i ei (B1)
where each multiplication is controlled by the bit value e i . Figure 4 shows an implementation of such a multiplication in which a quantum register encoding the integer x ends up into an encoding of x × g

H • • • • • • • • φ2 • • • H • • • • • • • • φ2 • • • H • • • • φn e • • • φn e-1 φ2 H (b) Rearranged Fourier transform. H • • • • • • • • • φ2 H • • • • • • • • φ3 φ2 H • • • • • • • • • • φn e φn e -1 • • • φ2 H (c) Semi-classical Fourier transform.
The successive classically controlled rotation gates can be merged.

H • • • • • • • • • + 3 φ2 H • • • • • • • • + 3 φ3 φ2 H • • • • • • • + 3 • • • φn e φn e -1 • • • φ2 H Figure 3
. Different versions of the Fourier transform followed by measurements. They are used to convince the reader that the number of gates in the Fourier transform is negligible with respect to the cost of the exponentiation. These three versions are based on the phase gates φ k defined as a 2 × 2 matrix with diagonal elements 1,

e 2πi 2 k
and zeros off diagonal. Note that the control and target qubits can be reversed in the representation of each controlled phase gate without changing the result.

|ei • |ei |x / ×g 2 i xg 2 i e i = |ei • • • |ei |x / Input x +x(-g -2 i ) × xg 2 i e i |0 / +xg 2 i Input x × |0 Figure 4
. Principle of a modular multiplication circuit transforming a quantum register encoding the integer x into a state encoding x × g 2 i e i . A first product-addition operation transforms auxiliary qubits in

|0 into x × g 2 i if |ei = |1 . Then, a product-addition applies +x(-g -2 i ) with x = x × g 2 i into the register encoding x if |ei = |1 . A final swapping is ap- plied if |ei = |1 to put the quantum register into x × g 2 i e i
and resets the auxiliary qubits to |0 . Note that all the operations are performed modulo N .

the first product-addition appearing in Figure 4 and (y, z, γ) → (x, x, -g -2 i ) for the second one, where the negative power stands for multiplicative inverse modulo N ) when |e i = |1 . In case |e i = |1 , the mapping is performed by considering the binary representation y n-1 . . . y 0 of y and by rewriting the product as

y × γ = n-1 j=0 γ2 j y j = n-1 j=0 γ2 j y j . (B2)
As y j is either 0 or 1, the controlled product-addition can be implemented by a sequence of additions, each of them controlled both by the values of bits |y j and |e i . Figure 5 shows explicitly the decomposition of the first product-addition appearing into each multiplication of the exponentiation.

|ei • |ei • • • • • • • • Input x |x0 • • • • • • • = . . . • • • • • • |xj • • • • • • • . . . • • • • • •        |x / +xg 2 i / +2 0 g 2 i • • • +2 j g 2 i • • • Figure 5
. Decomposition of the first product-addition appearing in each element of the decomposition of the exponentiation into multiplications, see Figure 4.

We deduce that the modular exponentiation requires n e multiplications, each being decomposed into 2n controlled additions and 1 controlled swap between two registers, giving to a total number of 2n e n (n e ) controlled additions (swaps between registers respectively). Each addition needs to be modular, which can be obtained with a specific representation and a standard adder circuit.

Coset representation

The basic idea of the coset representation for adding 2 j γ to a quantum register encoding the integer z is to extend the register for z with m additional qubits and to encode it into the state 1

√ 2 m 2 m -1 k=0 |z + kN . Except at
the bounds, this state is invariant under the addition of N . This implies:

1 √ 2 m 2 m -1 k=0 z + 2 j γ + kN mod 2 n+m ≈ 1 √ 2 m 2 m -1 k=0 z + 2 j γ mod N + kN
i.e. the modular addition of 2 j γ in the register of z can be performed with a standard adder, at the cost of a small error which is exponentially suppressed when increasing m [START_REF] Gidney | Approximate encoded permutations and piecewise quantum adders[END_REF]. Note that the resource needed to initialize the register is negligible with respect to the resource taken to implement the adder, see Appendix C. Taking into account the increase in register size, this means that 2n e (n + m) controlled additions and n e controlled register swaps are needed for realizing Ekerå and Håstad's algorithm.

Controlled operations

A controlled swap operation between two qubits (Fredkin gate) can be performed using two CNOTs and one Toffoli gates, see Figure 6b. Hence the total cost for controlled swaps operating on two registers prepared in the coset representation of integers (encoded each with n + m qubits) is of 2(n + m) CNOTs and n + m Toffoli gates.

For the controlled addition, note first that since we use the coset representation of integers, a circuit for controlled addition modulo a power of two is sufficient to implement a controlled modular addition. Such an addition can be implemented with the semi-classical adder presented in Figure 6a, which is inspired by Refs. [START_REF] Sanders | Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization[END_REF][START_REF] Cuccaro | A new quantum ripple-carry addition circuit[END_REF][START_REF] Gidney | Halving the cost of quantum addition[END_REF]. It shows the basic circuit taking a classical value 2 j γ and a register encoding z and returning 2 j γ and z +2 j γ if the two controlled qubits |e i and |x j are both in state |1 . When such an addition is applied on a quantum register encoding z using n + m qubits, the block in the dashed box of Figure 6a is repeated n + m -2 times, giving a mean cost of 5.5(n+m)-9 CNOTs and 2(n+m)-1 Toffoli gates.

(a) Doubly controlled semi-classical addition 4) is obtained by applying it to each pair of qubits.

|ei • • |xj • • |0 • • • • • • • • • |0 (2 j γ) 0 • • • |z 0 • • |s0 |0 • • • • • |0 (2 j γ) 1 • • • • • |z 1 • • |s1 |0 |0 • (2 j γ) 2 • |z 2 |s2 (b) Controlled swap • • × = • × • •

Number of gates

Given the number of gates in the controlled addition and swap operations, the number of additions and swaps in the multiplication and the number of multiplications in the modular exponentiation, we estimate that factorization takes at leading order 11n e (n + m) 2 CNOTs and 4n e (n + m) 2 Toffoli gates.

Appendix C: Coset representation

Modular addition is typically implemented with variants of the addition: an addition, a comparison, a controlled correction and the clean-up of ancillary qubits [START_REF] Vedral | Quantum networks for elementary arithmetic operations[END_REF]. As exposed in main text, coset representation of integers, introduced by Zalka [START_REF] Zalka | Shor's algorithm with fewer (pure) qubits[END_REF] and formalized by Gidney [START_REF] Gidney | Approximate encoded permutations and piecewise quantum adders[END_REF], can be used to approximate the modular addition with a single standard adder circuit. The basic idea of the coset representation for adding 2 j γ modulo N to a quantum register encoding the integer z is to extend the register for z with m additional qubits and to encode it into the state 1

|0 H • H |0 H • H |0 H • H |z / n +N -1 if x ≥ N +2N -1 if x ≥ 2N . . . +2 m-1 N -1 if x ≥ 2 m-1 N |0 / m . . .
√ 2 m 2 m -1 k=0 |z + kN .
Except at the bounds, this state is invariant under the addition of N . This implies

1 √ 2 m 2 m -1 k=0 z + 2 j γ + kN mod 2 n+m ≈ 1 √ 2 m 2 m -1 k=0 z + 2 j γ mod N + kN (C1)
i.e. the modular addition of 2 j γ in the register of z can be performed with a standard adder (modulo 2 n+m ), at the cost of a small error which is exponentially suppressed when increasing m [START_REF] Gidney | Approximate encoded permutations and piecewise quantum adders[END_REF]. Note also that the precision is improved if instead of adding 2 j γ, one adds 2 j γ mod N (which does not change the result of the sum since we consider the sum modulo N ). This is possible each time the quantity to add is known classically.

The goal of the first subsection is to show that the resource needed to extend the register encoding |z into the state

1 √ 2 m 2 m -1 k=0
|z + kN , as requested in this representation, is negligible with respect to the resource taken to implement the modular exponentiation. In the second subsection, we show that the coset representation is compatible with the modular multiplication circuit presented in the main text.

In the two next subsections, the coset representation is considered for additions modulo N ; n is the number of bits encoding N , and m the number of qubits added to the register for the coset representation. (m ancillary qubits in total) which is then uncomputed, see Figure 7. The controlled addition is performed using the circuit presented in Figure 6a with only one control qubit. The uncomputation of the ancillary qubit is based on a measurement and depending on the result, a conditioned correction is realized, see Figure 7. Let us detail the uncomputation of the first ancillary qubit presented in Figure 7. When the result of the measurement is 0, the register made with n + m qubits is projected into

1 √ 2 (|z + |z + N ). When the result is 1, the register state is 1 √ 2 (|z -|z + N )
and the operation -1 needs to be applied to the component |z + N , i.e., when the state of the register encodes an integer larger than N . In order to implement the conditioned operations for decomputing the m ancillary qubits, we need to compare the value x encoded in the quantum register of size n + m and an integer y known classically satisfying 0 < y ≤ 2 m-1 N < 2 n+m (see the last umcomputation in Figure 7) i.e. that can be written with n + m bits. This comparison is implemented using the circuit presented in Figure 8a. First, the value 2 n+m -y = y is computed classically. Then the last carry of the sum of x and y is computed with a circuit derived from the addition. If the value of this carry is 1, we conclude that x ≥ y, otherwise x < y. A Z gate is thus applied on the qubit encoding the last carry, before uncomputing the carries. The register ends up in state ± |x depending on the relative value between x and y, as desired.

Each controlled addition and correction costs O(n + m) gates. This operation is repeated m times, giving a total cost of the coset representation initialization of the order O(m(n + m)).

In the modular exponentiation algorithm, the two registers at the bottom of Figure 4 need to be prepared initially in x = 1 and 0 respectively. Initializing them in the coset representation 1 x ≥ y. This is done in three steps: i) compute the carries of y + x with y = 2 n+m -y, ii) apply a Z operation on the last carry and iii) uncompute the carries.

x0 • • x0 y 0 • • y 0 • • • • • • x1 • • x1 y 1 • • • • y 1 • • • • • • x2 • • x2 y 2 • • • • y 2 Z (b) AND computation • • • = • |0 (c) AND uncomputation • • • = • |0
(b) and (c): circuits defining the notations used to compute and uncompute an AND operation, as introduced in [START_REF] Gidney | Halving the cost of quantum addition[END_REF][START_REF] Babbush | Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity[END_REF] where the authors give efficient implementations in terms of T (or π 4 ) gates. When only one quantum control appear, it uses a CNOT instead of a Toffoli gate, and it can be removed by directly using the control bit instead of the ancillary.

1 √ 2 m 2 m -1 k=0 |kN takes O(m(n + m))
gates which is negligible compared to the cubic cost of the full exponentiation. Note however, that the cost of this initialization is taken into account in our script for the evaluation of the whole algorithm cost.

Compatibility with the multiplication

When computing the multiplications from sequences of two product-additions (see Figure 4 of main text), the input register encoding x and the ancillary register are used both as control and target of the product-additions. We here check that having the control register encoded in the coset representation is not a problem for performing the multiplication.

Let us consider the first product-addition used to implement the multiplication shown in the bottom part of Figure 4. In the coset representation, the input x and ancillary registers are in the state

1 2 m 2 m -1 k=0 |x + kN 2 m -1 k =0 |0 + k N
meaning that after the product-addiction, their state ends up in

1 2 m 2 m -1 k=0 2 m -1 k =0 |x + kN (x + kN )g 2 i + k N mod 2 n+m .
As kN g 2 i + k N is a multiple of N , the obtained state

is very close to 1 2 m 2 m -1 k=0 |x + kN 2 m -1 k =0 xg 2 i + k N
thanks to the coset representation itself, cf. Eq. (C1). The latter corresponds to the desired state.

Appendix D: Windowed arithmetic

In order to reduce the number of multiplications and additions in the exponentiation algorithm, we use windowed arithmetic circuits [START_REF] Gidney | Windowed quantum arithmetic[END_REF]. They consist in grouping the bits of e for controlling each multiplication, hence reducing the number of multiplications. Similarly, for each multiplication, the input bits are grouped to reduce the number of additions composing each multiplication.

The next subsection shows the details of the decomposition of the exponentiation into elementary additions of the form +T k mod N where the quantity T k depends on the value of an integer k. These specific additions are implemented in three steps, that are presented in separated subsequent subsections.

Windowed exponentiation and multiplication

Let us start by specifying the notations. We label the binary form of e as e ne-1 . . . e i+we ei:i+w e e i+we-1 . . . e i . . . e 2 e 1 e 0 (D1)

i.e. e j is the jth bit of e. Let also e i:i+we be defined as

e i:i+we = i+we-1 j=i 2 j-i e j (D2)
i.e. e i:i+we is the number whose bit decomposition is given by the bits of e starting at index i and taking w e bits. The strategy for computing the exponentiation using windowed arithmetic consists in decomposing exponent e in terms of numbers e i:i+we

/ we + wm

Input k / we + wm The comparison with the decomposition of g e presented in Eq. (B1) clearly shows that windowed exponentiation divides the number of multiplications by w e .

Input k Input k = |0 / n Load T k |T k Input T k Unload T k |0 / +T k mod N / +T k mod N
As for the standard algorithm, the multiplications of the product (D4) are implemented successively and each multiplication is decomposed into a sequence of two product-additions, as shown in Figure 9a. The difference is that the added number now depends on the number e i:i+we .

The product-addition is also performed in a windowed way [START_REF] Gidney | Windowed quantum arithmetic[END_REF]. Figure 9b shows in particular how the first product-addition needed for each multiplication is performed using windows for input x of size w m = 3. Figure 9c finally shows the implementation of an addition +T k mod N of a quantity T k that depends on the value k. It requires three steps. First, the number T k is loaded into an ancillary register. Second, this number is unconditionally added to the desired register and finally the ancillary register is cleaned up. Note that the value of T k (given by T k1,k2 = 2 i k 1 g 2 i k2 , with k 1 = e i:i+we and k 2 = x i:i+wm , k being the concatenation of k 1 and k 2 ) to be added is known classically. Its addition being realized modulo N , its value can be computed modulo N before being loaded. n bits are thus sufficient to encode T k .

Loading a value T k into a quantum register is done using a quantum table lookup circuit which we discuss right after. The subsequent subsection is dedicated to the task aiming to unload the value T k and reset the register in state |0 . The last subsection is dedicated to the requested addition.

Table lookup

The quantum table lookup proposed in [START_REF] Babbush | Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity[END_REF], produces the following operation on basis states: |k |x → |k |x ⊕ T k with ⊕ the bitwise XOR operator. For state preparation, as required in the first step of the operation presented in Figure 9c, the target register starts in the state |0 such that control and target registers end in |k |T k . The circuit presented in Figure 10 shows the principle of this operation with registers for k and T k composed respectively of 3 and 5 qubits. Concretely, the numbers T k specify the set of controlled NOT to be used (the question mark on the controlled NOT means that a controlled NOT is applied on qubit i only when the ith bit of T k takes the value 1). The circuit operating on the bits k i of k prepares the last ancillary qubit (line 5 from the top) in the state |1 at the time (specified by k) where the gates corresponding to T k are applied, and |0 otherwise. The building block of the circuit is boxed in Figure 10. It uses 1 CNOT, 1 AND computation and uncomputation. Given that k is encoded into the number of bits w e + w n and can thus take 2 we+wn different values, the number of blocks in the upper part of Figure 10 is given by we+wm-1 j=1 2 j = 2 we-wn -2. This means that 2 we+wm -2 CNOT gates, 2 we+wm -2 AND computations and uncomputations are needed to implement these blocks. Moreover, the number of controlled multi-NOT gates to load the value T k is given by 2 we+wm , each gate being decomposed into n/2 CNOT in average since T k takes n bits. When including the (two) NOT gates operating on the highest bit of k, we conclude that the table lookup uses 2 NOT gates, 2 we+wm -2 + 2 we+wm-1 n CNOT gates, 2 we+wm -2 AND computations and uncomputations (corresponding to 2 × (2 we+wm -2) Toffoli gates).

k2 • • • • • • k1 • • • • • • • • • • • • • • k0 • • • • • • • • • • •

Table unlookup

The purpose of the table unlookup operation (last step in Figure 9c) is to map the state

k α k |k |T k into k α k |k
, where α k are some complex coefficients. A natural way to do this mapping is to apply again the lookup operation described in the previous subsection. Since the lookup operates on the computational basis following |k |x → |k |x ⊕ T k where ⊕ stands for the bitwise XOR operator, by linearity it maps

k α k |k |T k → k α k |k |0
, the latter corresponding to the desired state when simply discarding the qubits previously encoding the numbers T k .

However, a more efficient measurement-based technique is possible, as shown in Ref. [41, Appendix C] and improved in Ref. [START_REF] Gidney | Windowed quantum arithmetic[END_REF]. The principle consists in starting by measuring the register encoding T k in the X basis before applying a phase shift conditioned on the result of measurements. For a more detailed explanation, let us start to expand the qubits encoding the numbers T k in bits indexed by j ((T k ) j being the jth bit of T k ). The state before the uncomputation can be written as

k α k |k j (T k ) j j . ( D5
)
Let us now focus on a specific qubit indexed by j * . We label

K 0 = {k | (T k ) j * = 0} and K 1 = {k | (T k ) j * = 1}.
The state before the uncomputation can be rewritten as

  k∈K0 α k |k j =j * (T k ) j j   |0 j * +   k∈K1 α k |k j =j * (T k ) j j   |1 j * . (D6)
By applying a Hadamard gate on the j * th qubit, we obtain

1 √ 2      k∈K0 α k |k j =j * (T k ) j j + k∈K1 α k |k j =j * (T k ) j j      |0 j * + 1 √ 2      k∈K0 α k |k j =j * (T k ) j j - k∈K1 α k |k j =j * (T k ) j j      |1 j * . (D7)
Hence, if the measurement of the j * th qubit yields 0, the qubit is properly uncomputed. If the result is 1, a phase shift needs to be applied on states corresponding to the indexes k ∈ K 1 .

This uncomputation is successively applied to all the qubits encoding the numbers T k . Let t j be the measurement result of the jth qubit. The state after all the measurements is given by

k α k σ k |k , ( D8
)
with σ k = j (-1) tj (T k ) j . We now label

K = {k | σ k = -1}. (D9)
In order to recover the desired state, we need to correct selectively the phase of terms |k for which k ∈ K. Representation of the four steps proposed in Ref. [START_REF] Gidney | Windowed quantum arithmetic[END_REF] to selectively change the phase of components |k in the state given in (D8) when the index k belongs to K (D9). The central operation is a table lookup with the values F ks: = 2 s -1 j=0 2 j δ(j + 2 s ks:) where δ() is the indicator function of K.

The selective phase correction is done in four steps [START_REF] Gidney | Windowed quantum arithmetic[END_REF], as shown in Figure 11. First, the control register which uses w e + w m qubits in state |k is split in two groups. The first group is made with s qubits in state |k :s . The second group takes the remaining w e + w m -s qubits in state |k s: , such that |k = |k s: ⊗ |k :s and k = k :s + 2 s k s: . The second step consists in writing the integer k :s in an ancillary register in the unary representation: a register with 2 s qubits representing a number k :s with the state of the qubit number k :s being |1 and all the other qubits in the state |0 . The qubits in state |k s: and the ancillary qubits are then used as control and target qubits for a lookup circuit where the controlled multi-NOT gates are replaced by controlled multi-Z gates. Finally, the ancillary register is uncomputed. The circuit used to initialize the ancillary register in shown in Figure 12a. The one used to put it back in its initial state is given in Figure 12b.

Starting from x encoded in s qubits, the conversion to the unary representation takes 1 NOT gate, 2 s -1 CNOT gates and 2 s -1 AND computation. The conversion back to the binary representation takes 1 NOT gate, 2 s -1 CNOT gates and 2 s -1 AND uncomputation. Given that k is encoded in w e + w m bits, and that a choice s = we+wm 2 is judicious to minimize the number of gates, the change of phase of components |k takes

• • • • • • •    |x |0 • • • • • • • • • • • • • • (b) Unary to binary conversion • • • • • • •    |x • • • |0 • • • • • • • • • • • Figure 12.
(a): representation of the circuit proposed in Ref. [START_REF] Gidney | Windowed quantum arithmetic[END_REF] for preparing a copy in a ancillary register of an integer x in a unary representation starting from an encoding of x in a control register in the binary representation. The first not operation prepares the first qubit in the ancillary register in state |1 . The first AND computation writes the result of an AND operation between the first bit of x and the bit 1 encoded in the first qubit of the ancillary register into the second qubit of the ancillary register. In case the state of the latter is |1 , the state of the first qubit of the ancillary register is changed to |0 . The combination of AND and CNOT operations is successively repeated until the desired qubit of the ancillary register is in state |1 . (b): representation of the circuit proposed in Ref. [START_REF] Gidney | Windowed quantum arithmetic[END_REF] to erase the value in the ancillary register while keeping the integer x into the control register. The circuits (a) and (b) corresponds to the first and third operations needed for the selective phase correction operation presented in Figure 11.

we +wm 2

+1 +4 1-qubit gates, 2 -3 ANDs.

Standard adder

As we use the coset representation of integers with windowed arithmetic operations, a circuit for unconditional addition modulo a power of two is sufficient to implement a modular addition. The adder we use, which is described in [START_REF] Gidney | Halving the cost of quantum addition[END_REF] and optimized from [START_REF] Cuccaro | A new quantum ripple-carry addition circuit[END_REF] for use with T gates, is presented in Figure 13. It is thrifty in gate number and ancillary qubits, at the cost of being deeper than other circuits [START_REF] Draper | Addition on a Quantum Computer[END_REF][START_REF] Draper | A logarithmic-depth quantum carry-lookahead adder[END_REF], which is not a disadvantage for our architecture.

x0 • • • x0 y0 • • (y + x) 0 • • • • x1 • • • x1 y1 • • (y + x) 1 • • • • x2 • • • x2 y2 • • (y + x) 2 • x3 • x3 y3 (y + x) 3
Figure 13. Adder modulo 2 4 from [START_REF] Gidney | Halving the cost of quantum addition[END_REF], using the same notations as in Figure 8. The building block (boxed) is repeated two times, for the qubits numbers 1 and 2, while the first and last use a simplified subcircuit.

As presented in Figure 9c, the adder needs to add a number T k taking n qubits into a register with n + m qubits. To achieve this, either the first register for T k is extended with qubits in the |0 state, either we use carry propagation blocs for the last qubits. Such blocs are identical to the ones of semi-classical adder with classical input 0; see [START_REF] Sanders | Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization[END_REF]Fig. 17] for an example of such a circuit. For gate counting, the first solution is taken into account.

The cost of the addition circuit (Figure 13) is 6(n + m) -9 CNOT gates and n + m -1 AND computations and uncomputations.

Cost estimation

In summary, the parameters of the logical circuit for computing the modular exponentiation are n number of bits of the exponentiated number g n e number of bits of the exponent e w e window size for the exponentiation w m window size for the multiplication m number of qubits added by the coset representation The aim of this subsection is to give an estimate of the number of gates needed to implement this circuit. In order to keep the evaluation independent of the error correction choice, we express the cost in terms of the number of 1-qubit, 2-qubit gates and AND computation and uncomputation [44].

The modular exponentiation consists in n e /w e multiplications, each multiplication using 2 product addition and a swap and each product addition is implemented with (n+m)/w m lookups, additions and unlookups. Note that the swap operation is realized by simply relabeling the register, hence is for free. According to the counts obtained from previous subsections, the cost of the exponentiation is dominated -in the limit n → ∞, n e = O(n), w e and w m constant -by: 2 ne(n+m)n Toffoli gates). Note that when considering the universal gate set T , S, H, X, Y , Z, CNOT, controlled-Z and their conjugate, according to Fig. 4 of Ref. [START_REF] Babbush | Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity[END_REF] the AND computation and uncomputation costs in average 8 1-qubit gates and 3.5 2-qubit gates. The total cost of the exponentiation is hence given at the leading order by 2 ne(n+m)n wewm (9n + 8m) 1-qubit gates and (2 we+wm n + 19(n + m)) ne(n+m) wewm 2-qubit gates. In the code used to compute the required resources and find the optimal parameters, the complete formula have been used [22].

Appendix E: Error correction

This appendix is dedicated to 3D gauge color codes. The first subsection is dedicated to the principle of subsystem codes. The second subsection describes the geometrical structure of 3D gauge color codes. The last subsection provides a detailed description of the cut of the code structure that is used to process and correct the logical qubits.

Subsystem codes

Subsystem stabilizer codes [START_REF] Poulin | Stabilizer Formalism for Operator Quantum Error Correction[END_REF] are defined by three subgroups of the Pauli group: the stabilizer, gauge and logical (also designated as bare logical in [START_REF] Bombín | Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes[END_REF]) operator groups, such that the stabilizer group is the center of the gauge group up to phases, i1 is included in the gauge group, the operators from the gauge and logical groups commutes, and the normalizer of the stabilizer group is the product of gauge and logical groups. We invite the reader to look at Refs. [START_REF] Bombín | Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes[END_REF][START_REF] Poulin | Stabilizer Formalism for Operator Quantum Error Correction[END_REF] for an explicit construction of those groups from canonical generators of the Pauli group. The stabilizer group plays the standard role of stabilizers, i.e. divides the total Hilbert space H into a direct sum of orthogonal subspaces C ⊕ C ⊥ where Cthe stabilized subspace -corresponds to the eigenspace +1 of all stabilizers. The gauge and logical groups decompose the stabilized subspace C into a tensor product of the logical qubits space A and the gauge qubits space B [START_REF] Zanardi | Quantum Tensor Product Structures are Observable Induced[END_REF], that is, the Hilbert space is decomposed as

H = (A ⊗ B) C ⊕C ⊥ .
The gauge group acts trivially on the logical qubits and is the Pauli group of the gauge qubits while the logical group acts trivially on the gauge qubits and is the Pauli group of the logical qubits (up to phases). This ensures that gauge operator measurements don't modify the logical qubits.

A gauge fixing operation consists in switching from a code to another one such that the new stabilizer group includes the original one while being included into the original gauge group, while keeping unmodified the logical group. The decomposition associated to the original code

H = (A ⊗ B) C ⊕C ⊥ then becomes of the form H = (A ⊗ B ) ⊕ (A ⊗ B ) ⊕ C ⊥ C ⊥
where B is the new gauge qubit space. As a consequence, a valid code-word for this new code is also valid for the initial one. The passage of the latter to the new code is done by measuring the generators of the gauge group, the results of these measurements giving the correction to apply on B ⊕ B to remove the components on B .

For 3D gauge color codes, code switching allows a transversal error-corrected implementation of a universal set of gates [START_REF] Bombín | Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes[END_REF].

Code geometrical structure

The geometrical structure of the 3D gauge color codes is described in detail in Section 3.1 of [START_REF] Bombín | Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes[END_REF]. It takes a large tetrahedron, itself decomposed into elementary tetrahedrons, see Figure 14 for an example. Four extra points (v i , i ∈ {1, 2, 3, 4}) are then added outside the large tetrahedron, one point in front of each facet of the large tetrahedron. Elementary tetrahedrons are finally added between those extra points and the vertices at the surface of the large tetrahedron, see Fig. 4b of [START_REF] Beverland | Cost of Universality: A Comparative Study of the Overhead of State Distillation and Code Switching with Color Codes[END_REF] for an illustration. The vertices of elementary tetrahedrons are colored with 4 different colors such that adjacent vertices get a different color. Each elementary tetrahedron represents a physical qubit.

The measured operators are the gauge generators for the code used to implement the H and CNOT gates -the (1, 1) code (see [START_REF] Bombín | Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes[END_REF]). These generators are described by the edges: each operator is the product of X or Z operators of the elementary tetrahedrons adjacent to a given edge (each operator implies up to 6 physical qubits).

The stabilizer generators of the (1, 1) and (1, 2) codes (the (1, 2) code refers to the code used to implement the T gate [START_REF] Bombín | Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes[END_REF]) which are described by the vertices and edges, are deduced from the values of measured operators. More precisely, the operator corresponding to a vertex can be written as the product of the operators corresponding to edges starting at the given vertex and ending on vertices of a common color. Three choices of color are possible, allowing one to recover in three different ways an operator corresponding to a vertex. This redundancy can be used for achieving fault-tolerant error correction in only one measurement of the (gauge) operators related to the edges [START_REF] Bombín | Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes[END_REF].

Let n code be the index of the code which is the number of vertices of the same color on one edge of the large tetrahedron (denoted as n in [START_REF] Bombín | Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes[END_REF]). The code distance is given by d = 2n code + 1, and the number of physical qubits is 1 + 4n code + 6n 2 code + 4n 3 code = d 3 +d 2 [START_REF] Bombín | Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes[END_REF][START_REF] Beverland | Cost of Universality: A Comparative Study of the Overhead of State Distillation and Code Switching with Color Codes[END_REF].

Slicing of the code structure

To process the information, the code structure is decomposed into slices, each slice being map successively into the 2D processor. While several cuts in slices are possible, we choose slices orthogonal to two faces (see Figure 14). The processor need to be sized to fit in the larger slice, that join the edge not included into any of the two faces to the middle of the opposing edge -the magenta slice in Figure 14.

With the lattice described in Ref. [START_REF] Bombín | Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes[END_REF], the central slice corresponds to the elementary tetrahedrons for which all vertices coordinates satisfy x + z = n code -2 or x + z = n code -1 (the elementary tetrahedrons between the two plans defined by the previous equations). Note that the number of slices is given by d -2.

The number of elementary tetrahedrons included in this slice is counted by considering three tetrahedron sets, see Figure 14 and Figure 15. Two sets correspond to the elementary tetrahedrons having a facet at the interplay between two slices (Figure 15a (Figure 15b) is associated to the elementary tetrahedrons with one facet are the interplay between the magenta slice and the green (cyan) slice). The last set is associated to the elementary tetrahedrons having no facet at the interplay between two slices (Figure 15c). One can check that the two first sets include 2(2k + 1) = 2n 2 code -2n code + 1 elementary tetrahedrons. They are 16n code -2 additional elementary tetrahedrons resulting from the 4 added points in the construction of the code. In total, the maximum number of elementary tetrahedron for one slice of the code structure is 6n 2 code + 8n code + 1. Since we consider a processor that can process up to two slices (associated to two different logical qubits) and accounting for the ancillary subsystems needed to measure the gauge generators by a simple factor of two, we obtain the number of physical qubits in the processor specified in the main text. For more details, see the ancillary file tetrahedron_3_bis.scad [22], where each tetrahedron color corresponds to a given slice, the larger being the magenta one.

Threshold of 3D gauge color codes

The value of the threshold for 3D gauge color codes has been evaluated in a few references that we now discuss.

In order to clarify on the context, let us first remind that there are three main definitions of error- In Ref. [START_REF] Brown | Faulttolerant error correction with the gauge color code[END_REF] a clustering decoding scheme is presented and by including a phenomenological noise to the measurement outputs, the authors estimate a code-capacity threshold of 0.46 % and phenomenological threshold to about 0.31 %, suggesting an upper bound on the circuitlevel threshold. Note however that the underlying lattice considered in Ref. [START_REF] Brown | Faulttolerant error correction with the gauge color code[END_REF] (cubic lattice) is different from the one we have considered (body centered cubic lattice (bcc)).

A more recent decoding algorithm is presented in [START_REF] Kubica | The ABCs of the color code: A study of topological quantum codes as toy models for fault-tolerant quantum computation and quantum phases of matter[END_REF][START_REF] Kubica | Efficient color code decoders in d ≥ 2 dimensions from toric code decoders[END_REF] using the bcc lattice, but the authors give an estimate of the code capacity threshold of 0.77 % only. By the way, a slightly better code capacity threshold of 0.80 % has been estimated in Ref. [START_REF] Beverland | Cost of Universality: A Comparative Study of the Overhead of State Distillation and Code Switching with Color Codes[END_REF] under the same assumptions.

Finally, statistical arguments have be used in Ref. [START_REF] Kubica | Three-Dimensional Color Code Thresholds via Statistical-Mechanical Mapping[END_REF] to estimate code-capacity threshold of 3D gauge color codes with ideal decoding to around 1.9 %. This suggests that an appropriate decoder could significantly improve the value of the code-capacity threshold and hence of the phenomenological and circuit-level thresholds.

Since we believe that the determination of the circuitlevel threshold goes beyond the scope of this work, the run-time and resource needed to factor a 2 048-bit RSA integer are given in the main text under the assumption of a threshold of 0.75 %. Since this choice is somehow arbitrary, we give the evolution of run-time and resource as a function of the threshold in Figure 16. More precisely, they are given as a function of the ratio p/p th between the physical error probability per cycle p and the faulttolerant threshold p th which is the only relevant quantity at first order. For p th = 0.75 % and an error probability per cycle and per physical qubit of 10 -3 , this ratio p/p th is given by ≈ 0.13. We emphasize that the value of the threshold for 3D gauge color codes does not change the take home message of the whole paper, namely that the use of a quantum memory in quantum computing strongly reduces the number of qubits in the processing unit. Even when considering for example a circuit-level threshold of 0.2 % and a error probability per operation of 10 -3 , the use of a quantum memory reduces the number of qubits by two orders of magnitude in the processor compared to an architecture without memory for factoring 2 048-bit RSA integers (the same conclusion holds when considering the standard approach using surface code, see Appendix F 3).

Appendix F: Results and possible improvements

We presented in the main text the resources needed to factor 2 048-bit RSA integers corresponding to the most common RSA key size. In the first subsection of this appendix, we discuss the factorization of RSA integers of various sizes. The second subsection is dedicated to a discussion on ways to reduce the run-time to factor RSA integers and in particular, on the trade-off between the number of physical qubits in the processor and the run-time.

Optimal parameters to factor n-bit RSA integers

The resources and parameters needed to factor RSA integers encoded in n bits are specified in Table I. In particular, we consider the factorization of RSA integers with n = 6 bits, the number of bits needed to factor 35. We also consider n = 829 which corresponds to the largest RSA integer factorized so far [START_REF] Boudot | Factorization of RSA[END_REF].

Trade-off between qubits and run-time

We have estimated that an average run-time of 177 days is needed to factor a 2 048-bit RSA number. There are several ways to reduce this number, most of them coming at the cost of using more qubits in the processor. The items below present several ways separately.

• Due to the tetrahedral geometry of the code structure, only one third of the processor qubits are used during the error-correction steps in average. A factor 3 in time could thus be saved by making use of them.

• The logical circuit can be parallelized in several ways, giving a speed-up roughly proportional to the increase in qubit numbers in the processor. More precisely:

-Some operations in the adder can be parallelized (see Figure 13). The controlled NOT operations aligned vertically can be applied at the same time.

-The run-time is dominated by the time spent to implement the CNOT gates of the quantum lookup circuit (see Figure 10) and they are easily parallelizable. A full parallelization, would reduce the factorization of 2 048bit RSA integers to about 27 days, at the cost of using about 12 million qubits in the processor.

-Oblivious carry runways allows parallelization of the adders [START_REF] Gidney | Approximate encoded permutations and piecewise quantum adders[END_REF].

-Other type of adders could exploit further parallelizations, for instance lookahead adders [START_REF] Draper | A logarithmic-depth quantum carry-lookahead adder[END_REF]. -During a product-addition operation, the different additions can be parallelized by computing separately partial sums.

-During the exponentiation, the different multiplications can be parallelized by computing separately partial products.

• The qubit number can be reduced using another slicing of the code structure, at the cost of a longer computation time. For example, if one chooses to cut the tetrahedron by slices parallel to a facet of this tetrahedron, we estimate that a 2 048-bit RSA integer could be factorized with 6 628 qubits in the processor and 354 days.

Decoupling the gain from 3D gauge color code and multimode memory

Two new design elements have been proposed in this manuscript, the use of 3D Gauge color codes and an architecture using a multi-mode memory. We here separate them out and get insight into the improvements from each.

The main motivation to use 3D gauge color codes is to get rid of the magical state factory needed for implementing non-Clifford gates in surface code. However, the transversality of T gate on 3D gauge color codes is strongly linked with the dimensionality, and 2D color codes can't directly achieve it [START_REF] Bombín | Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes[END_REF][START_REF] Bravyi | Classification of Topologically Protected Gates for Local Stabilizer Codes[END_REF]. There is no direct way to make use of a 3D color code on a 2D grid.

The main advantage brought by the memory is to unload qubits from the processing unit to the memory. Using a memory in the standard approach for example (2D grid and surface code), we estimate that a RSA-2 048 integer can be factorized with a 2D surface code in about 68 days using a memory that can store up to 5 million modes and a processor with 184 thousand qubits, 180 thousand being dedicated to the magical state factory and 4 thousand to the logical qubits on the processor. The additional reduction in the processor size in our approach comes from the fact that there is no need for magic state distillation in the use 3D gauge color codes. The number of qubits in the processor is kept small because the qubits are released from the memory and process slice by slice. We would like to first emphasize that the main objective of our project was to evaluate accurately the performance of an architecture in which unprocessed qubits are stored in a quantum memory. The standard approach suffers from the need of millions of individually controlled qubits and several research entities are dedicating large teams of engineers to tackle this challenge. We have shown through Shor's algorithm that the use of a quantum memory reduces significantly the number of qubits in the processor though a significant change in the way the information is processed and protected against errors. Our results hence provide a solution to an engineering problem and turns it into a physics problem: the implementation of a faithful and multimode memory. Before discussing the requirements on the memory in detail, let us clearly define the notion of multimode memory [START_REF] Simon | Quantum Repeaters with Photon Pair Sources and Multimode Memories[END_REF].

From an algorithm point of view, "spatial modes" are stored modes that can be accessed in constant time, while "temporal modes" can only be sequentially recoverable (first stored, first release). In the proposed implementation based on spin-echo, temporal modes correspond to different time slots, photons arriving in different time bins being remitted sequentially after spin refocusing. Spatial modes correspond to either different spatial (transverse) modes of a cavity or to different cavities (with possibility to combine both). As discussed in the main text, it is possible to use temporal multiplexing only, at the cost of increasing the run-time.

We now estimate that the factorization of RSA-2 048 integers with the proposed architecture would take a memory with the following characteristics:

• A large multimode capacity to store 28 million spatial modes, each spatial mode being used to store 45 temporal modes. We stress that the number of modes in the memory has not been optimized (only the number of qubits in the processor and the run-time are optimized). Note also that different choices of processing and error-correction protocols may lead to compromises between the numbers of processing qubits and multimode capacity, if needed. For example, we estimate that RSA-2 048 integers can be factorized in 68 days with a 2D surface code using a memory that can store up to 5 million modes and a processor with 184 thousand qubits in the processor.

• Storage time greater than 186 ms. More precisely, we estimate that the maximum storage time between two readouts of the same qubits is less than 2 hours. A memory with a storage time of at least two hours is however not necessary as errorcorrection steps can be implemented periodically at the cost of increasing the run-time. Error correction of all the qubits stored in the memory is estimated to take 186 ms with a processor having 13 436 qubits, meaning that the storage time simply needs to be longer than 186 ms. Applying a correction every second for example would increase the run-time by about 23 %.

• Error probability for a transfer to memory, storage, and retrieval less than 0.1 %. Note that this requirement for a complete cycle of write/read from memory is likely very conservative. Indeed, the threshold value of error correction is mainly determined by the errors happening during the stabilizer measurements. We thus conjecture that the error correction could handle higher error rate for those specific operations. The effect of this strongly dissymmetric noise between the memory/processor operations is still under investigation, and we choose to stick to the conservative hypothesis for this article.

• The information stored in a given memory mode can be mapped to 3 qubits of the processor: two for the 2-qubit gates (depending on whether the physical qubit is the logical control or target qubits) and one for the error correction and 1-qubit gates.

No need for an all to all connectivity.

Appendix H: Realization combining a rare-earth doped solid and a superconducting resonator

For implementing a multimode memory with a spinecho technique, materials doped with rare-earth, such as Erbium Er 3+ provide an appealing example since these ions have doubly-degenerate Zeeman states which split when an external magnetic field is applied. Several manuscripts have reported on the successful coupling between the crystal Er 3+ :Y 2 SiO 5 and a superconducting microwave resonator [START_REF] Bushev | Ultralow-power spectroscopy of a rare-earth spin ensemble using a superconducting resonator[END_REF][START_REF] Staudt | Coupling of an erbium spin ensemble to a superconducting resonator[END_REF][START_REF] Probst | Anisotropic Rare-Earth Spin Ensemble Strongly Coupled to a Superconducting Resonator[END_REF]. Ref. [START_REF] Probst | Anisotropic Rare-Earth Spin Ensemble Strongly Coupled to a Superconducting Resonator[END_REF] in particular reported on the strong coupling with a collective coupling rate g √ N = 2π × 34 MHz and an inhomogeneous linewidth Γ = 2π × 12 MHz. This results in a very high absorption coefficient α = 4.0 m -1 . If we assume a L = λ/2 cavity, unit absorption and reemission efficiencies are obtained if the quality factor is Q = F = 2π/(αλ) ≈ 26 for a 5 GHz cavity. In this low-Q regime, κ Γ and a coherence time of a few hundreds of microseconds would translate into a multimode capacity of a few tens of modes. By working with crystals having lower doping concentrations, the coherence time can be significantly increased [START_REF] Le Dantec | Twenty millisecond electron-spin coherence in an erbium doped crystal[END_REF], while still reaching the impedance matching point with low-Q resonators. In this case, a few thousand modes might realistically be stored very efficiently. Rare-earth doped materials is not the only option and other candidates such as negatively charged nitrogen vacancy color centers in diamond [START_REF] Kubo | Hybrid Quantum Circuit with a Superconducting Qubit Coupled to a Spin Ensemble[END_REF] or bismuth donors in silicon [START_REF] Ranjan | Multimode Storage of Quantum Microwave Fields in Electron Spins over 100 ms[END_REF] may be even more promising.

Figure 1

 1 Figure1. Quantum computer architecture using a processor made with a 2D grid of qubits and a memory operating as a qubit register where the address of each qubit is specified by a temporal and spatial index. Only (dressed) logical qubits are represented; additional ancillary qubits are used for measuring the operators for error correction.

Figure 2 .

 2 Figure 2. Number of qubits in the processor and run-time to factor n-bit RSA integers with a computer architecture using a multimode memory.

Figure 6 .

 6 Figure 6. Controlled operations. (a): semi-classical adder taking each bit of the classical value 2 j γ = 2 k=0 2 k (2 j γ) k and the three qubits register encoding z as inputs and returning (2 j γ) k and |s k = (z + 2 j γ • ei • xj) k . The block in the dashed box uses in average 5.5 CNOTs and 2 Toffoli gates. (b): Fredkin gate implemented with a Toffoli and two CNOT gates. The controlled swap between registers (as required in Figure4) is obtained by applying it to each pair of qubits.

Figure 7 .

 7 Figure 7. Preparation proposed in [35, Fig. 1] of a quantum register with n + m qubits in the state 1 √ 2 m

1 √ 2 m 2 m - 1 k=0

 11 Starting from a register with n qubits in state |z , the initialization of the coset representation consists in preparing the state |z + kN in an extended register of size n + m. This is done by performing successive additions, each controlled by an ancillary qubit prepared in the state |0 +|1 √ 2

√ 2 m 2 m - 1 k=0|1

 1 + kN and(a) Semi-classical comparison and correction

Figure 8 .

 8 Figure 8. (a): Circuit inspired from [4, Fig. 17] which compares the integer x encoded in n + m qubits and the integer y < 2 n+m known classically, and returns -|x if and only ifx ≥ y. This is done in three steps: i) compute the carries of y + x with y = 2 n+m -y, ii) apply a Z operation on the last carry and iii) uncompute the carries. (b) and (c): circuits defining the notations used to compute and uncompute an AND operation, as introduced in[START_REF] Gidney | Halving the cost of quantum addition[END_REF][START_REF] Babbush | Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity[END_REF] where the authors give efficient implementations in terms of T (or π 4 ) gates. When only one quantum control appear, it uses a CNOT instead of a Toffoli gate, and it can be removed by directly using the control bit instead of the ancillary.

Figure 9 .

 9 Figure 9. Windowed arithmetic subcircuits for the modular exponentiation. When not specified, the register size is n+m qubits (register encoded into the coset representation of integers).

wewm 1 -

 1 qubit gates, (2 we+wm n + 12(n + m)) ne(n+m) wewm CNOTs, and 2 ne(n+m) 2 wewm AND computations and uncomputations (translatable into 4 ne(n+m) 2 wewm

2n code- 2 k=1k

 2 = 2n 2 code -3n code + 1 elementary tetrahedrons while the last set has (2n code -1)+ n code -2 k=0

Figure 14 .

 14 Figure 14. Code geometrical structure for n code = 3 (without the extra points (vi, i ∈ {1, 2, 3, 4}). Each slice has been represented with a specific color. The larger slice is with the magenta elementary tetrahedrons. The figure shows that the maximum number of slices involved in an operator corresponding to an edge is 2.

Figure 15 .

 15 Figure[START_REF] Diffie | New directions in cryptography[END_REF]. Decomposition of the central slice for n code = 3 (magenta slice in the tetrahedron presented in Figure14). Each subfigure corresponds to a set of elementary tetrahedrons of the central slice, seen from different point of views. On (a) and (b), each triangle corresponds to an elementary tetrahedron. On (c) each small rectangle correspond to an elementary tetrahedron.

Figure 16 .

 16 Figure16. Number of qubits in the processor and run-time to factor of 2 048-bit RSA integers in function of the ration between the physical qubit error and the fault-tolerant code threshold.

  Appendix G: Memory requirements to factor RSA-2 048 integers

  Multiplication for the exponentiation, with i = 2 and we = 2, decomposed into product-additions.

	|e	 (a) Input ei:i+w e        	=	Input ei:i+w e	Input ei:i+w e
	|x / ×g 2 i e i:i+we mod N	|x /	Input x	+x -g -2 i e i:i+we	mod N
				|0 / +xg 2 i e i:i+we mod N	Input x	0|
			(b) Windowed product-addition, as needed in (a), with the windows size wm = 3.
		/ we	Input ei:i+w e	/ we	Input ei:i+w e	Input ei:i+w e
					Input x0:3
			Input x	=
						Input x3:6
		/ +xg 2
						e =	2 i e i:i+we ,	(D3)
						0≤i<ne
						i≡0 mod we
					such that
						g e =	g 2 i ei:i+w e .	(D4)
						0≤i<ne
						i≡0 mod we

i e i:i+we mod N / +2 0 x0:3g 2 i e i:i+we mod N +2 3 x3:6g 2 i e i:i+we mod N (c) Modular addition of a number read with a table lookup, as needed in (b).

  Example of a quantum table lookup. For a basis state |k specifying the address of the number T k from a classical table, the quantum table lookup maps basis states |k |0 into |k |T k .Here k and the output are composed respectively of 3 and 5 qubits. The notations for the AND computation and uncomputation is presented in Figure8. Black and white circles are controls on the |1 and |0 states respectively. The question mark on the controlled NOT means that a controlled NOT is applied on qubit i only when the ith bit of T k takes the value 1.

									•
	|0	?	?	?	?	?	?	?	?
	|0	?	?	?	?	?	?	?	?
	|0	?	?	?	?	?	?	?	?
	|0	?	?	?	?	?	?	?	?
	|0	?	?	?	?	?	?	?	?
		T7 T6	T5 T4	T3 T2	T1 T0
	Figure 10.

  we+wm-1 +2 Hadamard gates and n measurements on T k , we conclude that the table unlookup takes 2

						we+wm 2	+1 +
	2 3 ANDs (1 NOT gate, 2 we +wm 2 -4 CNOTs and 2 we +wm 2	we+wm 2 -1 CNOT gates and + 2 we +wm 2 -
	2	we +wm 2	-1 AND computation for the unary conver-
	sion, 2 × 2	we+wm 2	Hadamard gates around the table
	lookup, 2 NOT gates, 2	we+wm 2	-2 + 2 we+wm-1 CNOT
	gates, 2	we+wm 2	-2 AND computations and uncomputa-
	tions for the lookup circuit and 1 NOT gate, 2	we +wm 2	-
	1 CNOT gates and 2	we +wm 2	-1 AND uncomputa-
	tion for the binary conversion). Including the additional
	n we+wm 2	+1 + n +
	4 1-qubit gates, 2 we+wm-1 + 2	we +wm 2	+1 + 2	we+wm 2	-
	4 CNOTs and 2	we +wm 2	+ 2	we+wm 2

Table I .

 I For different integer sizes n and corresponding exponent size ne (∼ 1.5n), the table presents the optimal set of parameters, processor size and computation run-time, and the memory requirements.

	n	ne m we wm d n qubits	texp	logical qubits total modes spatial modes temporal modes all memory correction
	6	6 4 3 2 7	316 1 min	38	6 650	3 002	5	95 µs
	8	9 8 3 2 13 1 060	2 s	58	64 090	15 370	11	319 µs
	16	21 11 3 2 17 1 796	10 s	99	244 035	44 451	15	742 µs
	128 189 19 3 3 29 5 156 50 min	571	6 971 339	736 019	27	8 ms
	256 381 21 3 3 33 6 660 7 hours	1 089	19 585 665	1 813 185	31	17 ms
	512 765 24 3 3 37 8 356 2 days	2 122	53 782 090	4 432 858	35	37 ms
	829 1 242 26 3 3 41 10 244 11 days	3 396	117 097 476	8 697 156	39	66 ms
	2 048 3 029 30 3 3 47 13 436 177 days	8 284	430 229 540 27 825 956	45	186 ms

Decomposition of a modular exponentiation into additions

Appendix B: Decomposition of the exponentiation into elementary gates

In this appendix, we aim to give a clear view of how to decompose the modular exponentiation into elementary gates. The presented method is intended to be simple to understand, but not optimal. A more efficient one is presented in Appendix D.