Shor’s Algorithm Deep Dive (Shor to blow your mind)

RSA Encryption

Shor’s Algorithm

notice how the exponent is gone for Shor’s Algorithm!
  1. First it chooses a number a that is coprime with N. In other words, a and N do not share any common factors.
  2. Then, it uses modular exponentiation to store 13^z mod 15 in a list for z ranging from 0 to 14. The mod function is basically the remainder you get when dividing 13^z with 15. For example, 13² mod 15 is 4. What is interesting is that these values end up repeating no matter how large 13^z gets. In the graph above, you can see that the y-axis repeats 0, 13, 4, and 7. Now that we have a repeating function, we need to find how often it repeats. This is denoted by the value “r”, called the order or period. r is the smallest number such that 13^r mod 15= 1.
  3. Lastly, it checks if r is an even number. In this case, it assigns a variable x = 13^(r/2) (mod 15) and finds the prime numbers p and q by finding the greatest common factor between x+1 and N and x-1 and N. If r happens to be odd, we need to choose another number a that is coprime with N.
Here is the same graph with N= 375 instead of 15. It’s way more chaotic!
Here’s a drawing I made of the circuit
  1. Create two sets of four zero qubits. We are using four qubits because it can be used to represent 2⁴ (or 16) states, sufficient for N=15, which we are trying to factor.
  2. Next, we add a Hadamard gate to the qubits on the x register (top). This effectively transforms the qubits from the computational basis to the Fourier basis.
These are qubits in the computational basis (aka, the z axis). Image from Qiskit Textbook
The Hadamard gate transforms them to the Fourier basis (aka, the xy plane). Information is stored in terms of angles around the z-axis. Image from Qiskit Textbook
Note: the left vector represents the x register and the right is the w register (which is in superposition to x). 1/4 is a normalization constant, and the plus sign with the circle around it is a bitwise operation. Image from Qiskit
Image from Qiskit
  • If we measure 0, we would have to run this again since this is a trivial solution (j would need to be 0 and r could be anything, so that doesn’t help us).
  • If we measure 4, one pair of j and r is j=1 and r=4. You would run r=4 in step 3 and successfully find 3 and 5 as the factors.
  • If we measure 8, one pair could be j=1 and r=2. Plugging in r=2 into step 3 yields the factors 1 and 3 which is a partial solution. In this case, we could just divide 15 by 3 to obtain the other factor, 5. If we were to plug in r=4 (for j=2) then we would get 3 and 5.
  • If we measure 12, j=3 and r=4. We would get the factors 3 and 5.

Pitfalls

  • We don’t have enough qubits! The amount of qubits, n, we need is over log₂(N). In most general cases, we actually need 2n qubits. For example, a 1000 digit number we are trying to factorize will require 2000 qubits. Today’s quantum computers are not up to this level, so for now, RSA encryption is safe.
  • It may not meet the conditions! There’s a chance (less than 50%) that r is not even or a^(r/2)+1=0. In this case, we will not be able to carry out the classical post-processing and find the prime factors.

Conclusion

--

--

CS @ UPenn | TKS Activator | AI Enthusiast

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store