In Section $4-9$ we mentioned that given a quantum computer of

sufficient size, Shor$$s algorithm will efficiently factor numbers, and

thus break RSA. The method used by Shor$$s algorithm is somewhat

indirect, in that it factors a number by first finding the period of a

specific function. Furthermore, the speedup over classical

algorithms is obtained by using the quantum Fourier transform

$($QFT$)$ to find the period. Once this period is known, we can easily

factor the number. From a high level perspective, the technique

used by Shor$$s algorithm to factor N is as follows: