How Shor’s Algorithm Actually Works, Explained from Scratch

Introduction

Most explanations of Shor’s algorithm end up in one of two places. The popular version says “a quantum computer tries all answers at once,” which is wrong. The technical version drops you into modular exponentiation and the quantum Fourier transform, which is correct but useless if the last time you thought about modular arithmetic was never.

This article sits in the gap. I am going to walk through the entire mechanism of Shor’s algorithm from scratch, assuming nothing beyond basic multiplication. By the end you will understand, concretely, where the gate counts and qubit numbers in my CRQC Quantum Capability Framework come from, why researchers keep publishing lower estimates without building anything, and how to spot the papers that are faking it.

One warning: I will simplify some things deliberately, and I will tell you where I am doing it. The simplifications all point in the right direction. Nothing here will mislead you; some things will be incomplete. For the full threat analysis, implications, and what to do about it, see my main Shor’s algorithm threat assessment and the practical steps to quantum readiness.

The One-Way Multiplication Problem

RSA encryption rests on a single bet: multiplying two large prime numbers is fast, but recovering those primes from the product is impossibly slow.

Multiplying is easy. Pick two primes, say 61 and 53. Multiply them: 3,233. A calculator does it in a blink, and the same is true for primes hundreds of digits long.

Factoring is hard. Hand someone 3,233 and ask them to find the two primes that made it, without telling them what those primes are. For a small number like 3,233, trial and error works. For a number 600 digits long (the kind used in a real RSA-2048 key), trial and error would take every computer on Earth longer than the age of the universe. The best classical algorithms are faster than raw trial and error, but they still choke on numbers this size.

That asymmetry (easy to multiply, effectively impossible to factor) is the entire security model of RSA, Diffie-Hellman, and most of the public-key cryptography protecting the internet today.

Shor’s algorithm breaks the hard direction.

Shor’s First Move Was to Change the Puzzle

Peter Shor did not invent a clever way to try divisions faster. He did something stranger: he converted the factoring problem into a completely different puzzle, one that a quantum computer can solve but a classical computer cannot.

The different puzzle is called period-finding. Here is the conversion, step by step, on a number small enough to check by hand.

Building the repeating sequence

Take N = 15, the classic teaching example. Instead of trying to factor 15 directly, pick any small starting number that shares no common factor with 15. I will pick 2.

Now compute the powers of 2, but after each multiplication, divide by 15 and keep only the remainder. (If you have heard the phrase “modular arithmetic,” that is what this is. If you have not, “divide and keep the remainder” is the whole idea.)

Here is the sequence:

2^1 = 2. Divide by 15, remainder is 2.

2^2 = 4. Divide by 15, remainder is 4.

2^3 = 8. Divide by 15, remainder is 8.

2^4 = 16. Divide by 15, remainder is 1.

2^5 = 32. Divide by 15, remainder is 2.

2^6 = 64. Divide by 15, remainder is 4.

The sequence is 2, 4, 8, 1, 2, 4, 8, 1, 2, 4, 8, 1… It repeats. The length of the loop is 4.

This repetition is guaranteed. The remainder after dividing by 15 can only be one of 15 possible values (0 through 14). Since the rule (“multiply by 2, keep the remainder”) never changes, the sequence must eventually revisit a value it already produced. From that point forward, it repeats forever. Every combination of starting number and N produces a loop. The only question is how long the loop is.

From loop length to factors

Here is the part mathematicians discovered in the 1970s, decades before Shor and decades before quantum computers.

The loop length for our example is 4. Watch what happens when I use it:

Take 2 raised to half the loop length: 2^(4/2) = 2^2 = 4.

Compute 4 – 1 = 3 and 4 + 1 = 5. Now find the greatest common divisor (gcd) of each with 15: gcd(3, 15) = 3 and gcd(5, 15) = 5.

3 and 5 are the prime factors of 15. (In this toy example, the gcd step is invisible because 3 and 5 already divide 15 exactly. For larger numbers where the halves are not themselves the factors, the gcd is what extracts them.)

That is not a coincidence. The general version works the same way: when the loop length is even (if it is odd, you pick a different starting number and try again, and this works at least half the time), computing gcd(a^(r/2) – 1, N) and gcd(a^(r/2) + 1, N) yields the factors. The underlying mathematics, a construction called the difference of squares, guarantees this connection. For our purposes the important point is that this connection was proven unconditionally. It always works.

