Counsel for the
frontier of computation

Research

Technical work and legal analysis on cryptography, patent eligibility and the law of new technology.

All analysis

Post-quantum research

The mathematics behind the transition

Shor’s algorithm connects quantum computation to the mathematics underlying RSA and other widely used public-key systems. A sufficiently large, fault-tolerant quantum computer would change their security assumptions.

This small experiment makes one part of that idea tangible: how quantum order finding can help reveal the factors of a number. Measurements and continued fractions illustrate the underlying mathematics.

A view across the field

PQScope follows research, standards discussions and the people and organizations behind them. These figures describe PQScope’s coverage.

Ideas
—
Active IETF drafts
—
Organizations
—
People
—

Loading published statistics…

Shor’s algorithm · a small experiment

From a measurement to factors

Measurements from a quantum Fourier distribution provide evidence of the hidden period.

N =
a =
Fourier measurementQ = 64 · 6 control qubits
TheoryObserved frequency0 runs
Probability / frequency25%0y = 0: 25.00%y = 1: 0.00%y = 2: 0.00%y = 3: 0.00%y = 4: 0.00%y = 5: 0.00%y = 6: 0.00%y = 7: 0.00%y = 8: 0.00%y = 9: 0.00%y = 10: 0.00%y = 11: 0.00%y = 12: 0.00%y = 13: 0.00%y = 14: 0.00%y = 15: 0.00%y = 16: 25.00%y = 17: 0.00%y = 18: 0.00%y = 19: 0.00%y = 20: 0.00%y = 21: 0.00%y = 22: 0.00%y = 23: 0.00%y = 24: 0.00%y = 25: 0.00%y = 26: 0.00%y = 27: 0.00%y = 28: 0.00%y = 29: 0.00%y = 30: 0.00%y = 31: 0.00%y = 32: 25.00%y = 33: 0.00%y = 34: 0.00%y = 35: 0.00%y = 36: 0.00%y = 37: 0.00%y = 38: 0.00%y = 39: 0.00%y = 40: 0.00%y = 41: 0.00%y = 42: 0.00%y = 43: 0.00%y = 44: 0.00%y = 45: 0.00%y = 46: 0.00%y = 47: 0.00%y = 48: 25.00%y = 49: 0.00%y = 50: 0.00%y = 51: 0.00%y = 52: 0.00%y = 53: 0.00%y = 54: 0.00%y = 55: 0.00%y = 56: 0.00%y = 57: 0.00%y = 58: 0.00%y = 59: 0.00%y = 60: 0.00%y = 61: 0.00%y = 62: 0.00%y = 63: 0.00%03263Measured value y

Each run returns one value, not the whole distribution.

01 · MeasureNo measurements yet.

02 · ReconstructA continued fraction will suggest a denominator.

03 · Verify & factorThe period is not supplied to the reconstruction.

Mathematical details

Q = 64 is below N² = 225. Small registers can work here, but lack the usual general precision guarantee.

This models complete dephasing of the exponent register in its computational basis. Its Fourier outcomes become uniform. Chance samples may still yield factors in these tiny examples; they no longer concentrate near the useful phases.

Changing the instance, register size, or coherence starts a new experiment.

The modular function

The first 16 values of ax mod N. Equal values label the same state of the output register; their exponent amplitudes can interfere.

The Fourier chart is not a transform of these bar heights. It sums amplitudes within each group of equal function values, then adds the groups’ probabilities.

From a sample to an order

A sample gives y/Q ≈ k/r. Continued fractions produce possible reduced fractions; their denominators may be divisors of r. We keep candidates within half a Fourier bin, combine denominator hypotheses by least common multiples, and test aᴿ mod N = 1. A verified exponent is reduced by removing redundant prime factors to obtain the order r.

This is a bounded teaching implementation for N = 15 and 21. The usual textbook choice N² ≤ Q < 2N² gives Q = 256 and 512 respectively. Finite precision can produce incorrect candidates; the modular check is essential.

The latest continued fraction appears after a measurement.

Most recent measurements (0)
RunyCandidate k/raᵈ mod N
No measurements yet.

The ideal distribution

P(y)=1Q2∑z|∑x:f(x)=ze2πixy/Q|2

Here f(x) = aˣ mod N, 0 ≤ x < Q, and 0 ≤ z < N. This is the normalized distribution when the output register is ignored, with no postselection. The simulator computes it from f(x), without using a known period. In the dephased model, P(y) = 1/Q.

An even order helps only when aʳᐟ² is a nontrivial square root of 1 modulo N. An odd order or aʳᐟ² ≡ −1 calls for a different base.

Shor’s paper · Order finding explained

A classical simulation of quantum order finding at toy size. Applying Shor’s algorithm to an RSA-2048 modulus would require a sufficiently large, fault-tolerant quantum computer.