Computational number theory

Computational number theory
Name	Computational number theory
Discipline	Mathematics, Computer Science
Subdiscipline	Algorithmic number theory, Cryptography

Computational number theory is the branch of mathematical study that develops algorithms to solve problems about integers, primes, algebraic numbers, and arithmetic structures using computers. It connects classical results from Pierre de Fermat, Carl Friedrich Gauss, Adrien-Marie Legendre, Leonhard Euler and Srinivasa Ramanujan with algorithmic advances by Alan Turing, John von Neumann, Donald Knuth, Manuel Blum and Andrew Odlyzko. Applications span from secure communication used by RSA (cryptosystem), Diffie–Hellman key exchange, Elliptic Curve Cryptography to integer sequence investigations in projects like the Great Internet Mersenne Prime Search and computational verifications in the Langlands program.

History and development

The field evolved as computing machinery advanced: early theoretical foundations trace to work of Euclid, Pierre de Fermat, Euler, Gauss and Dirichlet, while algorithmic perspectives emerged with Alan Turing, Alonzo Church, John von Neumann, Norbert Wiener and engineers at Bell Labs. Milestones include fast multiplication algorithms by Karatsuba and Toom–Cook contributors, asymptotic analyses influenced by Andrey Kolmogorov and Emil Post, and the introduction of public-key cryptography by Whitfield Diffie, Martin Hellman, Rivest–Shamir–Adleman designers and others at institutions like MIT and Stanford University. Developments in primality testing and factorization accelerating research involved Carl Pomerance, John Pollard, Robert Silverman, A. O. L. Atkin, Harald Helfgott and computational projects at University of California, Berkeley, Princeton University and Cambridge University. Collaborative distributed projects such as GIMPS and national labs like Los Alamos National Laboratory and Lawrence Livermore National Laboratory pushed record computations, while conjectures from Riemann and programs like the L-functions and Modular Forms Database guided theory and computation.

Fundamental algorithms and methods

Core tools include fast integer arithmetic (implementations derived from work by Karatsuba, Schönhage, Strassen, Toom), modular arithmetic optimized by contributors affiliated with IBM and Microsoft Research, and lattice reduction methods from Hendrik Lenstra, Arjen Lenstra, Vijay Vazirani and Lenstra–Lenstra–Lovász authors. Algorithms for computing greatest common divisors trace to Euclid and modern variants connect to Knuth's analysis. Symbolic manipulation systems arising at NAG, Wolfram Research, SageMath developers and contributors like Richard Brent and Paul Zimmermann implement algorithms for arithmetic in algebraic number fields influenced by Dedekind and Hilbert.

Integer factorization and primality testing

Primality testing saw deterministic breakthrough algorithms by Agrawal, Kayal, Saxena (AKS) and practical randomized tests from Miller, Rabin, Solovay–Strassen proponents. Factorization developed through methods: trial division and Pollard's rho by Pollard; elliptic curve factorization by H. W. Lenstra; number field sieve advanced by teams including Adleman, Pomerance, Schroeppel and implemented in projects at CWI, NFSNet and efforts by Graham Steel and Arjen Lenstra. Record-breaking factorings involved collaborations with CWI, ANS authors, and entities like Microsoft and Google using distributed computing. Heuristic and rigorous approaches reference conjectures by Riemann and computational verifications by researchers at Princeton, Oxford, ETH Zurich and INRIA.

Algebraic and analytic number theory computations

Computation in algebraic number theory leverages algorithms for ring of integers, class groups and unit computations inspired by Kummer, Dedekind, Heegner, Stark and implemented by teams at PARI/GP, Magma and SageMath projects with contributions from Henri Cohen, J. H. Silverman, Joseph H. Silverman, John Cremona and Nils-Peter Skoruppa. Analytic computations for L-functions, modular forms and zeroes of zeta functions rely on methods developed by Atkin, Lehmer, Heath-Brown, Montgomery, Odlyzko and datasets maintained by LMFDB curators and collaborators at Harvard University, Princeton, Brown University and École Normale Supérieure.

Computational complexity and security applications

Complexity classifications reference work by Stephen Cook, Leonid Levin, Richard Karp and implications drawn by Shafi Goldwasser and Silvio Micali for probabilistic algorithms. Cryptographic primitives depend on hardness assumptions linked to integer factoring and discrete logarithm problems studied by Rivest, Shamir, Adleman, Menezes, Oorschot, Vanstone and post-quantum considerations from Peter Shor, Lov Grover and projects at IBM Research, Google Quantum AI, D-Wave Systems and Xanadu. Security standards and analyses are shaped by organizations like NIST, IETF, IEEE and industry teams at RSA Security and OpenSSL contributors.

Software and implementations

Major software ecosystems include PARI/GP (work by Henri Cohen and collaborators), Magma (developers with ties to University of Sydney), SageMath (initiated by William Stein and community contributors), Maple and Mathematica from Maplesoft and Wolfram Research, and specialized libraries like GMP (by Torbjörn Granlund and Richard Brent), NTL (by Victor Shoup), FLINT and MPFR used in research at University of Warwick, University of Tokyo and University of Paris-Sud. Distributed computation initiatives such as GIMPS, coordinated by volunteers and institutions including Georgia Tech and University of Central Missouri, have produced records for primes and factorizations, while academic packages from CWI, INRIA, Max Planck Institute and CNRS support large-scale experiments.

Category:Number theory