Factoring and RSA

Open a tab to https://www.sbi.co.in. Look at the little padlock icon next to the URL. Behind that padlock is a short handshake in which your browser and the State Bank of India server agree on a shared secret key, using only messages that any eavesdropper on the network can read. The trick that makes this possible — the thing that lets two strangers negotiate a secret in full public view — is public-key cryptography, and the most widely deployed version of it is RSA.

RSA is 47 years old. It is in your browser, in your UPI transactions, in the digital signatures on Aadhaar documents, in the PGP-signed firmware updates for your router, in the HTTPS certificate for every e-commerce site from Flipkart to the income tax portal. And its entire security rests on a single mathematical assumption: factoring a large integer into its prime factors is hard.

For forty-seven years, that assumption has held up. Every known classical algorithm for factoring takes sub-exponential time, which sounds fancy but in practice means "impractical at the key sizes people use." Then in 1994, a 35-year-old mathematician named Peter Shor walked into a Bell Labs seminar room and presented a quantum algorithm that factored integers in polynomial time. The algorithm does not yet run at scale — the quantum computers to execute it do not exist yet — but the mathematics is settled. On a large enough fault-tolerant quantum computer, RSA is dead.

This chapter is the setup for the next three, which build Shor's algorithm step by step. Here you see why factoring matters, how RSA uses it, what the classical cost is, and how far today's quantum hardware is from breaking it. The next chapter (ch. 75) shows the purely classical reduction from factoring to order-finding. The chapters after that (76, 77) show how quantum mechanics cracks the order-finding problem in polynomial time.

The puzzle that makes RSA work

Two operations sit at the heart of every cryptosystem: one that is easy, and one that is hard. For RSA, those are multiplication and factoring.

Multiplying two 1024-bit primes together takes a laptop microseconds. Going the other way — given just the 2048-bit product, recovering the two primes that made it — takes the largest supercomputer on Earth decades. This asymmetry is what is called a trapdoor function: easy forward, hard backward, unless you hold a secret piece of information that unlocks the backward direction.

You can sense the asymmetry with a small example. Multiply 101 \times 103 in your head; you probably get 10403 in a few seconds. Now do it backwards: somebody gives you 10403 and asks for its two prime factors. You would try dividing by 2, 3, 5, 7, 11, \ldots until something clicked — and even at this trivial scale, that is tedious. Now scale: instead of 10403, imagine the other person hands you a 617-digit number (that is what 2048 bits looks like in decimal). The same "try one prime at a time" strategy has to check about 2^{1024} primes, which is more atoms than the observable universe contains. That is the wall RSA hides behind.

RSA uses this gap to let a server publish a number anyone can encrypt with, while keeping a related number secret that only the server can decrypt with.

How RSA actually works

You do not need the full security proof to understand what RSA is doing. Five lines of arithmetic, done once at the server, set up the whole system.

Setup. You are a server preparing to receive encrypted messages.

1. Pick two large primes p and q. (In practice, each is 1024 bits, so p, q are each roughly 10^{308}.)
2. Compute N = pq. This is your public modulus.
3. Compute \varphi(N) = (p-1)(q-1), the Euler totient of N. Why this particular number: \varphi(N) counts integers in \{1, 2, \ldots, N\} that share no common factor with N. The next step uses a classical theorem (Fermat–Euler) that says a^{\varphi(N)} \equiv 1 \pmod N for any a coprime to N — and this is exactly what makes encryption reversible.
4. Pick e coprime to \varphi(N). A common choice is e = 65537. This is the public exponent.
5. Compute d such that e \cdot d \equiv 1 \pmod{\varphi(N)}. This d is the private exponent.

Publish. The public key is the pair (N, e). Anyone can see it. Put it on a web page.

Keep secret. The private key is d (or equivalently, p and q, from which d can be recomputed). Keep it on your server. Never send it over the network.

Encrypt. To send you a message m (an integer between 0 and N-1), anyone computes

and sends you c.

Decrypt. You compute

which, by the magic of the e and d exponents cancelling modulo \varphi(N), gives back exactly the original m.

