Breaking RSA Using Shor's Algorithm

Throughout this paper, we refer to the modulus as $N$. The modulus is the composite integer to be factored, or the prime characteristic of the finite field when computing discrete logarithms. The number of bits in $N$ is $n = [\; lg \; N]$ where $lg \; (x) = log_2(x)$. The number of modular multiplication operations to perform (i.e. the combined exponent length in the modular exponentiations) is denoted $n_e$. Our construction has a few adjustable parameters, which we refer to as $c_{exp}$ (the exponent window length), $c_{mul}$ (the multiplication window length), $c_{sep}$ (the runway separation), and $c_{pad}$ (the padding length used in approximate representations). 

In the examples and figures, we consider moduli of length $n = 2048$ bits when n needs to be explicitly specified. This is because $n = 2048$ bits is the default modulus length in several widely used software programs. Our optimizations are not specific to this choice of $n$. Section 3 provides cost estimates for a range of cryptographically relevant modulus lengths $n$. 

We often quote costs as a function of both the number of exponent qubits $n_e$ and the problem size $n$. We do this because the relationship between $n_e$ and $n$ changes from problem to problem, and optimizations that improve $n_e$ are orthogonal to optimizations that improve the cost of individual operations.