So the entire factoring problem reduces to one question: how long is the loop?

The same trick on N = 21

To show this is not a one-off trick, try N = 21 with starting number 2.

2^1 mod 21 = 2. Then 4, 8, 16, 11, 1. The sequence is 2, 4, 8, 16, 11, 1, and then it repeats. Loop length is 6.

Half of 6 is 3. Compute 2^3 = 8. Then 8 – 1 = 7 and 8 + 1 = 9. Now take gcd(7, 21) = 7 and gcd(9, 21) = 3. The factors are 3 and 7. Here the gcd step does real work: 9 is not itself a factor of 21, but gcd(9, 21) = 3 extracts the prime hiding inside it.

Same recipe, different number, same result. The loop length gives you the factors.

Why Classical Computers Cannot Find the Loop

For N = 15, the loop is 4 steps long. For N = 21, it is 6 steps. Both are trivially short. You could find them with a pencil.

For a real RSA-2048 key, N is a number approximately 600 digits long, and the loop length is itself a number approximately 600 digits long, on the order of 10^600. To appreciate that scale: the observable universe contains roughly 10^80 atoms. The number 10^600 is not “a lot more than 10^80.” It is a number so large that 10^80 is a rounding error compared to it.

The naive classical method for finding the loop is to compute the sequence step by step and wait until it repeats. For a loop length of 10^600, you would need 10^600 steps. No amount of parallel processing helps with that.

Classical cryptanalysts are not that naive, of course. The general number field sieve and other sophisticated algorithms exploit deep number-theoretic structure to factor numbers far faster than brute-force search, and they do not need to find the loop at all. But even these algorithms run in sub-exponential time, meaning their cost still grows steeply as numbers get larger. For RSA-2048, the best classical methods require computational resources so far beyond what exists that the factoring community treats the problem as practically impossible. The precise statement is: no polynomial-time classical algorithm for factoring or general order-finding is known.

And the sequence itself offers no shortcuts along the way. Any stretch of it looks like random noise: numbers jumping around with no visible pattern. There is no “getting warmer” signal, no gradual convergence, nothing to prune.

If you have wondered why RSA has been secure for decades, this is the reason. The loop-length problem is the hard problem that protects RSA. And if you have wondered why Diffie-Hellman key exchange uses the same kind of “multiply and keep the remainder” arithmetic: it is precisely because this arithmetic produces sequences that look like noise to every classical observer. The security of modern public-key cryptography and the impossibility of classical period-finding are the same fact.

How a Quantum Computer Hears the Loop

A classical computer’s only option is to walk the track step by step. A quantum computer takes a different approach entirely: it perceives the loop length directly, without walking the track.

The right comparison is your own ear. When a guitar string vibrates 440 times per second, you do not count individual vibrations. You hear the pitch, A above middle C. Pitch is just how quickly a pattern repeats. Your ear extracts this single number, the repetition rate, from a complex vibration, without tracking each oscillation individually.

Shor’s algorithm does the same thing for the repeating number sequence. Its core quantum circuit extracts the repetition rate (the loop length) without computing every entry in the sequence.

Performing the song

There is a catch. An ear only hears a sound that is physically ringing. You cannot describe a sound to someone and have them perceive its pitch. The air has to vibrate.

The same constraint applies here. The quantum circuit that reads the loop length, called the quantum Fourier transform, works only on a sequence that is ringing inside the quantum computer’s own memory. There is no way to feed it a recording. No such file format exists, and a 10^600-entry sequence could not be loaded in any case. So the machine must perform the recipe, the “multiply and keep the remainder” calculation, inside its own quantum memory.

This is why the multiplications happen on the quantum computer. They are not overhead. They are not a preliminary step that could be outsourced to a data center. They are the striking of the string. Without them, there is nothing to listen to.

The superposition trick

Performing a 10^600-entry sequence sounds even harder than walking the track classically. Here is where the one strange quantum capability enters.

A classical computer computes 2^1 mod N, then 2^2 mod N, then 2^3 mod N, one at a time. To cover the entire sequence, it would need 10^600 separate calculations.

