Hands-On with Shor's Algorithm: Factoring with a Real Quantum Computer

Get ready to explore and implement the most powerful quantum algorithm—yourself—on IBM's real quantum hardware.

TL;DR

In this article, we break down Shor’s algorithm, the most important quantum algorithm in existence, in a way that's accessible to everyone. You’ll learn why it's a threat to current cryptographic systems, how it works, and most importantly: you’ll actually run it on a real IBM quantum computer. We cover:

• Why factoring matters and how Shor's algorithm undermines RSA

• The difference in performance between classical and quantum approaches

• Hardware limitations in 2025

• How to run a working Python implementation via IBM Qiskit (you can sign up for 10 minutes free compute time per month)

• What quantum-resistant cryptography is and why it matters

🚀 A companion notebook is included that you can execute online for free to try Shor’s algorithm on a real quantum machine—no quantum physics degree required. All you need is an IBM Quantum account to get started.

Part 1: For Everyone

Introduction

In 1994, mathematician Peter Shor devised what is now considered the most important quantum algorithm in existence: Shor's algorithm. It can factor large numbers exponentially faster than any known classical method. This breakthrough is especially significant because modern cryptography relies on the difficulty of factoring such numbers.

What makes this even more exciting is that, in this article, we’ll walk through executing Shor’s algorithm on an actual IBM quantum computer—and yes, anyone with an internet connection and an IBM Quantum account can follow along.

So how close are we to breaking cryptographic systems in 2025? Let’s explore.

Why Factoring Matters

Imagine a safe that takes you 10,000 years to crack with today's tools, but with the right futuristic gadget, you can open it in 10 seconds. That’s the impact of quantum computing on RSA encryption.

RSA encryption secures banking, emails, websites, and even your WhatsApp messages. Its security comes from the fact that it’s really hard for classical computers to factor large numbers (e.g., the product of two huge primes). Shor's algorithm shortcuts that challenge.

But here's the twist: it works efficiently only on quantum computers.

How Quantum Algorithms Work

Quantum algorithms exploit three key principles of quantum mechanics:

• Superposition: Qubits can represent many states at once.

• Entanglement: Qubits can be correlated in ways classical bits cannot.

• Interference: Quantum states interfere to amplify correct answers.

How Qubits and Circuits Make It Happen

In quantum computing, information is stored in qubits—which can be both 0 and 1 simultaneously. To manipulate these, we use quantum circuits. More on these in the technical section.

Shor’s algorithm uses quantum phase estimation to determine the period of a modular function efficiently. This would be infeasible with classical resources.

Shor’s algorithm reduces breaking RSA encryption from a statistically impossible task, to something that can be achieved in minutes or hours.

Local Simulation

While real quantum hardware is limited, you can run quantum algorithms like Shor’s locally. The reason for this is explained in the Technical section. I provide a generic implementation which supports both local, and real quantum computer, execution.

Running the Notebook Online

To run the notebook online using IBM's quantum computers, follow these steps. Skip to Step 4 if you don’t want to create an IBM Quantum account, and instead run locally (locally just means not a quantum computer, and it can still be run on the online notebook).

1. Create a free IBM Quantum account:

   • Sign up at https://cloud.ibm.com/docs/quantum-computing?topic=quantum-computing-get-started.

   • Once registered, generate an API key and create a Quantum instance from your dashboard. If you need help, see https://docs.quantum.ibm.com/guides/setup-channel.

2. Launch the notebook:

   • Open the notebook directly in your browser: Launch via MyBinder

3. Edit the following lines of code in the notebook to input your credentials:

api_key = "XXX"  # Replace with your actual IBM Qiskit API key
instance_name = "YYY"  # Replace with your IBM Quantum instance name or CRN ID

• Once these are set, you’ll be ready to run Shor’s algorithm on a real quantum backend, directly from your browser.

4. To Run a factorization, click on the Restart the Kernel button (double arrows). Thereafter edit the section starting with the below lines. Set ‘run_locally’ to True if you wish to run locally, without creating an IBM account. The number to be factorized can changing the value of ‘N’.

   run_locally = False
   N = 15 # N larger than 15 is likely to cause problems on actual quantum computer. Can run larger locally.

5. Need help? See the official IBM documentation:

   • Setting up Qiskit and Authentication

Where We Stand Today: Limitations

In real life, Shor's algorithm has only been used to factor numbers up to 21 on actual quantum computers. That’s tiny. Why?

Hardware Challenges (slightly technical):

• Noise: Quantum gates are error-prone.

• Decoherence: Qubits lose information fast.

• Gate Depth Limits: Complex operations increase risk of failure.

• Qubit Connectivity: Not all qubits can interact directly.

• Resource Constraints: Fully error-corrected quantum computing is still years away.

The current generation of devices are called Noisy Intermediate-Scale Quantum (NISQ) devices. They are experimental and not ready to run large-scale Shor’s algorithm.

Quantum-Resistant Cryptography