The two modular exponentiations — m^e and c^d — can both be computed efficiently using repeated squaring, even for 2048-bit numbers. A laptop does them in milliseconds.

Where the security lives. The public key publishes N and e. If an eavesdropper could compute d from (N, e), they could decrypt any message. But computing d requires knowing \varphi(N) = (p-1)(q-1), which requires knowing p and q — which requires factoring N. That is the whole security argument, in one line. Break factoring and you break RSA. Nothing else in the scheme matters.

The classical cost of factoring

How hard is factoring, really? The honest answer is "sub-exponential, but not by as much as you might hope."

Write N in binary — it takes n bits, where n = \log_2 N. For 2048-bit RSA, n = 2048. The cost of the best-known classical factoring algorithms grows with n in four broad tiers.

Trial division. Divide N by every integer from 2 up to \sqrt N, checking for zero remainder. Cost: O(\sqrt N) = O(2^{n/2}). At n = 2048, that is 2^{1024} operations — beyond any possible computer, ever.

Pollard's rho method. A clever random-walk trick, discovered in 1975. Cost: O(N^{1/4}) = O(2^{n/4}). Still exponential in n. At n = 2048, 2^{512} operations — still impossible.

Quadratic sieve. A 1981 idea: look for pairs of numbers whose squares are congruent modulo N, extract a factor from their difference. Cost: \exp\!\bigl(O(\sqrt{n \log n})\bigr). Sub-exponential — meaning the exponent grows slower than n — but still much worse than polynomial. Practical up to maybe 400-bit N.

General Number Field Sieve (GNFS). The current champion, refined through the 1990s and 2000s. Cost:

Why this notation: the L_N[\alpha, c] form is the standard way to write sub-exponential complexities. When \alpha = 1 you recover exponential; when \alpha = 0 you recover polynomial. GNFS sits at \alpha = 1/3, closer to polynomial than to exponential but still not polynomial. No classical algorithm is known with \alpha < 1/3.

Plug in n = 2048 and GNFS comes out at roughly 2^{112} operations. For context, the entire Bitcoin network performs around 2^{90} hashes per year. 2^{112} is about four thousand times that, sustained for a year — nothing any adversary on the planet can afford today, and nothing that is getting cheap soon.

Why the jumps look like \sim 20 bits of work per doubling of key size: GNFS cost scales as \exp(c \cdot n^{1/3} \cdot (\log n)^{2/3}), so doubling n multiplies the cost exponent by roughly 2^{1/3} \approx 1.26. That is why going from 1024 to 2048 bits adds only about 22 bits of work to the attacker — it buys you security margin but not infinity.

Two lessons fall out. First, RSA-2048 is secure against every classical attacker you can imagine — governments, intelligence agencies, organised crime, well-funded academics. That is the foundation on which banking, e-commerce, Aadhaar and UPI sit. Second, RSA-2048's margin is not arbitrarily large: GNFS's cost grows as 2^{n^{1/3}} rather than 2^n, so if tomorrow someone found a classical algorithm with a 2^{n^{1/4}} scaling, the security of 2048-bit keys would evaporate overnight. The assumption that no such algorithm exists is a belief, supported by forty years of unsuccessful attack but never proved.

A toy worked example — RSA with N = 15

RSA is not an abstract protocol. You can run it with your head and a pen. The key sizes are unrealistically tiny, but every arithmetic step is identical to the real thing.

What the quantum threat actually looks like

So Shor's algorithm factors in polynomial time. Is RSA broken?

Not today. The honest picture needs two numbers.

What quantum computers can factor today (April 2026): small numbers with extra structure, using demonstrations rather than serious Shor implementations. The largest number Shor's algorithm has been used to factor without compiling shortcuts is 21 = 3 \times 7, demonstrated on trapped-ion and superconducting hardware around 2012. Larger demonstrations (numbers up to 10^{15}) have used heavily-optimised "compilation" that hard-codes parts of the answer into the circuit — impressive engineering but not a genuine factoring algorithm.

