This post assumes you have a sound understanding of Quantum Mechanics, more precisely eigenstates, superpositions and entanglements

Shor’s algorithm allows us to find a factor of any composite number $N$ in $O((log\ N)^2 (\ log^k\ (log\ N)^2))$ for any random $k$, which is important in this scope to understand, as cryptography’s security baseline is founded on the fact that factoring cannot happen in polynomial time - I have talked on this subject in my post Yes Diffie-Hellman is secure, quoting myself

Because the discrete logarithm is not NP-complete, it is not possible to compute our $\log_ba$ in polynomial time and therefore generating a big prime number to be used in generating a cryptographic key renders exhaustive search attack completely useless. - Ali Abbas

Since Shor’s algorithm runs in polynomial time to the length $log\ N$, it solves the discrete logarithm problem and hence breaks the conjecture on which public key cryptography such as RSA are based upon.

Shor works because the factoring problem can be reduced in finding the period  $r$ ( $0 < r <= N$) which validates the cyclic function $f(n) = n^r = 1\ mod\ N$, in other words, if the $gcd(n, N) = 1$ (n and N are coprime integers), then given $r$ is even, $n^{r/2} - 1$ and $n^{r/2} + 1$ are not multiples of $N$, but $\exists x \in \left \{1,..,N-1\right \} : (n^{r/2} + 1)(n^{r/2} - 1) = x N$. This gives us, $gcd(n, N) \Rightarrow gcd((n^{r/2} + 1), N), gcd((n^{r/2} - 1), N)$, since as we have just seen, both $n^{r/2} - 1$ and $n^{r/2} + 1$ share a common ‘non-trivial’ factor of $N$. Finding $r$ is done by transforming the periodic sequence using a Quantum Fourier Transform.

Quantum Fourier Transform

QFT is simply a Discrete Fourier transformation applied to a quantum amplitude using a unitary operator, meaning, there exists $\hat{U}$ such that $|\tilde{\psi}\rangle = \hat{U}|\psi\rangle$, in other words, assuming a basis state, there exists a vector $\tilde{\psi}$ which is a superposition of all computational basis, defining the orthonormal basis states - it is unitary because the amplitude of the vector never changes as part of the transform.

For example, taking a set of complex numbers, $\left \{n_0,..,n_{N-1}\right \}$, the orthonormal basis state acted upon is: $0\rangle\cdots|N-1\rangle$ defined by $|j\rangle \rightarrow \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{2\pi ijk/N}|k\rangle$.

This means that the Fourier transform of an amplitude $n_j$ is a mapping of an arbitary state $\sum_{j = 0}^{N-1} n_{j} |j\rangle$ to $\sum_{k = 0}^{N-1} {n}'_k |k\rangle$ since ${n}'_{k} = \frac{1}{\sqrt{N}} \sum_{j = 0}^{N-1} n_{j} e^{\frac{2\pi j k}{N}}$ per the Discrete Fourier equation, QFT can then be modelled as follow: $F = \frac{1}{\sqrt{N}}\sum_{j,k}^{N-1} e^{\frac{2\pi j k}{N}} |k\rangle \langle j|$.

Having said that, and not wanting of course to go into a full lecture on QFT - what is most important to understand here is that the speed at which we can apply QFT - by properly aligning the Qubits in a proper Quantum circuit, QFT is computed in order of $O(N^{2})$ gates (assuming of course that all factors of N are $O(logN)$) - an equivalent amplitude of  $2^N$ would require $O(N2^N)$ simple gates.

To find the period $r$ of a random $x$ such as $f(x) = f(x + r)$ and $f(x) = n^x mod\ N$, we create 2 entangled registers (input and output) of size $logN$, both initialized to $\frac{1}{\sqrt{N}}\sum_{n}^{N-1}|n\rangle|0\rangle$. We then compute our periodic function f(x) to each number (remember, register 1 is loaded with an equally weighted superposition of integers 0 to N-1) in our input register and store the value in the second register - due to the superposition state and quantum computation parallelism, this operation is done in one step.  Once the quantum computation is done, we observe the second register for some random value $k$, such that register 1 is collapsed into an equal superposition of each values ranging from $0$ to $N-1$ for each $k$ value; In other words, we have a set values of possible $x$ such as $f(x) = k$, which means we observe a lower integer $c$, such as $n^c\ mod\ N = k$. Our superposition in register 1 being $|c\rangle,|r+c\rangle,|2r+c\rangle,\cdots,|n-r+c\rangle$, we apply a Discrete Fourier Transform (see earlier) on the superposition, this will generate an amplitude of integers (spectrum) which are multiples of  $n/r$; Since we no longer have an equal superposition of states and our superposition in register 1 was periodic in nature, we can observe a state, let’s call it $a$, which has a high probability of being a multiple of $n/r$. Having $a$ and $n$, we can easily compute $r$ and verify whether $f(x) = f(x + r)$. If our verification works, we have found our periodic value and can resume to calculate $gcd((x^{r/2} \stackrel{+}{-} 1), N)$. If not, then we pretty much repeat the process with a random value $x$.

Of course, Shor’s algorithm can be more elaborated into steps and in soft and hard cases whether $r$ divides $q$ or not and if you have followed the core logic of the algorithm which we had quickly undergo, you can only come to realize that Shor’s algorithm is highly probabilistic in nature due to the nature of DFT, hence the more Shor is run, the more it becomes accurate. Quantum computing parallelism provides a significant gains since all states of all values of $n$ are computed in one step. Hence the problem of solving the discrete logarithm problem is in finding the period $r$, which in case of Shor’s is shown to be trivial and faster than classical computing using a Discrete Fourier transform.