Since quantum computers threaten traditional encryption, researchers are actively developing post-quantum cryptography (PQC). These are algorithms designed to be secure against both classical and quantum attacks. These algorithms will be of utmost importance in the future.

Further Reading

• This video gives a take on Quantum Computing as explained to people of different ages (starting with toddlers). YouTube: Quantum Computing for Everyone (3Blue1Brown). I highly recommend watching it.

• A good (short) course with the mathematics of Quantum Computing is Introduction to Quantum Computing: Zero to Shor’s Algorithm (Udemy). An undergraduate background in Linear Algebra should be sufficient to follow this. The course ends of with the basics of the implementation of Shor’s algorithm.

• If you want to download the code to run it on your desktop, see the Full Source Code on GitHub

Final Thoughts

Shor’s algorithm is a beacon. It shows what quantum computing could do, and it challenges us to build better machines. While we’re far from cracking RSA-2048, every step forward is a step closer to a computing revolution.

And the best part? You can try it from your laptop today.

Part 2: For the Techies

A Peek Under the Hood: Code Snippets

Using IBM’s Qiskit SDK, you can run a version of Shor’s algorithm locally or even on real quantum hardware. Below are some code snippets for working with the Qiskit SDK.

Step 1: Set Up Your Account and Connect

from qiskit_ibm_runtime import QiskitRuntimeService

os.environ["QISKIT_IBM_TOKEN"] = api_key
os.environ["QISKIT_IBM_INSTANCE"] = instance_name
service = QiskitRuntimeService()

Step 2: Create a Simple Circuit

from qiskit import QuantumCircuit

example_circuit = QuantumCircuit(2)
example_circuit.measure_all()

Step 3: Run a Sampler Job

from qiskit_ibm_runtime import Sampler

sampler = Sampler(backend)
job = sampler.run([example_circuit])
print(f"Job ID: {job.job_id()}")

How Qubits and Circuits Make It Happen

In quantum computing, information is stored in qubits—which can be both 0 and 1 simultaneously. To manipulate these, we use quantum circuits:

• Hadamard gates create superpositions.

• Controlled-NOT (CNOT) gates create entanglement.

• Phase gates introduce quantum interference.

These gates are strung together in circuits that carry out operations like the modular exponentiation needed in Shor’s algorithm.

In Qiskit, you can build these using:

from qiskit import QuantumCircuit
qc = QuantumCircuit(4)
qc.h(0)
qc.cx(0, 1)

How the Implementation Works

Shor’s algorithm combines classical and quantum steps. Here’s how it is structured in actual code:

Step 1: Classical Pre-processing

We wish to find the factors of an integer, N.

Pick a random number a such that gcd(a, N) = 1. If it isn’t, you already found a factor.

from math import gcd
import random

a = random.randint(2, N - 1)
if gcd(a, N) != 1:
    return gcd(a, N), N // gcd(a, N)

Step 2: Quantum Period Finding

Use quantum phase estimation to find the period r of a^x mod N.

This step uses:

• Superposition to try many values of x

• Modular exponentiation implemented as a quantum circuit

• Inverse Quantum Fourier Transform (QFT) to estimate the phase

n = math.ceil(math.log2(N))  # Number of qubits needed to represent N
m = 2 * n  # Extra qubits for accuracy in the QPE

qc = QuantumCircuit(m + n, m) # Create a circuit with m phase qubits and n target qubits
qc.h(range(m))  # Create superposition

# Apply controlled unitary operations
for qubit in range(m):
    qc.append(modular_exponentiation(a, 2**qubit, N, n),
        [qubit] + list(range(m, m + n))) qc.append(inverse_qft(m), range(m))

# Apply the inverse QFT to the phase register
qc.append(inverse_qft(m), range(m))

# Measure the phase qubits
qc.measure(range(m), range(m))

Step 3: Classical Post-processing

Check if the period r is valid, and compute:

factor1 = gcd(pow(a, r // 2) - 1, N)
factor2 = gcd(pow(a, r // 2) + 1, N)

If neither is a valid factor, pick a new a and try again.

Quantum-Resistant Cryptography

Since quantum computers threaten traditional encryption, researchers are actively developing post-quantum cryptography (PQC). These are algorithms designed to be secure against both classical and quantum attacks.

Promising Directions:

• Lattice-based cryptography (e.g., Kyber, NTRU)

• Code-based cryptography (e.g., McEliece)

• Multivariate polynomial schemes

• Hash-based signatures (e.g., SPHINCS+)

The NIST Post-Quantum Cryptography Standardization Project is expected to finalize standards for quantum-resistant algorithms within the next year or two.

While we’re not there yet, cryptographers are racing the quantum clock.

What's Next?

Research Directions

• Quantum Error Correction: Makes large-scale computations feasible.

• Better Qubit Designs: Improving coherence times.

• Hybrid Quantum-Classical Algorithms: Use quantum computers for the "hard part" only.