- Atlas
- Mathematics
- Computational Number Theory
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
- Classical hand-computational arithmetic 300 BCE-1945
- Primality test 1950-Present
- Computational algebraic number theory 1965-Present
- Computer algebra system 1965-Present
- Computational complexity of number-theoretic problems 1975-Present
- Integer factorization 1975-Present
- Randomized algorithm 1975-Present
- Public-key cryptography 1976-Present
- Lattice reduction and LLL-based methods 1982-Present
- Computational Diophantine geometry and elliptic-curve arithmetic 1985-Present
- Quantum algorithms for number theory 1994-Present
- Post-quantum cryptography 2000-Present
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
- Computational number theory, Wikipedia
- Sieve of Eratosthenes, Wikipedia
- Integer factorization, Wikipedia
- Randomized algorithm, Wikipedia
- Pollard's rho algorithm, Wikipedia
- Pollard's p − 1 algorithm, Wikipedia
- General number field sieve, Wikipedia
- 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.
- 300 BCE-1945
Classical hand-computational arithmetic
How do you compute with integers by hand?
- 1950-Present
- 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 or finite fields . This framework, which crystallized around 1990, extends algorithmic methods systematically to algebraic number fields—finite extensions of —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:- Number field and ring of integers: A number field is a finite extension of , and its ring of integers is the set of algebraic integers in . Computing an integral basis for is the first algorithmic task.
- Ideal factorization: In , 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.
- Class group: The ideal class group measures how far is from being a principal ideal domain. Computing its structure and size (the class number) is a central problem.
- Unit group: Dirichlet's unit theorem describes the structure of the unit group as a finitely generated abelian group. Computing its rank and generators (the regulator) is the companion problem to the class group.
- 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.
- 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.
- 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.
- Norm and trace: These linear-algebraic maps from to provide basic invariants and are used throughout, from defining the discriminant to constructing integral bases.
- 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.
- 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 or . 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
- 1965-Present
- 1975-Present
Computational complexity of number-theoretic problems
How hard are number-theoretic problems?
- 1975-Present
- 1975-Present
- 1976-Present
Public-key cryptography
How can we communicate securely using number theory?
- 1982-Present
Lattice reduction and LLL-based methods
How do we find short vectors in lattices?
- 1985-Present
Computational Diophantine geometry and elliptic-curve arithmetic
How do we find rational points on curves?
- 1994-Present
Quantum algorithms for number theory
How can quantum computers solve number-theory problems?
- 2000-Present
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.
Primality test grew out of Classical hand-computational arithmetic
Classical hand methods such as trial division and Fermat's little theorem were turned into machine procedures for testing primality after electronic computers arrived. The Fermat congruence in particular became the basis of the probabilistic tests that defined the new field.
Carried by Pierre de Fermat; Derrick Henry Lehmer.
Public-key cryptography influenced by Integer factorization
RSA's security was explicitly founded on the presumed difficulty of integer factorization, making factoring algorithms a strategic research target. The practical hardness of factoring became the basis for public-key encryption.
Carried by Ron Rivest; Adi Shamir; Leonard Adleman.
Quantum algorithms for number theory influenced by Public-key cryptography
Shor's quantum algorithms for factoring and discrete logarithms directly threatened the security of RSA and Diffie–Hellman. The existence of public-key cryptography based on these problems motivated the search for quantum attacks.
Carried by Peter Shor.
Post-quantum cryptography influenced by Quantum algorithms for number theory
The threat posed by quantum algorithms to factoring and discrete-log-based cryptography drove the development of post-quantum cryptographic schemes. Researchers sought systems based on problems believed hard even for quantum computers.
Integer factorization grew out of Classical hand-computational arithmetic
Ancient factoring methods such as trial division and Fermat's method were the starting point for modern factorization algorithms. Pollard's rho and p-1 methods built on these classical ideas while exploiting new number-theoretic structure.
Carried by John Pollard.
Computational complexity of number-theoretic problems influenced by Primality test
The quest for faster primality tests raised the question of the intrinsic complexity of number-theoretic problems. The Adleman–Pomerance–Rumely and later AKS tests were landmarks in placing primality within complexity classes.
Carried by Leonard Adleman; Carl Pomerance; Manindra Agrawal.
Randomized algorithm influenced by Primality test
Deterministic primality testing faced the problem of pseudoprimes, and the response was to randomize the choice of bases. The Solovay–Strassen and Miller–Rabin tests made primality checking probabilistic, establishing randomization as a standard tool.
Carried by Michael Rabin; Robert Solovay; Volker Strassen.
Computational Diophantine geometry and elliptic-curve arithmetic influenced by Computational algebraic number theory
Computational algebraic number theory provided the algorithmic techniques for arithmetic in number fields that were extended to elliptic curves and higher-genus curves. The group law and class group computations carried over into computational Diophantine geometry.
Carried by Henri Cohen.
Computational algebraic number theory influenced by Computer algebra system
Computer algebra systems provided the computational environment for implementing algorithms in algebraic number theory. The development of systems for symbolic computation enabled the practical computation of number field invariants.
Public-key cryptography influenced by Computational complexity of number-theoretic problems
Public-key cryptography rested on assumptions about the computational hardness of number-theoretic problems such as factoring and discrete logarithms. Complexity theory provided the framework for stating and questioning those assumptions.
Carried by Whitfield Diffie; Martin Hellman.
Computational Diophantine geometry and elliptic-curve arithmetic influenced by Integer factorization
Hendrik Lenstra's elliptic-curve factorization method demonstrated that elliptic-curve arithmetic could solve a classical integer problem. This spurred the development of computational Diophantine geometry on elliptic curves.
Carried by Hendrik Lenstra.
Post-quantum cryptography influenced by Lattice reduction and LLL-based methods
Lattice-based cryptography emerged as a leading candidate for post-quantum security, building on the hardness of lattice problems and the LLL algorithm's limitations. Lattice reduction became both a tool and a security concern in the new field.
Computer algebra system grew out of Classical hand-computational arithmetic
Early computer algebra systems were built to automate classical hand computations such as polynomial arithmetic and gcds. The tradition of exact symbolic calculation carried over from pencil-and-paper methods.
Computational Diophantine geometry and elliptic-curve arithmetic influenced by Computer algebra system
Computer algebra systems supplied the symbolic manipulation tools needed for computations on elliptic curves and higher-genus curves. These systems made explicit Diophantine computations feasible.
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.
Computational algebraic number theory grew out of Computational number theory in Number Theory
Computational algebraic number theory grew out of the broader computational number theory tradition as its algebraic branch, applying algorithmic methods to algebraic number fields. The general computational number theory programme was specialised to algebraic settings.
Computational algebraic number theory influenced by Algebraic number theory in Number Theory
Algebraic number theory supplied the objects, invariants and theorems (class groups, units, ideals) that computational algebraic number theory set out to compute. The classical theory's structures became the targets of algorithmic treatment.
Computational complexity of number-theoretic problems grew out of Computational number theory in Number Theory
The computational complexity of number-theoretic problems is the branch of computational number theory that studies the complexity of its algorithms. It grew directly out of the computational number theory tradition as its complexity-theoretic refinement.
Randomized algorithm influenced Probabilistic complexity theory in Randomized Algorithms
The randomized algorithms of the mid-1970s, above all Solovay–Strassen and Miller–Rabin primality testing, supplied the concrete examples from which Gill and others abstracted the probabilistic complexity classes BPP and RP.
Carried by John Gill; Michael Rabin.
Public-key cryptography influenced by Computational number theory in Number Theory
Computational number theory supplied the hard problems, such as integer factorization and discrete logarithms, on which Diffie, Hellman and Rivest–Shamir–Adleman built public-key schemes in 1976–77.
Carried by Whitfield Diffie; Martin Hellman; Ronald Rivest.
Public-key cryptography influenced by Computational number theory in Elementary Number Theory
Elementary computational number theory, especially modular arithmetic and primality testing, provided the concrete operations and hardness assumptions behind the first public-key systems of 1976–77.
Carried by Whitfield Diffie; Martin Hellman.
Public-key cryptography led to Elliptic-Curve Cryptography in Cryptography
The number-theoretic formulation of public-key cryptography, with its reliance on hard group-theoretic problems, was transferred to elliptic-curve groups by Koblitz and Miller.
Carried by Neal Koblitz; Victor S. Miller.
Public-key cryptography influenced Public-Key Infrastructure in Applied Cryptography
Public-key cryptography, grounded in computational number theory such as RSA and discrete logarithms, is the primitive that PKI distributes and certifies. PKI's certificate schemes are built on these number-theoretic public-key systems.
Carried by Rivest, Shamir, Adleman.
Public-key cryptography influenced Cryptographic protocol in Applied Cryptography
Number-theoretic public-key constructions such as RSA provided the concrete primitives that cryptographic protocols compose into key exchange and authentication schemes.
Carried by Rivest, Shamir and Adleman.
Lattice reduction and LLL-based methods influenced Lattice-Based Cryptography in Cryptography
The LLL lattice-reduction algorithm and its analysis supplied both the hard problems (SVP, CVP) and the attack model on which lattice-based cryptography was built.
Carried by Arjen Lenstra; Hendrik Lenstra; László Lovász.
Computational Diophantine geometry and elliptic-curve arithmetic grew out of Elliptic curve group law and Mordell–Weil theory in Arithmetic Geometry
The elliptic curve group law and Mordell–Weil theory are the direct foundation of computational elliptic-curve arithmetic; later work made the group law effective and computed ranks and rational points algorithmically.
Carried by Henri Poincaré; Louis Mordell; André Weil.
Computational Diophantine geometry and elliptic-curve arithmetic grew out of Arithmetic geometry in Number Theory
Arithmetic geometry, especially the Mordell–Weil and descent machinery developed from the 1920s onward, is the direct parent of computational Diophantine geometry, which made its constructions algorithmic.
Carried by André Weil.

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 TheoryRelated fields
Fields its ideas are linked to
- Number Theory 19 links
- Field And Galois Theory 5 links
- Randomized Algorithms 5 links
- Algebraic Number Theory 5 links
- Elementary Number Theory 5 links
- Cryptography 4 links
- Algebra 2 links
- Additive Number Theory 2 links
- Arithmetic Geometry 2 links
- Applied Cryptography 2 links
- Complexity Theory 2 links
- Quantum Computation 2 links
More in Number Theory
- Additive Number Theory
- Algebraic Number Theory
- Analytic Number Theory
- Arithmetic Geometry
- Elementary Number Theory
- Modular Forms And Automorphic Forms
- Number Theory
- Transcendental Number Theory
See where Computational Number Theory sits on the Map of Human Knowledge