What quantum computers need to factor RSA-2048: estimates vary with error-correction scheme, but the widely-cited 2021 analysis of Gidney and Ekerå [2] puts it at roughly 20 million physical qubits running for about 8 hours, assuming surface-code error correction at reasonable gate-error rates. A 2019 Google/Delft analysis gave a similar ballpark.

What quantum computers have today (2026): IBM's Condor (2023) reached 1121 physical qubits. IBM's Heron (2024) had 156 qubits but with far better fidelity. Google's Willow (2024) had 105 qubits with unprecedented error rates. The leaders all have circuit depths and error rates that remain far short of what Shor at 2048 bits would need.

The gap between 1121 physical qubits (today) and 20 million (needed) is about four orders of magnitude. At historical rates of qubit-count doubling (~1.5 years), that is roughly 20 years. At optimistic projections, 10 years. At pessimistic projections, never, because error-correction overhead scales badly and the physics gets harder as systems get larger. The NIST-standardised cryptographers' working estimate, calibrated against all public data, is that RSA-2048 becomes vulnerable somewhere between 2035 and 2045 — if all goes well for the quantum engineers.

Hype check. You will read press articles claiming quantum computers will "break RSA this year" or that banks are "weeks away from collapse." They are selling ad impressions. The timeline above is the honest one. The qubit counts you see today are physical, mostly noisy, only weakly error-corrected, and not remotely close to what Shor at 2048 bits requires. What the threat does require, urgently, is migration to post-quantum cryptography — because encrypted data intercepted today can be stored and decrypted later, the day quantum Shor comes online ("harvest now, decrypt later"). The policy case for migration is solid; the apocalyptic timeline is not.

Indian stakes — Aadhaar, UPI, banking

The Unique Identification Authority of India uses RSA-2048 signatures for every Aadhaar authentication. Every time you authenticate at a ration shop, a bank, a mobile shop — that transaction carries an RSA-signed payload from UIDAI servers. The biometric templates themselves are encrypted in transit with the same family of primitives.

UPI — which processed over 17 billion transactions in March 2026 — signs transaction messages with RSA or ECC (Elliptic Curve Cryptography, which Shor also breaks). Every Google Pay, PhonePe, BHIM tap relies on this.

The Reserve Bank of India's RTGS and NEFT settlement systems use RSA-signed certificates for inter-bank communication. The National Stock Exchange uses RSA for member authentication.

A working Shor's-algorithm-capable quantum computer would force India to migrate all of these to post-quantum primitives. The migration is a multi-year project across tens of thousands of endpoints. The National Quantum Mission (2023, ₹6003 crore over 8 years) includes a dedicated pillar on post-quantum cryptography, co-ordinating between UIDAI, NPCI, SEBI and RBI. The Indian standards body, the Bureau of Indian Standards, is working with NIST on aligning the Indian PQC recommendations with the international standards.

Post-quantum cryptography — what will replace RSA

Shor's algorithm breaks RSA, ECC, and Diffie-Hellman — all the public-key primitives whose security rests on factoring or discrete logarithm. It does not break cryptosystems whose security rests on other hard problems. A whole research programme, post-quantum cryptography, has been building alternatives since the early 2000s.

The main families:

• Lattice-based cryptography. Security based on problems like Learning With Errors (LWE) or Ring-LWE — roughly, "find a short vector in a high-dimensional lattice." Best-understood lattice algorithms are exponential in the dimension, and no known quantum speedup changes this. CRYSTALS-Kyber (for key exchange) and CRYSTALS-Dilithium (for signatures) are lattice schemes that NIST standardised in August 2024 as the primary post-quantum replacements for RSA and ECC.
• Hash-based cryptography. Signatures built entirely from a hash function — their security inherits directly from the collision-resistance of the hash. Quantum attacks give only a \sqrt N speedup (via Grover) which is handled by doubling the hash output. SPHINCS+ is the NIST-standardised hash-based signature scheme.
• Code-based cryptography. Security based on decoding a random linear code — hard classically and quantumly. Dates back to the 1970s. Classic McEliece is a NIST alternate-standard candidate.
• Isogeny-based cryptography. Security based on finding isogenies between elliptic curves. Was a candidate, but the front-runner (SIKE) was broken classically in 2022 by Wouter Castryck and Thomas Decru — a reminder that "post-quantum" does not mean "forever safe."

