Computational Number Theory

Computational number theory is the branch of number theory that asks how to actually do arithmetic—to factor a given large integer, to test whether it is prime, to find the rational points on a curve, to compute a class group—and to do it fast enough, and with guarantees reliable enough, to be useful.

12 frameworks, from 300 BCE to today · Number Theory · Mathematics

still a working view ended · each leads to its entry below

Overview

Computational number theory is the branch of number theory that asks how to actually do arithmetic—to factor a given large integer, to test whether it is prime, to find the rational points on a curve, to compute a class group—and to do it fast enough, and with guarantees reliable enough, to be useful1. Its organizing questions are algorithmic: not only is there a solution, but can we find it, how quickly, and with what evidence do we know we have it. This makes it distinct from number theory pursued purely for proof. A theorem that a number has a property is one thing; an algorithm that returns the number, or a certificate that it lacks the property, is another. The field matters because the integers are the raw material of cryptography, of computer algebra, and increasingly of large-scale experiment in mathematics itself1. Its history is the story of how pencil-and-paper methods were turned into procedures a machine could run, and how the demands of machines—speed, memory, certainty—reshaped what number theorists tried to prove.

Classical algorithms before machines

Long before electronic computers, number theory was full of procedures. Euclid's algorithm for the greatest common divisor, described in the Elements around 300 BCE, is the oldest nontrivial algorithm still in daily use; its efficiency (the number of steps grows only logarithmically with the size of the inputs) was analyzed in the nineteenth century. The Chinese remainder theorem, known in China by the third century CE and systematized in later commentaries, gives a way to reconstruct a number from its remainders modulo several moduli. Sieve methods for finding primes—the sieve of Eratosthenes from antiquity—are algorithms in the plainest sense2.

The early modern period added methods that would later become computational workhorses. Pierre de Fermat's "little theorem" (that \(a^{p-1} \equiv 1 \pmod p\) for prime \(p\) not dividing \(a\)) gave, in principle, a test for primality. Leonhard Euler extended it to the totient function and to quadratic reciprocity, and Carl Friedrich Gauss's Disquisitiones Arithmeticae (1801) organized congruence arithmetic into a system with explicit computational techniques, including the reduction of binary quadratic forms. Gauss also concerned himself, in his astronomical work, with efficient computation of the orbit of Ceres—an early demonstration that numerical and arithmetic techniques were intertwined.

Through the nineteenth and early twentieth centuries these methods remained hand computations. Tables of primes, of factorizations, and of class numbers were laboriously compiled. The mathematical question of how hard a computation is—its intrinsic difficulty rather than its execution time on a given person—was not yet sharply posed.

The computer arrives and primality testing crystallizes

Electronic computers after the Second World War turned these classical procedures into research programs. The first target was primality. A naive test divides by every integer up to the square root; that becomes hopeless quickly3. Fermat's test fails on pseudoprimes—composite numbers that nonetheless satisfy the congruence—so certainty requires more.

A decisive step came from the work of Derrick Henry Lehmer and others on deterministic tests, and then from the discovery (published in the 1970s and 1980s, associated with Leonard Adleman, Robert Rumely, Carl Pomerance, and others) of progressively faster deterministic algorithms. The culmination for many years was the Adleman–Pomerance–Rumely test (1983), which could prove primality in time roughly \((\log n)^{c \log \log \log n}\)—subexponential, though still not polynomial. Then in 2002 Manindra Agrawal, Neeraj Kayal, and Nitin Saxena announced the AKS test, the first deterministic primality test running in polynomial time, a purely theoretical landmark that settled the complexity class of primality (it lies in P) even though in practice it is slower than the alternatives it displaced. The theoretical resolution and the practical winner are often different algorithms—a recurring theme.

Probabilistic algorithms and the factorization problem

