For pen-and-paper arithmetic, what is the computational complexity of addition vs multiplication of two n-digit numbers, and why is that relevant to crypto?
Addition is O(n) — work scales linearly with digit count. Multiplication (long-form) is O(n²) — work scales quadratically. Both are polynomial. Factoring, however, is conjectured super-polynomial — exponentially harder than multiplication, which is exactly what makes RSA possible.
The pen-and-paper observation:
| Operation | 3-digit example | Work |
|---|---|---|
345 + 889 |
4 column additions (incl. carries) | ~n + 1 ops |
24 × 53 |
4 single-digit multiplications + 4 additions | ~n² ops |
So multiplication is n²/n = n times harder than addition for n-digit numbers. Still polynomial — completely tractable for modern computers even with thousand-digit numbers.
Factoring is on a different complexity tier entirely:
| Algorithm | Complexity for n-bit integer |
|---|---|
| Trial division | O(2^(n/2)) — exponential |
| Pollard's rho | O(2^(n/4)) — exponential, but faster than trial |
| Quadratic sieve | sub-exponential |
| General Number Field Sieve | sub-exponential (best classical, but still way more than polynomial) |
For a 3072-bit RSA key, GNFS needs roughly 2¹²⁸ operations — beyond anything any classical computer can do.
The cryptographic asymmetry:
- Defender (key generation, encryption, decryption) → polynomial-time operations only. Fast.
- Attacker (factor the public key) → super-polynomial. Infeasible.
Doubling the key size only doubles defender cost but raises attacker cost exponentially. That's why "use a longer key" is always the right response to "computers got faster."
Tip: This gap is what every PK system depends on. Quantum computers (Shor's algorithm) would also solve factoring in polynomial time, collapsing the gap — that's why post-quantum crypto is being deployed before quantum computers actually arrive.