! Educational demonstration only. Keys, moduli, and RSA sizes here are intentionally tiny so classical/quantum attacks finish in seconds — today's classical hardware cannot run Shor's algorithm against real production RSA keys. See Security & Limitations.
Shor's Lab

The QFT doesn't factor anything by itself -- it turns periodic structure in a superposition into a measurable peak pattern, which is what Shor's algorithm's period-finding step relies on.

0. Apply the QFT and watch it happen

QFT∣x⟩=12n∑y=02n−1e2πixy/2n∣y⟩\text{QFT}|x\rangle = \frac{1}{\sqrt{2^n}} \sum_{y=0}^{2^n-1} e^{2\pi i x y / 2^n} |y\rangle

Run against this project's real quantum/qft.py circuit (H + controlled-phase gates), which is independently verified against this exact matrix definition in the test suite -- shown below as a live validation, not a claim.

1. The actual code behind this step

quantum/qft.py:26-37
def apply_qft(register: GateSink, qubits: list[int]) -> None:
    """Apply the QFT circuit to `qubits` (qubits[0] most significant) in place."""
    n = len(qubits)
    for i in range(n):
        target = qubits[i]
        register.apply_gate(H, target)
        for j in range(i + 1, n):
            control = qubits[j]
            k = j - i + 1  # rotation R_k = diag(1, e^{2*pi*i / 2^k})
            register.apply_controlled_gate(phase(2 * np.pi / 2**k), control, target)
    for i in range(n // 2):
        register.apply_swap(qubits[i], qubits[n - 1 - i])

2. How this connects to period-finding

In Shor's algorithm, a control register is put into superposition, then entangled with a target register via controlled modular exponentiation (so the target register's value depends periodically on the control register's value, with period equal to the order r we're trying to find). Applying the inverse QFT to the control register concentrates the measurement probability at multiples of 2^n_count / r -- try it yourself on the Shor's Algorithm Lab page.

Go deeper: QFT & Period-Finding