In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
and
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, computational number theory, also known as algorithmic number theory, is the study of
computational methods for investigating and solving problems in
number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...
and
arithmetic geometry, including algorithms for
primality testing and
integer factorization
In mathematics, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is a comp ...
, finding solutions to
diophantine equations, and explicit methods in
arithmetic geometry.
Computational number theory has applications to
cryptography
Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...
, including
RSA,
elliptic curve cryptography and
post-quantum cryptography
Post-quantum cryptography (PQC), sometimes referred to as quantum-proof, quantum-safe, or quantum-resistant, is the development of cryptographic algorithms (usually public-key algorithms) that are currently thought to be secure against a crypt ...
, and is used to investigate
conjectures
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis or Fermat's conjecture (now a theorem, proven in 1995 by Andrew Wiles), hav ...
and
open problems
In science and mathematics, an open problem or an open question is a known problem which can be accurately stated, and which is assumed to have an objective and verifiable solution, but which has not yet been solved (i.e., no solution for it is kno ...
in number theory, including the
Riemann hypothesis, the
Birch and Swinnerton-Dyer conjecture, the
ABC conjecture, the
modularity conjecture, the
Sato-Tate conjecture, and explicit aspects of the
Langlands program
In mathematics, the Langlands program is a set of conjectures about connections between number theory, the theory of automorphic forms, and geometry. It was proposed by . It seeks to relate the structure of Galois groups in algebraic number t ...
.
Software packages
*
Magma computer algebra system
*
SageMath
*
Number Theory Library
*
PARI/GP
*
Fast Library for Number Theory
Further reading
* Michael E. Pohst (1993): ''Computational Algebraic Number Theory'', Springer, ISBN 978-3-0348-8589-8
*
*
*
*
*
*
*
*
*
*
*
* Peter Giblin (1993): ''Primes and Programming: An Introduction to Number Theory with Computing'', Cambridge University Press, ISBN 0-521-40988-8
* Nigel P. Smart (1998): ''The Algorithmic Resolution of Diophantine Equations'', Cambridge University Press, ISBN 0-521-64633-2
* Ramanujachary Kumanduri and Cristina Romero (1998): ''Number Theory with Computer Applications'', Prentice Hall, ISBN 0-13-801812-X
* Fernando Rodriguez Villegas (2007): ''Experimental Number Theory'', Oxford University Press, ISBN 978-0-19-922730-3
* Harold M. Edwards (2008): ''Higher Arithmetic: An Algorithmic Introduction to Number Theory'', American Mathematical Society, ISBN 978-1-4704-2153-3
* Lasse Rempe-Gillen and Rebecca Waldecker (2014). ''Primality Testing for Beginners''. American Mathematical Society. ISBN 978-0-8218-9883-3
References
External links
*
{{Number theory-footer
Number theory
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...