The steps of RSA is explained below

Shor’s algorithm

Shor’s algorithm is a polynomial-time quantum computer algorithm which is used
for integer factorization. The efficient nature of Shor’s algorithm is due to the efficient
nature of quantum Fourier transform and modular exponentiation by repeated squarings. Shor’s
algorithm consists of two parts,

- A reduction algorithm which is generally performed on a classical computer, in order to reduce the factoring problem to a order finding problem.
- A quantum algorithm to solve the order finding problem.

- A random number is selected (k < n)
- gcd(k,n) is calculated using Euclidean algorithm
- If, gcd(k,n) ≠ 1, then k is a nontrivial factor of n hence stop

- Else, quantum period finding subroutine is used to find r, where r is the period of the function f(x)=kx mod n
- If r is odd or kr/2 ≡ -1 mod n, then jump to step i.
- Else, one of gcd(kr/2+1, n) or gcd(kr/2-1, n) is a nontrivial factor of n hence stop.

- The registers are initialized to
Here, the initial state is a superposition of Q states where q independent qubits are generated, each in a superposed state.

- A quantum function f(x) is constructed which is applied to the above state in order to obtain Uf|x, 0q⟩ = |x, f(x)⟩
- Inverse quantum Fourier transform is applied to the input register.
- A measurement is performed which is used to obtain an outcome y in the input register and some outcome z in the output register.
- Otherwise, jump to step i of this subroutine.

- Since yr/Q is some arbitrary
integer c, so y/Q=c/r. On performing continued
fraction expansion on y/Q we get approximations d/s of it which satisfies two
conditions:
- A. s<n
- B.

- If f(x)=f(x + s) ⇔ ks ≡ 1 mod n, then stop.
- Else using multiples of s obtain more candidates for r, if any candidate works then stop.

- https://www.americanscientist.org/article/is-quantum-computing-a-cybersecurity-threat
- https://medium.com/@jonathan_hui/qc-cracking-rsa-with-shors-algorithm-bc22cb7b7767
- Nielsen, Michael A. & Chuang, Isaac L. (2010), Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press, .
- Shor, Peter W. (1997), “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, SIAM J. Comput., 26 (5): 1484–1509, arXiv: quant-ph/9508027v2 , Bibcode: 1999SIAMR..41..303S, doi: 10.1137/S0036144598347011.
- Quantum Computing and Shor’s Algorithm , Matthew Hayward’s Quantum Algorithms Page , 2005-02-17, imsa.edu
- Shor’s Factoring Algorithm , Notes from Lecture 9 of Berkeley CS 294-2, dated 4 Oct 2004, 7 page postscript document