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: