  Typical circuit implementations of Shor's algorithm involve controlled
rotation gates of magnitude $\pi/2^{2L}$ where $L$ is the binary length of the
integer N to be factored. Such gates cannot be implemented exactly using
existing fault-tolerant techniques. Approximating a given controlled
$\pi/2^{d}$ rotation gate to within $\delta=O(1/2^{d})$ currently requires both
a number of qubits and number of fault-tolerant gates that grows polynomially
with $d$. In this paper we show that this additional growth in space and time
complexity would severely limit the applicability of Shor's algorithm to large
integers. Consequently, we study in detail the effect of using only controlled
rotation gates with $d$ less than or equal to some $d_{\rm max}$. It is found
that integers up to length $L_{\rm max} = O(4^{d_{\rm max}})$ can be factored
without significant performance penalty implying that the cumbersome techniques
of fault-tolerant computation only need to be used to create controlled
rotation gates of magnitude $\pi/64$ if integers thousands of bits long are
desired factored. Explicit fault-tolerant constructions of such gates are also
discussed.
