Computational number theory

Computational number theory is the study of algorithms for solving problems in number theory — the branch of mathematics concerned with the properties and relationships of integers. Where classical number theory asks whether a property holds (are there infinitely many twin primes? is every even number greater than 2 the sum of two primes?), computational number theory asks how efficiently that property can be tested, verified, or exploited. It is the mathematical substrate on which modern cryptography rests: the security of RSA, Diffie-Hellman, and elliptic curve systems depends on the presumed computational difficulty of problems that computational number theory has spent decades mapping.

Core Problems and Their Complexity

The field is organized around a handful of canonical problems whose complexity status determines what cryptography can and cannot promise. Integer factorization — given a composite integer N, find its prime factors — is the problem that underpins RSA. Despite centuries of attention, no classical polynomial-time algorithm is known, and the best known method, the General Number Field Sieve, runs in sub-exponential time. This gap between polynomial and sub-exponential is the asymptotic boundary that makes RSA feasible: large enough to resist brute force, small enough to permit key generation and decryption.

The discrete logarithm problem — find x such that g^x ≡ h (mod p) — is structurally similar. It underpins Diffie-Hellman and elliptic curve cryptography, and like factoring, it resists polynomial-time classical attack. The presumed equivalence of factoring and discrete log (in the sense that a breakthrough in one might transfer to the other) has never been proven, but the cryptographic community treats them as siblings in hardness.

Primality testing stands in contrast. Where factorization is hard, determining whether a number is prime is easy — deterministic polynomial-time since the AKS primality test (2002). The asymmetry is striking: we can efficiently verify that a number is prime without being able to efficiently find its factors if it is composite. This asymmetry is not merely a technical curiosity. It is the reason RSA key generation is practical while RSA breaking is not.

The Quantum Inflection Point

Computational number theory was transformed in 1994 when Peter Shor showed that a quantum computer could factor integers and compute discrete logarithms in polynomial time. Shor's algorithm did not merely offer a speedup; it collapsed the complexity class of these problems from presumably