The 1970s and 1980s transformed the field by embracing randomization. A probabilistic algorithm does not guarantee an answer on every run, but succeeds with high probability, and repeated runs drive the failure probability arbitrarily low4. For primality this yielded the Miller–Rabin test (building on Gary Miller's deterministic test under an unproved hypothesis, made probabilistic by Michael Rabin in 1980): pick random bases, check the Fermat-type congruence; composite numbers pass only rarely. This gave fast, reliable-in-practice primality checking, and the closely related Solovay–Strassen test (1977) gave an independent method using Jacobi symbols. Probabilistic thinking also reshaped factoring.

Integer factorization is the complementary problem: given a composite, find its factors3. Trial division and Fermat's method are ancient; the modern era opened with algorithms whose running time depends on the size of the factors rather than the number. Pollard's rho (John Pollard, 1975) and Pollard's \(p-1\) method find small or specially structured factors quickly56. The quadratic sieve (Carl Pomerance, 1981) and later the number field sieve (late 1980s–1990s, with contributions from John Pollard, Arjen Lenstra, Hendrik Lenstra, Mark Manasse, and others) exploit smooth numbers—integers all of whose prime factors are small—to build congruences of squares modulo \(N\), then extract a factor by greatest-common-divisor arithmetic. The number field sieve remains the best known classical method for factoring the large numbers used in cryptography, and its subexponential complexity is a benchmark against which progress is measured7.

Public-key cryptography as the engine

The single largest external driver of computational number theory was the invention of public-key cryptography. In 1976 Whitfield Diffie and Martin Hellman proposed a key-exchange scheme whose security rests on the presumed difficulty of the discrete logarithm problem in a finite field. In 1977 Ron Rivest, Adi Shamir, and Leonard Adleman introduced RSA, whose security rests on the presumed difficulty of factoring. Suddenly a hard number-theory problem was worth money and national attention. Factoring and discrete-log algorithms became strategic research; the gap between "hard in practice" and "provably hard" became an urgent practical question, and a cautionary one, since the security of every RSA message depends on no one having found a fast factoring algorithm3.

This dynamic also drove the study of the computational complexity of number-theoretic problems: which problems are in polynomial time, which are not known to be, and how reductions connect them. Factoring and discrete log are not known to be NP-hard; they may be "merely" hard8. Establishing lower bounds on their difficulty is one of the deep open problems of the area. Probabilistic algorithms, the hardness assumptions behind cryptography, and the algorithms that would break it form one tightly coupled story.

Algebraic and geometric computation

Number theory's objects are not only integers. Computational algebraic number theory concerns the explicit arithmetic of number fields: computing rings of integers, class groups, unit groups, discriminants, and the splitting of primes. The key insight, developed in the 1960s–1980s (notably by Michael Pohst, Hans Zassenhaus, and later Henri Cohen, whose 1993 book A Course in Computational Algebraic Number Theory became the standard reference), was that these objects can be computed using lattice reduction—LLL, the lattice basis-reduction algorithm of Arjen Lenstra, Hendrik Lenstra, and László Lovász (1982)—combined with algorithms for ideals and linear algebra over the rationals. LLL became a ubiquitous tool, equally at home in factoring (it underlies the elliptic-curve factoring method), in cryptography (where it breaks certain schemes), and in Diophantine approximation.

The geometric side produced computational Diophantine geometry and the arithmetic of elliptic curves. The group law on an elliptic curve—points can be "added" by a geometric chord-and-tangent rule—makes the curve's rational points a finitely generated abelian group (Mordell's theorem, extended by Weil). Making this computational meant algorithms for adding points, for finding generators of the rational points, and for computing the rank, often relying on the Birch and Swinnerton-Dyer conjecture as a heuristic guide. Hendrik Lenstra's elliptic-curve factorization method (1985) was a striking demonstration that elliptic-curve arithmetic could solve a classical integer problem by working in a group where the relevant order is easy to vary. Higher-genus curves, with their Jacobians and divisor class groups, extended the program; the Mordell–Weil and Mazur structures supply the targets that computations aim to realize.

Computer algebra systems and mathematical software

None of this would have spread without computer algebra systems—software that manipulates symbolic expressions and exact arithmetic rather than floating-point approximations. Systems such as MACSYMA (developed from the 1960s), REDUCE, Mathematica (1988), Maple, PARI/GP, SageMath (2005, now often called Sage), and the specialized Magma brought the algorithms of the field into the hands of working mathematicians. A number theorist could now compute a class group, test primality, or find rational points by issuing a command. The systems also became a medium for verifying conjectures and for generating the data that motivates new theorems—a computational practice that increasingly shapes what number theorists choose to investigate1.

Quantum algorithms and the present

