Shor’s Algorithm: How Quantum Computers Might Break Cryptography
Have you ever thought about how your secret messages on the internet are kept safe? Modern systems like RSA encryption keep our information secure by relying on a problem that is really hard for normal computers to solve. In simple terms, they depend on the fact that finding the factors of a very large number is extremely difficult. Then along came Peter Shor in 1994 with an idea that sounded like something out of a sci-fi movie. His algorithm shows that a quantum computer could find these factors really fast. Today we will explain the basic ideas behind quantum computers, describe what Shor’s Algorithm does, and even walk through a playful Python example that mimics the main idea.
What is Quantum Computing?
Before we jump into Shor’s Algorithm, let us have a quick chat about quantum computers. Imagine you are trying to choose your favorite ice cream flavor. A classical computer is like having to pick one flavor at a time. In contrast, a quantum computer is like having the superpower to enjoy both chocolate and vanilla at the same time until you decide which one you truly prefer.
Qubits and Superposition
In a normal computer, information is stored as bits that are either a zero or a one. In a quantum computer, the basic unit is called a qubit. A qubit can be in a state that is a mixture of zero and one at the same time. Think of it as being in a state of “maybe” until you take a closer look. It is similar to when you are in a state of indecision about what meme to share to your friend (based on their humor level which you assume) until you finally click and decide.
Quantum Interference
Now, imagine that many people are sharing different memes in a group chat. Some memes are so funny that they get shared a lot, while others fade away. Quantum interference is a process that makes the good memes (the right answers) become louder and the less funny ones cancel out. In a quantum computer, the different possible outcomes combine in such a way that the correct answer becomes more likely when you check the result.
The Quantum Fourier Transform (QFT)
One of the most important tools in Shor’s Algorithm is the Quantum Fourier Transform. You can think of the QFT as a magic magnifying glass that helps you spot patterns. When you look at a messy picture, you might not see the hidden pattern immediately. But when you use this special magnifying glass, the repeated patterns pop out like a secret code or a funny meme hidden in plain sight.
How Shor’s Algorithm Works
Let us now talk about the big idea behind Shor’s Algorithm in easy and simple way.
The Factoring Challenge
Imagine you have a big number that is like a locked treasure chest. The secret to opening it is hidden in its factors. Classical computers have to try many different keys one by one. It is like trying every single key in your keychain when you really just need to open one door. This process takes a very long time when the numbers are huge.
Step One: Pick a Random Number
The first step is to choose a random number between 2 and the big number minus one. This is like randomly picking one of your keys without knowing if it works. If by any chance this key (number) has a common factor with the big number, then you are in luck and you have already found one of the secret ingredients to open the chest. If not, then you continue with the next step.
Suppose we want to factor the number fifteen.
- We randomly choose a number between two and fourteen. Imagine we pick seven.
- We check the greatest common divisor of seven and fifteen, and since they are coprime, we move to the next step.
Step Two: Find the Secret Beat (The Period)
Here is where the magic begins. For the chosen number, there is a special secret beat called the period. The period is the smallest number that tells us when the pattern of multiplying the chosen number repeats itself. In simpler words, if you keep multiplying the chosen number and then divide by the big number, you will eventually see that the results start repeating after a certain number of steps. This step is like finding the chorus in your favorite song. Once you know how long the chorus is, you can predict when it will come back.
Find the period for our chosen number.
- For the sake of an example, let us switch to a more friendly number. Instead, consider the number two (2).
- We compute: 2¹ mod 15 gives 2, 2² mod 15 gives 4, 2³ mod 15 gives 8, and 2⁴ mod 15 gives 1.
- The period r is 4.
Step Three: Use Quantum Magic for Period Finding
In a true quantum computer, this period finding is done using a quantum trick called quantum phase estimation. The computer creates a big mix of all possible steps (all possible beats) at the same time. Then, thanks to the power of interference (remember our meme analogy?), the computer makes all the wrong beats cancel out, leaving behind a clear picture of the correct period. This is the moment when quantum computers really show off their superpowers.
In a real quantum computer, a special circuit would reveal the period four almost instantly by making all the wrong possibilities vanish with destructive interference.
Step Four: Break the Code
Once you know the period, you can do a little math magic. If the period is even and a certain condition holds (the number raised to half the period is not too close to the big number), then you can use this information to compute the greatest common divisor (gcd) of two numbers. These gcd values are the factors you were looking for. It is like having a recipe that tells you exactly which ingredients to mix to get the perfect cake. And if things do not work out, you simply go back, pick another key, and try again. Quantum computers are persistent like that, and so can be our algorithm!
Break the code using our period.
- Now, calculate 2⁽⁴/²⁾ = 2² = 4.
- Next, find the greatest common divisor of 4 − 1 = 3 with 15 and of 4 + 1 = 5 with 15.
- These calculations yield the factors three and five.
A Simple Python Example (The “Quantum Lite” Version)
Now, let us share a Python example that simulates the idea behind Shor’s Algorithm. Keep in mind that this is a simplified, classical version. We will simulate the period finding using a simple loop because real quantum magic is still waiting in the wings of future computers.
import math
import random
def gcd(a, b):
"""
This function finds the greatest common divisor.
Think of it as checking which numbers are best friends with each other.
"""
while b:
a, b = b, a % b
return a
def find_period(a, N):
"""
Here we search for the period.
We want to find the smallest positive number r such that a raised to the r modulo N equals 1.
In our simulation, we simply try numbers until we hit the right beat.
"""
r = 1
while pow(a, r, N) != 1:
r += 1
return r
def shors_algorithm(N):
"""
This function simulates Shor's Algorithm in a very simple way.
It picks a random number and checks if it can help factor the big number N.
If not, it repeats the process.
This is our version of "quantum lite" that works only for small numbers.
"""
# If the number is even, then we already know one factor
if N % 2 == 0:
return 2, N // 2
# Pick a random number between 2 and N-1
a = random.randint(2, N - 1)
print("Randomly chosen number a is", a)
# Check if this number already gives a factor by being a common friend with N
d = gcd(a, N)
if d > 1:
print("Wow, a lucky break! The greatest common divisor gave us a factor right away.")
return d, N // d
# Find the period (the secret beat) for a modulo N
r = find_period(a, N)
print("The period r found is", r)
# We need the period to be even for the next step to work well
if r % 2 != 0:
print("The period r turned out to be odd. Oops! Let's try with another number a.")
return shors_algorithm(N)
# Compute a^(r/2) modulo N, which is our next clue
x = pow(a, r // 2, N)
print("We computed x as a raised to r/2 modulo N and got", x)
# If x is one less than N, then our secret key did not reveal any new information
if x == N - 1:
print("x is equal to N - 1 which is not helpful. We need to choose a different number a.")
return shors_algorithm(N)
# Now we use the greatest common divisor again to extract the factors
factor1 = gcd(x - 1, N)
factor2 = gcd(x + 1, N)
# Final check: if these factors are trivial, we try again
if factor1 == 1 or factor2 == N:
print("We ended up with trivial factors. Time for another round of picking a new a!")
return shors_algorithm(N)
return factor1, factor2
# Let us factor a small number such as 15. This is like cracking a tiny safe.
if __name__ == "__main__":
N = 15
factors = shors_algorithm(N)
print("\nThe factors of", N, "are", factors[0], "and", factors[1])What Is Happening in the Code?
- Finding the GCD:
This part is like having a helpful friend who tells you when two numbers are best buddies. It is our quick check to see if the random number already shares a secret connection with our big number. - Searching for the Period:
This function is our detective, slowly counting until it finds the repeating pattern in the powers of the number. In a real quantum computer, a quantum circuit would do this in one fell swoop while we sit back and enjoy a good meme. - Putting It All Together:
The main function simulates the overall process. It picks a random number, checks for luck, finds the period, and then uses that period to unlock the factors of the big number. If something does not work out, it politely says, “Let’s try again”.
Output for the above code:
Randomly chosen number a is 14
The period r found is 2
We computed x as a raised to r/2 modulo N and got 14
x is equal to N - 1 which is not helpful. We need to choose a different number a.
Randomly chosen number a is 5
Wow, a lucky break! The greatest common divisor gave us a factor right away.
The factors of 15 are 5 and 3Now, Let’s See an Example Using Qiskit
For those who want a taste of real quantum computing, here is an example using Qiskit —
https://github.com/Qiskit/textbook/blob/main/notebooks/ch-algorithms/shor.ipynb
Quantum Versus Classical: The Real Deal
The real strength of Shor’s Algorithm comes from its quantum routine that finds the order by using quantum phase estimation together with the quantum Fourier transform. Imagine having a superpower that lets you quickly explore a huge number of possibilities by allowing them to mix and cancel out until only the right answer stands out. This is the magic that quantum computers offer. In contrast, classical computers must laboriously examine each possibility one by one.
Even though our Python simulation relies on a straightforward brute-force method, it still captures the essential idea behind the algorithm. Researchers use simulators, such as those provided by Qiskit, to run Shor’s Algorithm on small numbers like 15 or 21. These early demonstrations are like the very first steps of a long journey toward full quantum factoring, showing us that the quantum approach really holds great promise for the future.
In summary, Shor’s Algorithm shows us how quantum computers can quickly find hidden patterns in numbers that make breaking encryption possible. It works by using the special abilities of quantum machines to explore many possibilities all at once and then letting the right answer emerge through interference. While our Python example uses a simple method to illustrate the idea, real quantum computers use advanced techniques such as phase estimation and the quantum Fourier transform. This approach is like having a superpower that lets you instantly sort through an endless list of options, a feat that would take a classical computer an impractical amount of time. Researchers are taking these early demonstrations with small numbers as promising first steps toward a future where quantum factoring becomes a reality.
As quantum hardware improves, we might see real quantum computers performing these tasks in no time. Until then, we can enjoy the humor, memes, and fascinating science behind these ideas. And remember, whether you are a student or simply someone who loves a good quantum pun, the world of quantum computing is full of surprises, laughter, and, of course, brilliant breakthroughs.
Check out this awesome video on Shor’s Algorithm by the man Peter Shor himself!
Happy factoring and may your qubits always be in a state of superposition!