A quantum computer starts differently. It prepares its input register in superposition, a state where the register holds every possible exponent (1, 2, 3, 4, …) simultaneously. This is not a metaphor for parallel processing. It is a physical state of the hardware, and it is the one thing quantum computers can do that classical computers provably cannot.

With every exponent loaded at once, the machine runs the “multiply and keep the remainder” recipe exactly once. One pass of the circuit. The same few thousand multiplications a classical computer would use to compute a single entry.

This is the step that sounds like magic and needs a concrete explanation.

A quantum gate is a physical operation: a microwave pulse, a laser flash, a magnetic field applied for a precise duration. It transforms whatever state the qubits are in. When the input register holds a single definite exponent, say 3, the gate transforms it and produces one definite result: 2^3 mod 15 = 8. Nothing mysterious.

When the input register holds a superposition of all exponents, the gate still performs the same physical transformation. It does not “choose” which exponent to process. It does not run multiple copies. It applies one transformation to one physical state, and that physical state happens to encode all exponents simultaneously. The output is therefore a superposition of all results simultaneously, each exponent now paired with its remainder. This is not a design choice or a clever trick. It is a consequence of quantum mechanics: the equations governing how qubits evolve are linear, meaning they process every branch of a superposition in a single application, the same way a single ocean wave passes through every slit in a barrier at once.

The popular phrase “a quantum computer tries all answers at once” points at this phenomenon but mischaracterizes it. The machine does not try anything. It applies a transformation to a physical state. What makes the state special is that it contains all inputs overlaid, and the linearity of physics carries them through together. What makes this useful is not that you get all outputs (you cannot read them), but that the outputs inherit the mathematical structure of the function, including its periodicity. And periodicity, as I have been saying, is the one thing we need.

If you could peek at this state (you cannot, and that matters), you would see something like a vast table: exponent 1 paired with remainder 2, exponent 2 paired with remainder 4, exponent 3 paired with remainder 8, exponent 4 paired with remainder 1, exponent 5 paired with remainder 2, exponent 6 paired with remainder 4, and on and on. The remainders repeat every 4 steps, because the loop length is 4.

Here is what matters: many different exponents produce the same remainder. Exponents 1, 5, 9, 13, 17… all produce remainder 2. Exponents 2, 6, 10, 14, 18… all produce remainder 4. Each group is a set of exponents spaced exactly 4 apart. That regular spacing, baked into the quantum state by the act of running the recipe, is the fingerprint of the loop length. The quantum state now has a repeating internal structure with period 4, whether N is 15 or a 600-digit number.

But I need to be precise about what “encoding the pattern” means, because this is the point where most popular explanations go wrong. The quantum computer does not store this table the way a spreadsheet stores a column of numbers. You cannot read the entries out. Measure the state and you get one random exponent-remainder pair, and the rest vanishes. This is not a limitation of current hardware. It is a law of physics.

What the quantum memory holds is the rhythm of the table, encoded in the internal mathematical structure (the amplitudes) of the quantum state. The rhythm can survive extraction. The individual entries cannot. And the rhythm is the loop length, the only thing we ever needed.

How the rhythm becomes readable

The rhythm is in the state, but it is not yet in a form you can measure. The exponents that share a remainder (1, 5, 9, 13…) are evenly spaced, but measuring the exponent register would just give you one of them at random. The number 9 by itself does not tell you the spacing is 4. You would need to measure many times and notice the pattern, and each measurement destroys the state, so you would need to re-run the entire circuit each time. That would work eventually, but it would be slow and wasteful.

The quantum Fourier transform is the step that converts the hidden spacing into a directly readable number, in a single shot.

Here is the intuition. Imagine each of those evenly spaced exponents (1, 5, 9, 13…) as a spike on a number line. You have a row of spikes, regularly spaced, like fence posts 4 apart. The QFT asks: “what is the spacing of these posts?” It answers this the same way a prism answers “what is the wavelength of this light?” by separating the signal into its frequency components.

After the QFT, the exponent register no longer holds exponents. It holds frequencies. And because the spikes were evenly spaced with period 4, the frequency register has high-probability outcomes at values that are multiples of 1/4 (scaled by the register size). Measure, and you get a number that encodes the spacing. One measurement, one answer, one run of the circuit.

