# 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.
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

--

--

## More from Aashvi Manakiwala

CS @ UPenn | TKS Activator | AI Enthusiast