The theoretical shock came in 1994, when Peter Shor showed that a quantum computer could factor integers and compute discrete logarithms in polynomial time. Shor's algorithm exploits quantum period-finding via the quantum Fourier transform to solve the order-finding problem underlying both factoring and discrete log. The result did not break cryptography on existing machines, but it made the long-term security of RSA and finite-field discrete-log systems a live concern, and it made post-quantum cryptography—schemes based on lattices, error-correcting codes, and other structures believed hard even for quantum computers—a major research area. It also sharpened the distinction between classical and quantum complexity for number-theoretic problems.

Today the field runs on several parallel tracks that descend directly from this history. Deterministic and probabilistic primality testing are mature, with much current attention on certification and on algorithms suited to constrained devices. Factoring and discrete log have moved to number-field and function-field sieves and to record computations that test their limits. Computational algebraic number theory and elliptic-curve arithmetic are routine in software and central to the cryptography that uses them. Post-quantum cryptography is the newest driver, and the questions it raises—how to prove hardness, how to design schemes whose security survives quantum attack, how far lattice reduction can be pushed—are continuous with the eighty-year-old question of what makes a number-theoretic problem genuinely hard. The subject is no longer a corner of number theory but a principal way the discipline touches the world.

References

  1. Computational number theory, Wikipedia
  2. Sieve of Eratosthenes, Wikipedia
  3. Integer factorization, Wikipedia
  4. Randomized algorithm, Wikipedia
  5. Pollard's rho algorithm, Wikipedia
  6. Pollard's p − 1 algorithm, Wikipedia
  7. General number field sieve, Wikipedia
  8. NP-intermediate, Wikipedia

