Computational number theory

From Wikipedia, the free encyclopedia

Jump to: navigation, search

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.

[edit] See also

Victor Shoup, A Computational Introduction to Number Theory and Algebra. Cambridge, 2005, ISBN 0-521-85-154-8
Henri Cohen, A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics 138, Springer-Verlag, 1993.
Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, volume 1: Efficient Algorithms. MIT Press, 1996, ISBN 0-262-02405-5
Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, Springer-Verlag, 2001, ISBN 0-387-94777-9
Hans Riesel, Prime Numbers and Computer Methods for Factorization, second edition, Birkhäuser, 1994, ISBN 0-8176-3743-5, ISBN 3-7643-3743-5

v · d · e Number-theoretic algorithms

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 division

Sieving algorithms	Sieve of Atkin · Sieve of Eratosthenes · Sieve of Sundaram · Wheel factorization

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's

Multiplication algorithms	Ancient Egyptian multiplication · Karatsuba algorithm · Toom–Cook multiplication · Schönhage–Strassen algorithm · Fürer's algorithm

Discrete logarithm algorithms	Baby-step giant-step · Pollard rho · Pollard kangaroo · Pohlig–Hellman · Index calculus · Function field sieve

GCD algorithms	Binary GCD · Euclidean · Extended Euclidean · Lehmer's

Modular square root algorithms	Cipolla · Pocklington's · Tonelli–Shanks

Other algorithms	Chakravala · Cornacchia · integer relation algorithm · integer square root · Modular exponentiation · Schoof's

Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests (current article is always in bold).

v · d · e 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 dynamics

Numbers Natural numbers Prime numbers Rational numbers Irrational numbers Algebraic numbers Transcendental numbers p-adic numbers Arithmetic Modular arithmetic Arithmetic functions

Quadratic forms Modular forms L-functions Diophantine equations Diophantine approximation Continued fractions

List of recreational number theory topics List of number theory topics

This number theory-related article is a stub. You can help Wikipedia by expanding it.