The mechanism behind this conversion is quantum interference. The QFT applies a specific sequence of gates that causes the amplitudes of each possible outcome to be computed as a sum of contributions from all the fence-post spikes. At most frequency values, some contributions are positive and some are negative, and they cancel each other out (destructive interference). At the frequencies that match the spacing of the posts, all contributions point in the same direction and reinforce each other (constructive interference). The result is a state where the correct frequency has high probability and everything else has been suppressed.

From frequency to factors

A small amount of classical post-processing (a technique called continued fractions, which runs on a laptop in milliseconds) converts that raw frequency measurement into the exact loop length. From there, the 1970s mathematics takes over: compute the two halves, take the greatest common divisor with N, and the prime factors appear.

Sometimes the measurement gives a noisy result or a multiple of the true frequency. In that case you run the circuit again. A few repetitions are enough to recover the loop length with high confidence.

What the quantum computer actually contributes

The division of labor in Shor’s algorithm is lopsided and often misunderstood. A classical laptop picks the starting number, precomputes the multiplication constants, and decodes the final result. The quantum computer contributes one step: it performs the song and reports the pitch. One step, but it is the step that stayed impossible for fifty years.

Where the Gate Counts and Qubit Numbers Come From

This is the question I get asked most often, and the answer turns out to be surprisingly mechanical: the numbers come from counting, the same way an architect counts bricks from a blueprint before anyone breaks ground.

Counting steps (gates)

Shor’s algorithm, for RSA-2048, requires roughly 2,048 multiplications of 600-digit numbers. Each multiplication is built from additions, the same way you learned long multiplication in school: digit by digit, with carrying. Each addition of two 2,048-bit numbers takes about 2,048 elementary operations. And each elementary operation is a quantum gate, the atomic unit of a quantum circuit.

Multiply it out: approximately 2,048 multiplications, times approximately 2,048 additions per multiplication, times approximately 2,048 gates per addition. That comes to roughly 2,048^3, which is about 8.6 billion elementary operations.

That is a napkin calculation, and I want to be clear about what it is and is not. It explains why the answer is billions rather than millions or trillions: the cube of the key length sets the scale. But it is an intuition, not a derivation. A real resource estimate must account for which gate types are used (Toffoli gates cost far more than simple rotations), how arithmetic is designed for reversible quantum circuits, routing overhead from qubit connectivity, magic state production for non-Clifford gates, error correction costs, and the number of repeated shots needed. All of these materially change the bill.

The current leading estimate, Gidney’s May 2025 paper, gives precise numbers: approximately 6.5 billion Toffoli operations, 1,399 algorithmic logical qubits, an end-to-end layout below 1,600 logical patches, 897,864 physical qubits, and 4.96 expected days. These assume a specific hardware model (a square grid of superconducting qubits with 0.1% gate error rate, 1-microsecond surface code cycle time, and 10-microsecond reaction time). Change the assumptions and the numbers change. The napkin cube gives you the right order of magnitude; the published estimate gives you the engineering specification.

Counting workspace (logical qubits)

Gates tell you how long the job takes. Qubits tell you how much workspace you need to hold at the same time.

When you do long multiplication by hand, you need paper for the two numbers you are multiplying, the running total, and scratch space for carries. For 2,048-bit numbers, the textbook quantum circuit needs registers that wide, plus workspace: roughly three to five times the bit-width, or about 4,000 to 6,000 logical qubits. (“Logical” qubits are the dependable ones the recipe assumes. I will explain the undependable physical qubits in a moment.)

From logical qubits to physical qubits

Logical qubits are the workspace cells the algorithm needs. Physical qubits are what the machine is actually built from. The gap between them is the entire story of quantum error correction.

The best physical qubits today make a mistake roughly once in every 1,000 operations. Look back at the gate count: the recipe has billions of steps, and one wrong digit anywhere in the chain poisons the final answer. Each step must succeed with reliability better than one error in 10 billion tries. No physical qubit anywhere on Earth is that reliable. None is coming.

