 Computational number theory

In mathematics, computational number theory, also known as algorithmic number theory, is the study of algorithms for performing number theoretic computations. The best known problem in the field is integer factorization.
See also
Further reading
 Victor Shoup, A Computational Introduction to Number Theory and Algebra. Cambridge, 2005, ISBN 0521851548
 Henri Cohen, A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics 138, SpringerVerlag, 1993.
 Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, volume 1: Efficient Algorithms. MIT Press, 1996, ISBN 0262024055
 Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, SpringerVerlag, 2001, ISBN 0387947779
 Hans Riesel, Prime Numbers and Computer Methods for Factorization, second edition, Birkhäuser, 1994, ISBN 0817637435, ISBN 3764337435
Primality tests AKS · APR · Baillie–PSW · ECPP · Elliptic curve · Pocklington · Fermat · Lucas · Lucas–Lehmer · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay–Strassen · Miller–Rabin · Trial divisionSieving algorithms Integer factorization algorithms CFRAC · Dixon's · ECM · Euler's · Pollard's rho · p − 1 · p + 1 · QS · GNFS · SNFS · rational sieve · Fermat's · Shanks' square forms · Trial division · Shor'sMultiplication algorithms Ancient Egyptian multiplication · Karatsuba algorithm · Toom–Cook multiplication · Schönhage–Strassen algorithm · Fürer's algorithmDiscrete logarithm algorithms Babystep giantstep · Pollard rho · Pollard kangaroo · Pohlig–Hellman · Index calculus · Function field sieveGCD algorithms Modular square root algorithms Cipolla · Pocklington's · Tonelli–ShanksOther algorithms Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests (current article is always in bold).Major topics in Number theory Algebraic number theory • Analytic number theory • Geometric number theory • Computational number theory • Transcendental number theory • Combinatorial number theory • Arithmetic geometry • Arithmetic topology • Arithmetic dynamicsNumbers • Natural numbers • Prime numbers • Rational numbers • Irrational numbers • Algebraic numbers • Transcendental numbers • padic numbers • Arithmetic • Modular arithmetic • Arithmetic functionsThis number theoryrelated article is a stub. You can help Wikipedia by expanding it.