Breaking RSA Using Shor's Algorithm

To avoid overloading the reader, we will describe our factoring construction by starting from a simple reference implementation of the quantum part of Shor's original algorithm and then apply optimizations one by one. 

The reference implementation works the way most implementations of Shor's algorithm do, by decomposing exponentiation into iterative controlled modular multiplication. A register $x$ is initialized to the $|1〉$ state, then a controlled modular multiplication of the classical constant $g^{2j} \text{(mod N)}$ into $x$ is performed, controlled by the qubit $ej$ from the exponent $e$, for each integer $j$ from $n_e − 1$ down to 0. After the multiplications are done, $x$ is storing $g^e \text{(mod N)}$ and measuring $x$ completes the hard part of Shor's algorithm. 

Controlled modular multiplication is still not a primitive operation, so it must also be decomposed. It can be performed by introducing a work register y initialized to $|0〉$ and then performing the following two controlled scaled additions: $y += x · k \text{(mod N)}$ then $x += y · (−k^{−1}) \text{(mod N)}$. After these two operations, $y$ is storing the result and $x$ has been cleared to the $|0〉$ state. Swapping the two registers, so that the result is in $x$, completes the multiplication. 

Performing a controlled scaled addition with classical scale factor $k$ can be done with a series of $n$ controlled modular additions. For each qubit $qj$ in the input register, you add $k · 2^j \text{ (mod N )}$ into the target, controlled by $qj$. Controlled modular addition in turn is performed via a series of non- modular additions and comparisons. Finally, using the Cuccaro adder, uncontrolled non-modular additions can be performed with $O(1)$ additional workspace using $2n$ Toffolis. 

Combining the numbers in the preceding two paragraphs implies a Toffoli count of $n_e ·2n·5·2n = 20n_en^2$ for the reference implementation. It constitutes the baseline for the optimizations that we apply in the following sections.