India's National Quantum Mission cryptography working group has committed to adopting NIST's standardised lattice schemes as the migration target. The timeline laid out in the Digital India documents aims for pilot PQC deployment in Aadhaar and UPI by 2028, with full migration by 2035. That is a big engineering project — every TLS server, every signed Aadhaar payload, every UPI app needs to be re-issued with new primitives, and rollback compatibility has to be maintained for years. The earlier you start, the more manageable it is.

Common confusions

• "RSA will be broken tomorrow because somebody demonstrated Shor's algorithm." Today's demonstrations factor 15 and 21 with the answer essentially pre-compiled into the circuit. The gap to RSA-2048 is four orders of magnitude in qubit count and far more in fidelity. The timeline is 10–20 years, not tomorrow.
• "Any quantum computer breaks RSA." Only a fault-tolerant quantum computer with millions of physical qubits. NISQ-era machines, including those with hundreds of noisy qubits, cannot run Shor at cryptographically relevant sizes — the error-corrected circuit depth required exceeds what NISQ error rates permit by many orders of magnitude.
• "Post-quantum cryptography is ready, so migration is easy." The primitives are ready — NIST standardised four schemes in 2024. Deploying them across the tens of thousands of endpoints in Aadhaar, UPI, banking, and internet infrastructure is not easy. It took a decade to migrate from SHA-1 to SHA-256, and that was a hash function change, not a full primitive swap. PQC migration is larger.
• "Shor's algorithm breaks all encryption." Only public-key cryptosystems based on factoring, discrete logarithm, or elliptic-curve discrete logarithm. Symmetric encryption (AES) is merely weakened by Grover's O(\sqrt N) speedup — doubling the key length restores the security level. AES-256 remains quantum-secure; AES-128 becomes AES-64-equivalent and must be upgraded.
• "RSA's security is proved." It is not. The assumption "factoring is hard classically" is unproven. The best classical algorithm is GNFS at sub-exponential cost, but there is no proof that no better classical algorithm exists. Shor proved that a polynomial-time algorithm exists quantumly. A polynomial-time classical algorithm for factoring would shock the world but is not ruled out.

Going deeper

The General Number Field Sieve in one paragraph

GNFS works in three phases. Relation collection: search for pairs (a, b) such that a + b\alpha (in a number field defined by a carefully chosen polynomial) and a + b m (in the integers, for a specific m) both factor into small primes — "smooth" numbers. Linear algebra: assemble the smooth factorisations into a huge sparse matrix over \mathbb{F}_2 and find a null vector, which corresponds to a congruence X^2 \equiv Y^2 \pmod N. Square-root and gcd: compute \gcd(X - Y, N), which is a non-trivial factor of N with high probability. The bottleneck is relation collection, which is heavily parallelisable (factors of RSA-768 were collected on a distributed network), and the linear algebra, which needs many terabytes of RAM. No known improvement to GNFS has beaten the L_N[1/3, (64/9)^{1/3}] complexity in over thirty years of research.

Lattice-based cryptography — why Shor can't break it

Lattice cryptography is built on the Learning With Errors (LWE) problem. Given a matrix A and a vector b = As + e where s is a short secret and e is a small noise vector, recover s. The classical difficulty comes from the noise: without noise, this is a linear system you can solve in polynomial time by Gaussian elimination; with noise, the best algorithms take 2^{O(n)} time where n is the lattice dimension.

Shor's algorithm exploits the periodic structure of modular exponentiation — specifically that a^{k+r} \equiv a^k \pmod N. Lattices have no such clean periodicity; the shortest-vector problem and learning-with-errors have rich algebraic structure but not a single global period that a quantum Fourier transform could pick out. Known quantum algorithms for lattice problems give at most polynomial speedup, not exponential — which is why lattice-based schemes are the presumed replacement for RSA.

The standardised scheme CRYSTALS-Kyber uses Module-LWE, a variant of LWE over polynomial rings, with recommended parameters at n = 256 and module dimension 3. At these parameters, the security level is estimated at 256 bits of quantum security — meaning even a full-scale quantum computer needs 2^{256} operations to break it.

