No result has done for quantum computing what Shor's algorithm did. In 1994 it turned a speculation among physicists into a planetary security problem, showing that a sufficiently large quantum computer factors integers in polynomial time and therefore breaks RSA cryptography. This guide tackles the subject without sugar-coating and without alarmism. It covers the problem it solves, the mechanics of the reduction to period finding, the role of the quantum Fourier transform, realistic resource estimates for a real key, the state of experimental runs, the ‘harvest now, decrypt later’ threat and the defences already standardised, up to how to study it concretely in quantum emulation.
What is Shor's algorithm?
Shor's algorithm is a quantum procedure for factoring integers, published by Peter Shor in 1994 in the paper that founded quantum cryptanalysis, now freely readable on arXiv. Its running time grows polynomially with the number of digits of the integer to be factored, whereas the best known classical method, the number field sieve, grows superpolynomially. For keys of cryptographic size the gap becomes the one between hours and billions of years. It was the first demonstration that exponential quantum advantage exists on a problem of enormous practical value, and for this reason it remains the benchmark against which every other claim in the sector is measured. Thirty years on, when one wants to explain to a board of directors why quantum computing is not just basic research, one still starts from here.
What problem does it solve exactly?
Given a composite integer N, find a non-trivial factor of it. It looks like school arithmetic, but half a century of computer security rests on the difficulty of this problem for numbers of hundreds of digits. It must be stated precisely. Factoring has never been proven hard; it has merely withstood every known classical attack; Shor's algorithm therefore violates no theorem, but exploits a different model of computation in which the problem falls into a tractable class. The same scheme solves the discrete logarithm, which extends the threat from RSA cryptography to Diffie-Hellman and elliptic curves, that is, to practically all pre-quantum public-key cryptography. Symmetric cryptography such as AES and hash functions, on the other hand, remain beyond the reach of Shor's algorithm, and against them quantum computing offers at most Grover's quadratic advantage; there it is enough to lengthen the keys to restore the security margin.
Why does factoring threaten RSA cryptography?
RSA bases its security on an asymmetry. Multiplying two large primes is immediate; recovering the factors from the product is classically prohibitive. The public key contains the product N, and whoever could factor it would derive the private key, and with it the ability to decrypt every communication and to forge every signature. Shor's algorithm strikes exactly this asymmetry, and not with a negotiable margin. Doubling the key length, which is the classical defence against advances in attacks, increases the quantum cost only polynomially, that is, by little. There is no ‘long enough’ version of RSA cryptography that resists, so the answer must be a change of mathematics, as explained on the page on post-quantum cryptography.
What is the RSA public-key cryptosystem
RSA takes its name from its inventors Rivest, Shamir and Adleman, who published it in 1977, and is the most widely used public-key system in the world. It allows two parties to communicate in encrypted form without having first exchanged any secret, thanks to a pair of mathematically linked keys. With the public key, which can be distributed to anyone, one encrypts; with the private key, kept by the recipient alone, one decrypts; the inverse mechanism generates digital signatures. The pair arises from two very large prime numbers p and q, whose product n enters the public key. Encrypting means computing c = me mod n, decrypting means computing m = cd mod n, where the private exponent d is derived only by knowing p and q. All the security therefore lies in the difficulty of factoring n, the problem that Shor's algorithm makes tractable. In practice RSA protects the exchange of a disposable symmetric key, for example AES, with which the actual traffic is encrypted; this is the hybrid model behind HTTPS, VPNs, digital signatures and banking transactions, and it is the reason why the scope of the threat described on this page is so wide.
How does the reduction to period finding work?
The stroke of genius is classical before it is quantum. Choosing at random an integer a coprime to N, one considers the sequence of powers of a modulo N. This sequence is periodic, and number theory guarantees that from the period r, if even and ‘well-behaved’, factors of N are extracted with a greatest common divisor, an immediate computation. All the difficulty is therefore concentrated in finding r, a task in which classical methods become exponential again because the period can be enormous. And this is where the quantum comes into play. The function is evaluated in superposition over all exponents together, and the global periodicity becomes a property that can be extracted by interference, invisible to any local sampling. In other words, the quantum computer does not try the divisors one by one, but interrogates the hidden structure of the problem, which is exactly the kind of task in which this model of computation excels.
What role does the quantum Fourier transform play?
In-depth section for readers with a scientific background
Having prepared the state Σx|x⟩|ax mod N⟩ and measured the second register, the first collapses onto a superposition of only those exponents that share the same residue, a comb-like structure with spacing r. The quantum Fourier transform applied to this register concentrates the amplitude on the multiples of 2n/r, so the measurement returns a value from which the continued fractions algorithm recovers r with high probability. The QFT on n qubits costs O(n²) gates, and it is this efficiency that makes the entire scheme polynomial. The rest, controlled modular exponentiation included, is reversible arithmetic, laborious to implement but conceptually ordinary. Anyone who has followed this step holds the heart of the algorithm; the entire debate on resources, in the section that follows, concerns how much it costs to realise it on real hardware.
How many resources are needed to break RSA-2048?
The most cited estimates in the literature place the undertaking at the order of twenty thousand logical qubits with error correction, that is, with current codes and error rates, a few million physical qubits, for a run of hours. Today's processors count physical qubits in the order of thousands, noisy and uncorrected. Three orders of magnitude are missing and, above all, large-scale error correction is missing. The estimates fall with every algorithmic and engineering advance, and research is lively on this, but the numbers must be handled with rigour. Those who announce RSA broken tomorrow morning and those who declare it impossible forever are both wrong, and for the same reason, because they confuse the trajectory, which is clear, with the timing, which remains uncertain. For the decision-maker the number to remember is not a date, but a ratio. Roughly a thousand physical qubits per useful logical qubit are still needed, and it is that ratio, more than the total qubit count, that is the indicator to monitor in annual reports on the state of the hardware.
Has it ever actually been run?
Yes, on textbook numbers. The founding record is the factoring of 15 with nuclear magnetic resonance in 2001; 21 and a few other minimal integers followed on photons, ions and superconductors. They must be read for what they are, namely proofs of principle, often with simplified circuits that exploit advance knowledge of the answer, a compromise declared in the publications themselves. Periodically, announcements of ‘record factorisations’ circulate, obtained however with methods other than Shor, typically optimisation variants that do not scale; telling the two cases apart is the first test of competence in reading sector news. No honest and complete run of Shor's algorithm on a cryptographically interesting number has ever taken place, nor is one imminent. The value of these experiments is engineering, that is, verifying that every block of the chain works, not cryptanalytic. The gap with RSA-2048 remains the one described above.
What does ‘harvest now, decrypt later’ mean?
It is the reason why the problem is urgent today even though the hardware does not yet exist. A patient adversary can intercept and archive encrypted traffic now, at negligible storage cost, in order to decrypt it when the hardware is mature. Every piece of data whose confidentiality must last beyond the arrival horizon of quantum computing is therefore already at risk, today. For categories such as trade secrets, health data, diplomatic communications and intellectual property, the migration calendar is dictated not by the arrival of the machine but by the useful life of the data. It is the criterion by which security agencies and regulators, in Europe and the United States, have already set transition deadlines for critical infrastructure.
How to defend with post-quantum cryptography
The defence is not quantum but mathematical. It consists in replacing the vulnerable problems, factoring and the discrete logarithm, with problems for which no efficient quantum attacks are known, such as those on lattices. NIST standardised the first schemes in 2024, including ML-KEM for key exchange and ML-DSA for signatures, and migration has begun in network protocols and critical infrastructure. For an organisation the work is one of inventory and planning. One must map where vulnerable cryptography lives, often nested in suppliers, libraries and devices that no one has ever mapped, and sequence the replacement starting from long-lived data. Experience teaches that the inventory is the longest part of the path, and it is advisable to start it before regulatory deadlines turn it into an emergency. The subject falls fully within the perimeter of critical technologies.
How is Shor's algorithm studied in emulation?
In the most instructive way possible, that is, by running it in full on small numbers, with every register inspectable. In an emulation environment such as the EQM platform, one prepares the superposition of the exponents, literally watches the periodicity comb form in the register after the partial measurement, applies the Fourier transform and sees the amplitude concentrate on the right multiples. The logical chain stops being a narrative and becomes a reproducible experiment. It is also the bench on which the modern qubit-efficient variants are studied and the teams that will have to govern the cryptographic transition are trained, because understanding the attack is the first step in sizing the defence.
Understand the threat, size the defence
With HumanQ you run Shor's algorithm in emulation, train your team and assess your organisation's cryptographic exposure. Learn more about post-quantum cryptography, assess your quantum readiness or contact the HumanQ team.