  We describe an implementation of Shor's quantum algorithm to factor n-bit
integers using only 2n+2 qubits. In contrast to previous space-optimized
implementations, ours features a purely Toffoli based modular multiplication
circuit. The circuit depth and the overall gate count are in O(n^3) and O(n^3
log(n)), respectively. We thus achieve the same space and time costs as
Takahashi et al., while using a purely classical modular multiplication
circuit. As a consequence, our approach evades most of the cost overheads
originating from rotation synthesis and enables testing and localization of
faults in both, the logical level circuit and an actual quantum hardware
implementation. Our new (in-place) constant-adder, which is used to construct
the modular multiplication circuit, uses only dirty ancilla qubits and features
a circuit size and depth in O(n log(n)) and O(n), respectively.