The frameworks of Computational Number Theory

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 300 BCE-1945
  2. 1950-Present

    Primality test

    How can we tell if a number is prime?

    Fly to its tower in Nousfarer

  3. 1965-Present

    Computational algebraic number theory

    How do we compute in number fields?

    About Computational algebraic number theory
    Computational algebraic number theory addresses a question that earlier computational frameworks largely set aside: how can we compute the fundamental algebraic invariants of number fields—their rings of integers, class groups, unit groups, and Galois groups—explicitly and efficiently? While the subexponential algorithms of the 1980s had shown that integer factorization and discrete logarithms could be tackled in practice, they worked almost exclusively over the rational integers Z\mathbb{Z} or finite fields Fp\mathbb{F}_p. This framework, which crystallized around 1990, extends algorithmic methods systematically to algebraic number fields—finite extensions of Q\mathbb{Q}—and to the arithmetic of their ideals. Its central commitment is that the algebraic structures that 19th-century number theorists described purely theoretically can be made computationally accessible, and that doing so opens up new solutions to Diophantine equations and provides the algorithmic foundations for later cryptographic systems.
    The core curriculum for a first course in computational algebraic number theory proceeds through a logical sequence of concepts, each building on the last:
    1. Number field and ring of integers: A number field KK is a finite extension of Q\mathbb{Q}, and its ring of integers OK\mathcal{O}_K is the set of algebraic integers in KK. Computing an integral basis for OK\mathcal{O}_K is the first algorithmic task.
    2. Ideal factorization: In OK\mathcal{O}_K, unique factorization of elements fails, but unique factorization of ideals into prime ideals is restored. Algorithms for factoring an ideal into prime ideals are essential.
    3. Class group: The ideal class group Cl(K)\mathrm{Cl}(K) measures how far OK\mathcal{O}_K is from being a principal ideal domain. Computing its structure and size (the class number) is a central problem.
    4. Unit group: Dirichlet's unit theorem describes the structure of the unit group OK×\mathcal{O}_K^\times as a finitely generated abelian group. Computing its rank and generators (the regulator) is the companion problem to the class group.
    5. Lattice reduction: The LLL algorithm (Lenstra–Lenstra–Lovász, 1982) finds short vectors in lattices and is the workhorse for nearly all computations in number fields, from reducing ideal bases to finding relations.
    6. Buchmann's algorithm: Developed around 1988–1990, this algorithm computes the class group and regulator by combining lattice reduction with subexponential techniques, making computations feasible for fields of moderate degree.
    7. Galois group: The Galois group of a number field describes its symmetries. Algorithms for computing Galois groups, often using resolvent polynomials, are a standard tool.
    8. Norm and trace: These linear-algebraic maps from KK to Q\mathbb{Q} provide basic invariants and are used throughout, from defining the discriminant to constructing integral bases.
    9. Index calculus: The index-calculus method for the discrete logarithm problem in finite fields and on elliptic curves relies on smoothness in number fields, linking this framework to cryptographic applications.
    10. Number field sieve: The number field sieve (1990) is the asymptotically fastest known algorithm for factoring large integers, and it is a direct application of computational algebraic number theory.
    These concepts are not taught as isolated facts; they form a coherent toolkit. For example, computing the class group of a quadratic field requires finding an integral basis, factoring the discriminant, and then using lattice reduction to search for relations among prime ideals—a sequence that ties together items 1, 2, 3, and 5.
    The intellectual history of computational algebraic number theory begins with its precursors. The theoretical foundations were laid in the 19th and early 20th centuries by Gauss, Dedekind, Kronecker, and Hilbert, who developed the concepts of rings of integers, ideal factorization, class groups, and unit groups. These were purely structural results, with no algorithmic content. The subexponential algorithms of the 1980s—notably the quadratic sieve for factoring (Pomerance, 1981) and the index-calculus method for discrete logarithms (Adleman, 1979)—showed that number-theoretic problems could be solved in practice for inputs of cryptographic size, but they worked only over Z\mathbb{Z} or Fp\mathbb{F}_p. The key figure who bridged algebraic number theory and algorithmic practice was Henri Cohen, whose 1993 book A Course in Computational Algebraic Number Theory (Springer GTM 138) codified the framework. Cohen systematized algorithms for computing in number fields: finding integral bases, factoring ideals, computing class groups and unit groups via the Buchmann–Cohen algorithm (a refinement of Buchmann's original method), and applying these to Diophantine equations. Other seminal works include Michael Pohst's 1993 Computational Algebraic Number Theory and the development of the PARI/GP system (started by Henri Cohen and François Dress in the late 1980s), which became the standard software for this framework. The framework coexists with its peers: it shares the subexponential ethos with Subexponential Algorithms, but insists on exact algebraic structures; it provides the algorithmic core for Post-Quantum and Lattice-Based Cryptography (which emerged around 2000 and uses lattices in a more abstract setting); and it contrasts with Deterministic Polynomial-Time Algorithms (like AKS) that avoid heuristics entirely. The framework's legacy is a mature set of algorithms implemented in PARI/GP, Magma, and SageMath, enabling number theorists to compute invariants of number fields up to degree 100 or more, and to attack Diophantine equations that were previously intractable.
    The 11 concepts its tower teaches
    • Buchmann's algorithm
    • Class group
    • Galois group
    • Ideal factorization
    • Index calculus
    • Lattice reduction
    • Norm and trace
    • Number field
    • Number field sieve
    • Ring of integers
    • Unit group

    Fly to its tower in Nousfarer

  4. 1965-Present

    Computer algebra system

    How can machines do symbolic mathematics?

    Fly to its tower in Nousfarer

  5. 1975-Present
  6. 1975-Present

    Integer factorization

    How do we find the factors of an integer?

    Fly to its tower in Nousfarer

  7. 1975-Present

    Randomized algorithm

    How can randomness help solve problems?

    Fly to its tower in Nousfarer

  8. 1976-Present

    Public-key cryptography

    How can we communicate securely using number theory?

    Fly to its tower in Nousfarer

  9. 1982-Present
  10. 1985-Present
  11. 1994-Present

    Quantum algorithms for number theory

    How can quantum computers solve number-theory problems?

    Fly to its tower in Nousfarer

  12. 2000-Present

    Post-quantum cryptography

    How can we encrypt against quantum computers?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Classical hand-computational arithmet…Primality testComputational algebraic number theoryComputer algebra systemComputational complexity of number-th…Integer factorizationRandomized algorithmPublic-key cryptographyLattice reduction and LLL-based metho…Computational Diophantine geometry an…Quantum algorithms for number theoryPost-quantum cryptography

Beyond the field

Where Computational Number Theory's ideas came from in other fields, and what they led to there: the strongest 12 of 61 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Computational Number Theory is a planet in Nousfarer

Its city has a tower for each of these 12 frameworks. Land, walk in, and climb one concept at a time.

Land on Computational Number Theory

Related fields

Fields its ideas are linked to

More in Number Theory

See where Computational Number Theory sits on the Map of Human Knowledge