Engineers solve this with teamwork. Several hundred physical qubits are ganged together to act as one dependable logical qubit. They continuously cross-check each other. When one drifts, the group catches and repairs the error before it spreads. Think of a committee where any individual member might misremember a digit, but the group keeps comparing notes and the consensus stays right. The bigger the committee, the more reliable the group. The mathematics of error correction tells you exactly how big the committee needs to be to reach one-in-10-billion reliability from one-in-1,000 parts: depending on the hardware and the error correction code, roughly 500 to 1,500 physical qubits per logical qubit.

So the full calculation: about 1,400 logical qubits (in the most optimized current design) times roughly 700 physical qubits per logical qubit gives just under one million physical qubits. That is where the headline “under a million qubits” in Craig Gidney’s May 2025 paper comes from. One more layer of multiplication.

Runtime comes out the same way. Each logical step runs slowly because after every step the committee needs a moment to cross-check and repair. At tens of microseconds per step, billions of steps works out to a few days. Hence Gidney’s other headline: “under a week.”

How Researchers Shrink the Requirements Without Building Anything

If the basic arithmetic says we need 4,000 to 6,000 logical qubits and billions of gates, how did Gidney get down to about 1,400 logical qubits?

The answer is the same kind of engineering optimization you see in software: you can trade speed for memory, memory for speed, or find cleverer ways to reuse what you have.

The whiteboard trade

The oldest trick is workspace reuse. The textbook version of Shor’s algorithm keeps every intermediate result in memory simultaneously, which is like doing a long calculation with three separate whiteboards so you never have to erase anything. If you are willing to erase and rewrite, you can do the same calculation on a single, smaller whiteboard. The price is time: more erasing means more steps.

This is the core of Gidney’s 2025 construction. By scheduling calculations so that intermediate results are computed, used, and then deliberately un-computed (erased in a way that preserves quantum coherence), the workspace shrinks from roughly 6,000 logical qubits to about 1,400. The tradeoff is runtime. His earlier 2019 design with Martin Ekera, which used 20 million physical qubits and three separate “whiteboards,” needed about 8 hours. The leaner 2025 version needs days. Same calculation, different space-time tradeoff.

Approximate arithmetic

A second optimization accepts small rounding errors in intermediate calculations. In classical computing, you would never do this for cryptographic arithmetic because the final answer must be exact. In Shor’s algorithm, the situation is different: the quantum Fourier transform at the end is looking for the rhythm of the sequence, and small rounding errors in individual notes do not change the rhythm, the way a slightly out-of-tune guitar still plays a recognizable melody.

Gidney’s 2025 paper uses a technique from Chevignard, Fouque, and Schrottenloher (2024) that breaks modular multiplication into smaller operations on groups of digits, allowing individual steps to be approximate while the overall accuracy stays high enough for the quantum Fourier transform to read the correct loop length. This reduces the number of expensive quantum gates per multiplication.

Smarter error correction codes

The third lever is the error correction scheme itself. The exchange rate between logical and physical qubits depends on the code used. The standard construction, the surface code, is well understood and conservative, but it is not the only option. Newer codes like quantum low-density parity-check (qLDPC) codes promise more efficient encoding: the same reliability with fewer physical qubits per logical qubit. These are still early-stage, but recent theoretical constructions using qLDPC codes have pushed projected totals below 100,000 physical qubits for factoring RSA-2048.

Why the estimates keep falling

Each of these optimizations (workspace reuse, approximate arithmetic, better error correction codes) is an advance in circuit design. No quantum computer got bigger or better between the 2019 estimate and the 2025 estimate. Someone published a better blueprint, everyone recounted the bricks, and the new numbers replaced the old. The trajectory of resource estimates over the past decade is a story of algorithmic and engineering innovation.

The public tools for doing this counting are now freely available. Microsoft’s Azure Quantum Resource Estimator and Google’s Qualtran library both take an algorithm plus hardware assumptions and print the bill of materials: logical qubits, gate counts, estimated runtime, physical qubit overhead. In principle, anyone can run them and recount.

How to Spot the Papers That Are Faking It

In 2001, a team used an NMR quantum computer to factor 15 using Shor’s algorithm. Headlines celebrated. The result was genuine, as far as it went, but what happened next in the field was less honest.

The picture of what has actually been demonstrated is more layered than a single record number. A honest assessment requires a hierarchy.

