The Algorithm With Your Encryption's Name On It — How Shor's Algorithm Breaks RSA
Part 2 of “Quantum, explained simply” — but slightly deeper insight for decision-makers who want the real picture, not the hype. By Amit Agarwal, CEO & Co-Founder, SeQure AG.
In the first article we saw how a quantum computer computes — by orchestrating interference so that wrong answers cancel and the right one survives. That sounds abstract until you point it at the one mathematical problem on which much of the world's secure communication quietly rests. Then it becomes the most consequential algorithm in cryptography. This piece explains, with the mathematics kept in optional boxes, exactly how Peter Shor's 1994 algorithm dismantles RSA — and, just as importantly, how far off that day actually is.
What RSA actually relies on
RSA — named for Rivest, Shamir and Adleman, who published it in 1978 — is the archetypal public-key cipher. Its elegance is a deliberate asymmetry: anyone can lock a message using a public key, but only the holder of the private key can unlock it. That asymmetry rests on a single piece of arithmetic that is easy in one direction and brutally hard in the other. Multiplying two large prime numbers together is trivial; taking the resulting product and recovering the original primes — factoring — is, for a classical computer, effectively impossible at the sizes used in practice. For example, RSA-2048 relies on finding the two prime factors of a massive 2048-bit (617 decimal digits) number. The fastest supercomputer today is estimated to need billions to trillions of years to break it. Therefore, it ensured security for financial transactions as it was simply not worth trying to break this.
|
The mathematics Choose two large primes p and q, and form the modulus and totient: N = p · q φ(N) = (p − 1)(q − 1) The public key is (N, e); the private key is d, chosen so that e · d ≡ 1 (mod φ(N)). Encryption and decryption are simple modular exponentiations: c = me mod N m = cd mod N The crucial point: recovering the private d from the public (N, e) requires knowing φ(N), and knowing φ(N) is equivalent to factoring N. Factor N and the whole cipher falls open.
Figure 1. RSA's security is a one-way street: easy to walk forwards, effectively impassable in reverse — for a classical computer. |
Why factoring is hard — for a classical computer
"Effectively impossible" deserves to be made precise, because precision is the whole point. The best classical factoring method we know, the General Number Field Sieve, does not run in time proportional to the size of the number; it runs in sub-exponential time — far better than trying every divisor, but far worse than the polynomial time that makes a problem genuinely tractable. For a 2048-bit modulus, that gap is the difference between an afternoon and a span longer than the age of the universe.
|
The mathematics The General Number Field Sieve factors an integer N in heuristic time exp ((c + o(1)) · (ln N)1/3 · (ln ln N)2/3), c = (64/9)1/3 ≈ 1.923 This is sub-exponential but super-polynomial. Doubling the key size does not double the work — it multiplies it many times over. That single fact is what has kept RSA standing for nearly half a century. |
Shor's sideways move: don't factor, find a period
Here is the part most accounts skip, and it is the most beautiful idea in the whole subject. Shor did not teach a quantum computer to factor head-on; hunting for prime factors directly is hard even for a quantum machine. His move was lateral. He proved that factoring is secretly the same problem as finding a hidden repetition — a "period" — in a simple arithmetic sequence. And finding hidden periods turns out to be precisely the kind of task at which quantum interference excels.
The bridge is pure, classical number theory, known since Euler. Pick a random number “a” below N. Look at its powers modulo N — a, a², a³, … — and they eventually cycle back to 1. The length of that cycle is the period, r. Once you know r, ordinary arithmetic (a greatest-common-divisor computation) hands you a factor of N with high probability. The entire difficulty has been relocated to one question: what is the period r?
|
The mathematics To factor N: choose a random a with 1 < a < N and gcd(a, N) = 1. Find the order r — the smallest positive integer with ar ≡ 1 (mod N) If r is even and ar/2 ≢ −1 (mod N), then a nontrivial factor of N is recovered by gcd(ar/2 − 1, N) and gcd(ar/2 + 1, N) For a randomly chosen a, those two conditions hold often enough that a few attempts succeed with overwhelming probability.
Figure 2. The reframing that makes everything possible: factoring becomes period-finding, and only the middle step needs a quantum computer. |
How the quantum computer finds the period
This is where the machinery of the first article does its work. The quantum computer prepares a superposition over a huge range of exponents x, and computes ax mod N for all of them at once, holding the results in superposition. By itself that is useless — measure it and you get one random value. The genius is the next step: the Quantum Fourier Transform, a quantum operation that is exquisitely sensitive to periodicity. It arranges the amplitudes so that they reinforce at values related to the period and cancel everywhere else. Measure now and the outcome is no longer random — it points, sharply, at the period.
|
The mathematics Over a register of size Q = 2n (taken larger than N²), the Quantum Fourier Transform acts as QFT |x⟩ = (1/√Q) Σy=0 Q−1 e2πi·xy/Q |y⟩ Applied to the periodic state, measurement returns a value y close to an integer multiple of Q/r. A continued-fraction expansion of y/Q then recovers r. The quantum stage runs in time polynomial in the number of digits — the exponential barrier is gone.
Figure 3. A concrete case (a = 7, N = 15, period r = 4): the QFT converts a hidden repetition into sharp, readable peaks. This is interference, put to work. |
It is not only RSA
It would be comforting to think RSA is a single vulnerable cipher we could simply swap out for another of the same family. It is not. Shor's 1997 paper solved two problems, not one: factoring and the discrete logarithm. The discrete logarithm is the hardness assumption beneath Diffie–Hellman key exchange and elliptic-curve cryptography (ECC) — the other pillars of today's public-key infrastructure. A large enough quantum computer running Shor's algorithm therefore threatens essentially the entire classical public-key edifice at once: the key exchanges that protect data in transit, the digital signatures that authenticate software and payments, the certificates that underpin trust on the web. Symmetric encryption such as AES is a different and far more resilient story — the subject of the next article — but public-key cryptography, as a class, is the exposed flank.
So how far off is it?
This is where responsible analysis parts company with headlines. Shor's algorithm is mathematically complete and not in dispute. What does not yet exist is a quantum computer large and stable enough to run it on a 2048-bit key. Such a machine requires not a few hundred fragile physical qubits — roughly where today's hardware sits — but a fault-tolerant machine with extensive error correction. Published resource estimates give a sense of the distance, and of how quickly the estimates are falling: in 2021, Gidney and Ekerå estimated around twenty million noisy physical qubits to factor RSA-2048 in eight hours; by 2025, a further result brought that figure below one million. These are research estimates of what would be required — not announcements that the machine has been built.
|
THE MATHEMATICS
Figure 4. The estimated cost of breaking RSA-2048 is dropping sharply — but the machine still does not exist. The trend, not any single date, is the signal. |
Two conclusions follow, and they must be held together. First, "Q-Day" — the day this becomes practical — is genuinely uncertain; it is a forecast with a range, not a date on the calendar, and anyone who quotes you a precise year is selling certainty that does not exist. On the other hand, companies like IBM and IonQ have accelerated their roadmaps for stable large-number qubit machines by few years. Second, and less comfortably, the uncertainty does not buy as much time as it appears to. Encrypted data captured and stored today can be decrypted the moment a capable machine arrives — the HNDL or "harvest now, decrypt later" threat. For information that must stay confidential for a decade or more, which describes a great deal of what a bank holds, the relevant clock is not when Q-Day arrives, but how long your data must remain secret, set against how long migration will take.
What replaces RSA
The reassuring part is that the destination already exists. In 2024 the US National Institute of Standards and Technology finalised the first post-quantum cryptographic standards — FIPS 203, 204 and 205 (ML-KEM, ML-DSA and SLH-DSA) — algorithms built on mathematical problems for which no efficient quantum attack is known. The work ahead is not inventing a replacement; it is the considerable engineering task of finding every place where public-key cryptography is used across a complex estate and migrating it, in order of exposure, before it matters. The work does not stop there. It continues in building cryptographic agility in operations to ensure similar future threats can be addressed efficiently and in a timely manner. For the times until Quantum computing reaches its full promise and to make the transition smoother, hybrid solutions of classical and/or PQC algorithms is the most sensible way forward.
The takeaway
Shor's algorithm is a masterpiece of redirection: it does not break RSA by brute force but by translating an impossible problem into one a quantum computer can solve. That same lesson — that quantum advantage comes from reformulation, not raw speed — runs through this entire series. For a financial institution, the practical implication is calm and specific: the threat to public-key cryptography is real and well understood, its timing is uncertain but its preparation is not optional, and the institutions that fare best will be those that mapped their exposure early. At SeQure AG we help banks do exactly that mapping; but the mathematics above stands on its own, and it is worth understanding before the headlines next insist the sky is falling tomorrow.
——————————————————————————————
References
1. P. W. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer," SIAM Journal on Computing 26(5), 1484–1509 (1997) — originally in Proc. 35th IEEE FOCS (1994).
2. R. L. Rivest, A. Shamir and L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Communications of the ACM 21(2), 120–126 (1978).
3. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press (2010) — for the Quantum Fourier Transform and order-finding.
4. C. Gidney and M. Ekerå, "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits," Quantum 5, 433 (2021).
5. C. Gidney, "How to factor 2048 bit RSA integers with less than a million noisy qubits," arXiv:2505.15917 (2025) — preprint; cited as a resource estimate, not a deployed result.
6. NIST, FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), FIPS 205 (SLH-DSA), finalised 2024 — the post-quantum replacements.
About the author. Amit Agarwal is CEO and Co-Founder of SeQure AG, a Swiss quantum cybersecurity company helping banks and financial institutions identify, prioritise, and remediate cryptographic vulnerabilities before Q-Day. He brings 25+ years across software, SaaS, payments and FinTech and holds a BTech (Computer Science), an MBA, an MAS, and a Quantum Computing qualification from MIT's executive education.
Comments