Harvest now, decrypt later

The most immediate reason PQC migration cannot wait is harvest-now-decrypt-later. Adversaries with network access — state-level intelligence agencies, primarily — can intercept encrypted traffic today, store it, and decrypt it when a Shor-capable quantum computer comes online. For data with long-term value — Aadhaar biometrics, medical records, state secrets, patent-pending research — the timeline that matters is not "when does Shor exist" but "when does the data become worthless." If your data is still sensitive in 2040, encrypting it with RSA today is equivalent to posting it on a bulletin board that becomes readable in 2040.

This is why the US Office of Management and Budget issued a 2022 memorandum requiring all federal systems to migrate to PQC by 2035, and why India's NQM cryptography working group is pushing similar timelines. The NSA's 2022 "Commercial National Security Algorithm Suite 2.0" already requires PQC transition for classified systems.

NIST's post-quantum standardisation — 2016 to 2024

In December 2016, NIST launched a public competition for post-quantum cryptographic standards. Over eight years and four rounds, 69 submitted candidates were winnowed down. In 2022, NIST selected CRYSTALS-Kyber (key encapsulation), CRYSTALS-Dilithium (signatures), FALCON (signatures), and SPHINCS+ (hash-based signatures) as the initial winners. The formal standards were published in August 2024 as FIPS 203 (Kyber → ML-KEM), FIPS 204 (Dilithium → ML-DSA), and FIPS 205 (SPHINCS+ → SLH-DSA).

In July 2022, during round 4, one of the alternate candidates — SIKE, an isogeny-based scheme — was broken classically in under an hour on a laptop by Wouter Castryck and Thomas Decru. This was a cautionary tale: "post-quantum" does not guarantee "secure against all classical attacks," and the standardisation process includes continuous review.

India's National Quantum Mission and PQC

The NQM was approved in April 2023 with a budget of ₹6003 crore over 2023–2031. Its four Thematic Hubs cover quantum computing, quantum communication, quantum sensing, and quantum materials. Within communication, a dedicated PQC working group is tasked with:

• Evaluating NIST-standardised primitives for Indian deployment.
• Pilot-deploying hybrid schemes (classical + PQC) in UIDAI's Aadhaar signing infrastructure.
• Coordinating with RBI, NPCI, SEBI on banking and exchange migration.
• Collaborating with the Centre for Development of Advanced Computing (C-DAC) on Indian PQC libraries.

The leading Indian academic centres — IIT Madras, IISc Bangalore, IIT Delhi, IIT Bombay, TIFR — have active cryptography groups contributing to both attack-side (lattice reduction) and defence-side (new scheme proposals) research. The Indian standards body (BIS) is tracking NIST alignment and preparing IS:xxx:202x standards for PQC primitives in Indian systems.

Where this leads next

• Factoring Reduces to Order Finding — the classical number-theoretic reduction that lets order-finding factor any RSA modulus.
• Order Finding — The Quantum Idea — how quantum phase estimation extracts the multiplicative order of a mod N.
• The Shor Circuit End to End — the complete quantum circuit that factors N, with all subroutines visible.
• Post-Quantum Cryptography — lattice, code-based, and hash-based alternatives to RSA.
• BB84 Quantum Key Distribution — the quantum-native alternative to RSA-based key exchange, based on the physics of measurement rather than computational hardness.

References

1. Rivest, Shamir, and Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (1978) — the original RSA paper. Summary at Wikipedia.
2. Craig Gidney and Martin Ekerå, How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) — arXiv:1905.09749.
3. Wikipedia, General number field sieve.
4. NIST Post-Quantum Cryptography Standardization — csrc.nist.gov/projects/post-quantum-cryptography.
5. Michele Mosca, Cybersecurity in an era with quantum computers: will we be ready? (2015) — arXiv:1512.00039.
6. John Preskill, Lecture Notes on Quantum Computation, Chapter 6 — factoring and Shor's algorithm — theory.caltech.edu/~preskill/ph229.