Computational number theory
Encyclopedia
In mathematics
, computational number theory, also known as algorithmic number theory, is the study of algorithm
s for performing number theoretic
computation
s. The best known problem in the field is integer factorization
.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, computational number theory, also known as algorithmic number theory, is the study of algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s for performing number theoretic
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
computation
Computation
Computation is defined as any type of calculation. Also defined as use of computer technology in Information processing.Computation is a process following a well-defined model understood and expressed in an algorithm, protocol, network topology, etc...
s. The best known problem in the field is integer factorization
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
.
See also
- Computational complexity of mathematical operationsComputational complexity of mathematical operationsThe following tables list the running time of various algorithms for common mathematical operations.Here, complexity refers to the time complexity of performing computations on a multitape Turing machine...
- Sage Math
- Number Theory LibraryNumber Theory LibraryNTL is a C++ library for doing number theory. NTL supports arbitrary length integer and arbitrary precision floating point arithmetic, finite fields, vectors, matrices, polynomials, lattice basis reduction and basic linear algebra. NTL is free software released under the GNU General Public License....
- PARI/GPPARI/GPPARI/GP is a computer algebra system with the main aim of facilitating number theory computations. It is free software; versions 2.1.0 and higher are distributed under the GNU General Public License...
Further reading
- Victor ShoupVictor ShoupVictor Shoup is a computer scientist and mathematician. He obtained a PhD in computer science from the University of Wisconsin–Madison in 1989, and he did his undergraduate work at the University of Wisconsin-Eau Claire. He is currently a professor at the Courant Institute of Mathematical Sciences...
, 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 BachEric BachEric Bach is an American computer scientist who has made contributions to computational number theory. Bach did his undergraduate studies at the University of Michigan, Ann Arbor, and got his Ph.D. in computer science from the University of California, Berkeley, in 1984 under the supervision of...
and Jeffrey ShallitJeffrey ShallitJeffrey Outlaw Shallit is a computer scientist, number theorist, a noted advocate for civil liberties on the Internet, and a noted critic of intelligent design. He is married to Anna Lubiw, also a computer scientist....
, Algorithmic Number Theory, volume 1: Efficient Algorithms. MIT Press, 1996, ISBN 0-262-02405-5 - Richard CrandallRichard CrandallRichard E. Crandall is an American Physicist and computer scientist who has made contributions to computational number theory.He is most notable for the development of the irrational base discrete weighted transform, an important method of finding very large primes. He has, at various times, been...
and Carl PomeranceCarl PomeranceCarl Bernard Pomerance is a well-known number theorist. He attended college at Brown University and later received his Ph.D. from Harvard University in 1972 with a dissertation proving that any odd perfect number has at least 7 distinct prime factors. He immediately joined the faculty at the...
, Prime Numbers: A Computational Perspective, Springer-Verlag, 2001, ISBN 0-387-94777-9 - Hans RieselHans RieselHans Ivar Riesel is a Swedish mathematician who discovered the 18th known Mersenne prime in 1957, using the computer BESK. This prime is 23217-1, which consists of 969 digits. He held the record for the largest known prime from 1957 to 1961, when Alexander Hurwitz discovered a larger one. Riesel...
, Prime Numbers and Computer Methods for Factorization, second edition, Birkhäuser, 1994, ISBN 0-8176-3743-5, ISBN 3-7643-3743-5