← Quantum Store · Guides · Lessons · Glossary · Packages · About · Türkçe

Quantum Store editors

Factor 15 with Shor's algorithm

The smallest working example of Shor's algorithm, the threat to RSA encryption: 15 = 3 × 5 with quantum phase estimation and the inverse Fourier transform. Tested with Qiskit, explained step by step.

Why is Shor's algorithm famous?

Most encryption on the internet (RSA) rests on factoring very large numbers into primes being practically impossible for classical computers. In 1994 Peter Shor showed that a large enough, error-free quantum computer could do this very quickly.

The idea: turn factoring into period finding

1. Pick an a that shares no divisor with N (here N = 15, a = 7).
2. The sequence a^x mod N is periodic: 7, 4, 13, 1, 7, 4, … The period is r = 4.
3. Once r is found, the factors are computed classically: gcd(7² − 1, 15) = 3 and gcd(7² + 1, 15) = 5.

The hard part is finding the period. A quantum computer does it with phase estimation and the inverse quantum Fourier transform.

The example in this package

shor_15.py builds the circuit with 8 counting qubits and 4 target qubits (12 qubits in total). In 1000 measurements the phases come out near 0, 1/4, 1/2 and 3/4, each with about 25% probability. The period r = 4 is read from the denominators and the program finds the factors 3 and 5.

An honest note

The "a^x mod 15" gates in this circuit were simplified by hand, knowing the structure of the answer. Breaking a real RSA key (2048 bits) needs an error-corrected quantum computer much larger than today's devices. Current estimates are on the order of a million physical qubits. That is why the world is already moving to quantum-resistant (post-quantum) encryption.

Next steps

1. Set A to 2, 4, 8, 11 or 13; see how the period changes.
2. Lower SAYAC (the number of counting qubits) to 3; can the phases still be read?

Installation and running

pip install qiskit
python shor_15.py

Tested with: qiskit 2.5.2, Python 3.12.

Links

• Shor's paper (arXiv:quant-ph/9508027)
• Qiskit documentation

Package contents

• shor_15.py
• README.en.md — this file
• README.md — the same guide in Turkish
• LICENSE — the licence of the files in this package
• KAYNAK.json — a machine-readable summary of the official source

Licence

This package was prepared by the Quantum Store editors and is distributed under the MIT licence.

Quantum Store — https://hakanerdogan.com/en

Example code

The example shipped in the package, run and checked. Comments and printed messages are in Turkish; the code is the same in any language. Everything is in the ZIP.

shor_15.py

"""Shor algoritmasıyla 15'i çarpanlarına ayır (Qiskit).

Çalıştırma:
    pip install qiskit
    python shor_15.py
"""

from fractions import Fraction
from math import gcd

from qiskit import QuantumCircuit
from qiskit.circuit.library import QFTGate
from qiskit.primitives import StatevectorSampler

N = 15
A = 7  # N ile ortak böleni olmayan bir taban
SAYAC = 8  # Faz tahmini için sayaç kübiti


def a_us_mod15(a: int, us: int):
    """|y⟩ → |a**us · y mod 15⟩ işlemini yapan kontrollü kapı (4 kübit)."""
    U = QuantumCircuit(4)
    for _ in range(us):
        if a in (2, 13):
            U.swap(2, 3)
            U.swap(1, 2)
            U.swap(0, 1)
        if a in (7, 8):
            U.swap(0, 1)
            U.swap(1, 2)
            U.swap(2, 3)
        if a in (4, 11):
            U.swap(1, 3)
            U.swap(0, 2)
        if a in (7, 11, 13):
            U.x(range(4))
    kapi = U.to_gate()
    kapi.name = f"{a}^{us} mod 15"
    return kapi.control()


qc = QuantumCircuit(SAYAC + 4, SAYAC)
qc.h(range(SAYAC))
qc.x(SAYAC)  # Hedef yazmaç |1⟩ ile başlar
for q in range(SAYAC):
    qc.append(a_us_mod15(A, 2**q), [q, *range(SAYAC, SAYAC + 4)])
qc.append(QFTGate(SAYAC).inverse(), range(SAYAC))  # Ters kuantum Fourier dönüşümü
qc.measure(range(SAYAC), range(SAYAC))

sayim = StatevectorSampler(seed=5).run([qc], shots=1000).result()[0].data.c.get_counts()
print("Ölçülen fazlar (en sık 4):")
for bitler, adet in sorted(sayim.items(), key=lambda kv: -kv[1])[:4]:
    faz = int(bitler, 2) / 2**SAYAC
    print(f"  {bitler} → faz {faz:.3f} = {Fraction(faz).limit_denominator(N)}  ({adet} kez)")

# Klasik son işlem: fazdan periyodu (r) bul, r çiftse çarpanlar gcd(A**(r/2) ± 1, N).
carpanlar: set[int] = set()
for bitler in sayim:
    faz = int(bitler, 2) / 2**SAYAC
    r = Fraction(faz).limit_denominator(N).denominator
    if r % 2 == 0 and pow(A, r, N) == 1 and pow(A, r // 2, N) != N - 1:
        for aday in (gcd(pow(A, r // 2) - 1, N), gcd(pow(A, r // 2) + 1, N)):
            if 1 < aday < N:
                carpanlar.add(aday)

print(f"Periyot: {A}^r mod {N} = 1 için r = 4")
print(f"Bulunan çarpanlar: {sorted(carpanlar)}")
assert carpanlar == {3, 5}, carpanlar
print(f"Tamam: {N} = 3 × 5")

Related concepts

• Shor’s algorithm · Shor’s algorithm factors large numbers exponentially faster than known classical methods, which is why it threatens RSA encryption.
• Quantum Fourier transform (QFT) · The quantum Fourier transform (QFT) computes the discrete Fourier transform of the amplitudes with H and controlled-phase gates; it underlies period finding and phase estimation.
• Quantum phase estimation (QPE) · Quantum phase estimation (QPE) reads the phase a gate adds to one of its eigenstates as a binary number in counting qubits, using phase kickback and the inverse Fourier transform.
• Post-quantum cryptography (PQC) · Post-quantum cryptography means encryption algorithms that run on today’s classical computers and are believed to stay secure against large quantum computers.

← All packages

Share: X · LinkedIn