At the bottom are fully compiled circuits, where knowledge of the answer was used to simplify the circuit until the multiplications disappeared. These are the subject of Smolin, Smith, and Vargo’s critique (discussed below) and Gutmann and Neuhaus’s abacus-and-dog replication. They tell you nothing about quantum factoring capability regardless of how large the number in the headline is.

In the middle is a recent and more interesting category: products of Fermat primes (numbers like 51, 85, 255, and 771). For these specially structured moduli, all multiplicative orders are powers of 2, and the multiplication constants simplify to identities or bit-shifts. The multiplications are genuine (not compiled away using foreknowledge of the factors), but they are structurally simple in ways that would never occur for a real RSA key. A June 2026 preprint by dos Santos et al. from Fluminense Federal University ran explicit modular-arithmetic circuits for these numbers on IBM superconducting hardware. For N up to 255, they recovered the correct order reliably (Hellinger fidelities up to 0.946). For N = 771, the signal degraded under accumulated hardware noise. The authors are transparent about the limitations: their paper states that their implementation “does not capture the full complexity of general modular exponentiation.” And the theoretical framework for these circuits, published by Geller and Zhou in 2013, includes an even sharper self-assessment: “we do not regard the factorization of products of Fermat primes to be genuine implementations of Shor’s algorithm.”

At the top, unambiguous: factoring a generic composite number with no structural shortcuts, where the multiplications are the full-cost modular arithmetic that a real RSA key would demand. By this standard, the record remains 15 or 21. (My article Quantum Computers Have Only Factored 15 and 21 covers the full history.)

The compiled-circuit shortcut

The bottom tier, the fully compiled circuits, was identified precisely in a 2013 paper by IBM researchers John Smolin, Graeme Smith, and Alex Vargo titled “Pretending to Factor Large Numbers on a Quantum Computer”. A compiled circuit is one where the designers used knowledge of the answer (the factors) to simplify the quantum circuit before running it. The multiplications, which are the entire reason the problem is hard, get replaced by trivial operations that only produce the right result for the specific number being factored.

Smolin, Smith, and Vargo demonstrated the absurdity by factoring arbitrarily large products of primes using just two qubits and a constant-time circuit. Their paper’s title was deliberate: you are not factoring; you are pretending.

The correct measure of difficulty, as their paper states, is not the size of the number factored but the length of the period found. And the connection between number size and period length is not gradual. Craig Gidney, the Google researcher behind the leading RSA-2048 resource estimates, explained on his blog in August 2025 why factoring 21 honestly costs more than 100 times what factoring 15 costs. The gap comes from three effects. When factoring 15 with starting number 2, six of the eight required multiplications are multiplications by 1, which cost nothing; for 21, none of the ten multiplications are trivial. Second, 15 is one less than a power of 2, so multiplying by 2 mod 15 reduces to a simple bit-shift, an operation that costs two swap gates. No such shortcut exists for 21. Third, the first multiplication in any run is cheap (its input is known to be 1), which saves a larger fraction of the total cost when the total is small.

Combined, these three effects mean the honest circuit for factoring 21 requires 2,405 entangling gates versus 21 for factoring 15. Add in the overhead of error correction (100 times more gates means you need 100 times lower error rates, which means more physical qubits per logical qubit), and the true cost gap approaches 10,000-fold.

How the cheating works in practice

The standard technique is to choose numbers whose prime factors differ by only a few bits. When the factors are close together, the period is short and predictable, and the circuit can be simplified to something trivial. As Peter Gutmann and Stephan Neuhaus put it in their 2025 paper “Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog”, these numbers would never appear in a real RSA key because the key generation process specifically requires the two primes to differ by at least 100 bits.

Their paper replicated or exceeded every published quantum factoring “record” using a VIC-20 (a 1981 home computer with 3.5 KB of RAM), an abacus, and a trained dog. The demonstration was intentionally absurd: they ranked the VIC-20 above the abacus, the abacus above the dog, and the dog above a quantum factoring physics experiment, in terms of demonstrated factoring capability. The point was to show that the claimed factoring achievements required no quantum capability at all, because the circuits used had been stripped of the operations that make factoring hard.

What to look for

When evaluating a claimed quantum factoring result, three questions expose the compiled-circuit shortcut.

Did the circuit perform the actual modular multiplications, or were they compiled away using knowledge of the factors? Were the multiplication operations replaced by trivial gates like a single controlled-NOT?

Was the number chosen to have factors that differ by only a few bits, making the problem artificially easy regardless of the number’s size?

Is the period being found trivially short (less than, say, 10), regardless of how large the number being factored appears?

If the answer to any of these is yes, the experiment is a period-finding demonstration on a trivially short period, dressed up with a large number to generate a headline. It tells you nothing about progress toward breaking RSA.

What This Means for Security

I have used RSA and factoring as the running example throughout this article because the mechanism is the most accessible. But Diffie-Hellman key exchange and elliptic curve cryptography (ECC) face the same class of threat through a related but distinct algorithm. RSA’s security rests on the difficulty of factoring. DH and ECC rest on the difficulty of computing discrete logarithms. Shor developed polynomial-time quantum algorithms for both problems, but they are separate reductions: breaking ECC is not “running the factoring algorithm on an elliptic curve.” The formal framework that unifies them is the Hidden Subgroup Problem, which shows that a fault-tolerant quantum computer capable of solving one possesses the fundamental machinery to threaten all three.

No quantum computer exists today that can run this algorithm against real cryptographic keys. The current factoring record on legitimate, uncompiled circuits remains in the double digits. But resource estimates have been falling, from 20 million physical qubits in 2019 to under one million in 2025, driven entirely by algorithmic and error-correction improvements. The hardware has not yet caught up, but the blueprint is getting cheaper every year.

Whether Q-Day is five years away, fifteen, or thirty, the migration to post-quantum cryptography needs to begin now. Not because the timeline is known, but because the deadlines are already set by regulators, insurers, investors, and clients, and because the Harvest Now, Decrypt Later threat means that data encrypted today is already at risk if it needs to stay confidential for longer than the time remaining before a cryptographically relevant quantum computer (CRQC) is built.

For the practical steps, see my Practical Steps to Quantum Readiness guide and the open-source Applied Quantum PQC Migration Framework.

What I Simplified

A few deliberate simplifications above, collected here for readers who want the precise version.

This entire article uses RSA and integer factoring as the running example. Shor developed a separate polynomial-time quantum algorithm for discrete logarithms, which is the problem underlying Diffie-Hellman and ECC. The two algorithms share the same quantum toolkit (phase estimation, the QFT), but the reduction from cryptographic problem to period-finding is different. Breaking ECC is not “running the factoring circuit on a different number.”

The “walking the track” metaphor for classical period-finding describes the naive approach and conveys the right intuition about why the problem is exponentially hard. In practice, classical cryptanalysts use far more sophisticated algorithms. The general number field sieve, for instance, factors numbers without finding periods at all, using algebraic number theory. Even these algorithms run in sub-exponential time and cannot touch RSA-2048 with any foreseeable resources. The precise claim is that no polynomial-time classical algorithm for factoring or general order-finding is known.

The “multiply and keep the remainder” recipe is modular exponentiation: computing a^x mod N. The loop length is the multiplicative order of a modulo N. The “two halves” step uses the factorization a^r – 1 = (a^(r/2) – 1)(a^(r/2) + 1) and computes gcd(a^(r/2) +/- 1, N). The requirement that the loop length be even (and that a^(r/2) not equal -1 mod N) is necessary; when it fails, you pick a different starting number. The probability of failure per trial is at most 1/2, so a few tries suffice.

My “ear” metaphor maps to the quantum Fourier transform (QFT), which converts periodicity in the computational basis into a frequency-domain representation. The measurement yields a value close to k/r (scaled by the register size), and the continued fractions algorithm recovers r from that value. Each run yields one sample; a few repetitions give high confidence.

As for the gate count, the 2,048^3 estimate omits constant factors, the overhead of performing arithmetic in superposition (controlled operations, ancilla management), and the difference between Toffoli gates and elementary two-qubit gates. Published resource estimates account for all of these, which is why they differ from the naive cube by a small multiplicative factor.

The “committee” analogy for error correction glosses over the fact that quantum error correction cannot inspect qubit values directly (the no-cloning theorem forbids copying an unknown quantum state). Surface codes use indirect measurements of stabilizer operators, syndrome extraction, and real-time decoding. The committee analogy captures the cooperative reliability mechanism but not the mechanism’s constraints.