View source for Computational number theory

{{short description|Study of algorithms for performing number theoretic computations}}
In [[mathematics]] and [[computer science]], '''computational number theory''', also known as '''algorithmic number theory''', is the study of 
[[computation|computational methods]] for investigating and solving problems in [[number theory]] and [[arithmetic geometry]], including algorithms for [[primality testing]] and [[integer factorization]], finding solutions to [[diophantine equations]], and explicit methods in [[arithmetic geometry]].{{r|pcm}}
Computational number theory has applications to [[cryptography]], including [[RSA (cryptosystem)|RSA]], [[elliptic curve cryptography]] and [[post-quantum cryptography]], and is used to investigate [[conjectures]] and [[open problems]] in number theory, including the [[Riemann hypothesis]], the [[Birch and Swinnerton-Dyer conjecture]], the [[ABC conjecture]], the [[Modularity theorem|modularity conjecture]], the [[Sato-Tate conjecture]], and explicit aspects of the [[Langlands program]].{{r|pcm}}{{r|bachshallit}}{{r|cohen}}

==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

*{{cite book
| author1   = Eric Bach | author1-link = Eric Bach
| author2   = Jeffrey Shallit | author2-link = Jeffrey Shallit
| title     = Algorithmic Number Theory, Volume 1: Efficient Algorithms
| publisher = MIT Press
| year      = 1996
| isbn      = 0-262-02405-5
| url       = https://cs.uwaterloo.ca/~shallit/ant.html
}}

*{{cite book
| author     = David M. Bressoud
| authorlink = David Bressoud
| title      = Factorisation and Primality Testing
| publisher  = Springer-Verlag
| year       = 1989
| isbn       = 0-387-97040-1
| url-access = registration
| url        = https://archive.org/details/factorizationpri0000bres
}}

* {{cite book
| editor1   = Joe P. Buhler | editor1-link = Joe P. Buhler
| editor2   = Peter Stevenhagen
| title     = Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography
| series    = MSRI Publications
| volume    = 44
| publisher = [[Cambridge University Press]]
| year      = 2008
| isbn      = 978-0-521-20833-8
| zbl       = 1154.11002
| url       = https://www.cambridge.org/us/academic/subjects/mathematics/number-theory/algorithmic-number-theory-lattices-number-fields-curves-and-cryptography?format=HB&isbn=9780521808545
}}

* {{cite book
| author    = Henri Cohen | author-link = Henri Cohen (number theorist)
| title     = A Course In Computational Algebraic Number Theory 
| year      = 1993
| isbn      = 0-387-55640-0
| publisher = [[Springer-Verlag]]
| series    = [[Graduate Texts in Mathematics]]
| volume    = 138
| doi = 10.1007/978-3-662-02945-9
}}

* {{cite book
| author    = Henri Cohen | author-link = Henri Cohen (number theorist)
| title     = Advanced Topics in Computational Number Theory
| year      = 2000
| isbn      = 0-387-98727-4
| publisher = [[Springer-Verlag]]
| series    = [[Graduate Texts in Mathematics]]
| volume    = 193
| doi = 10.1007/978-1-4419-8489-0
}}

* {{cite book
| author    = Henri Cohen | author-link = Henri Cohen (number theorist)
| title     = Number Theory – Volume I: Tools and Diophantine Equations
| year      = 2007 
| isbn      = 978-0-387-49922-2
| publisher = [[Springer-Verlag]]
| series    = [[Graduate Texts in Mathematics]]
| volume    = 239
| doi = 10.1007/978-0-387-49923-9
}}

* {{cite book
| author    = Henri Cohen | author-link = Henri Cohen (number theorist)
| title     = Number Theory – Volume II: Analytic and Modern Tools
| year      = 2007 
| isbn      = 978-0-387-49893-5
| publisher = [[Springer-Verlag]]
| series    = [[Graduate Texts in Mathematics]]
| volume    = 240
| doi = 10.1007/978-0-387-49894-2
}}

* {{cite book
| author1   = Richard Crandall | author1-link = Richard Crandall
| author2   = Carl Pomerance | author2-link = Carl Pomerance
| title     = Prime Numbers: A Computational Perspective
| publisher = Springer-Verlag
| year      = 2001
| isbn      = 0-387-94777-9
| doi = 10.1007/978-1-4684-9316-0
}}

* {{cite book
| author     = Hans Riesel
| authorlink = Hans Riesel
| title      = Prime Numbers and Computer Methods for Factorization
| edition    = second
| publisher  = Birkhäuser
| year       = 1994
| isbn       = 0-8176-3743-5
| zbl        = 0821.11001
| series     = Progress in Mathematics
| volume     = 126
}}

* {{cite book
| author      = Victor Shoup
| author-link = Victor Shoup
| title       = A Computational Introduction to Number Theory and Algebra
| publisher   = [[Cambridge University Press]]
| year        = 2012
| isbn        = 9781139165464
| doi         = 10.1017/CBO9781139165464
| url = http://www.shoup.net/ntb/
}}

* {{cite book 
| author     = Samuel S. Wagstaff, Jr.
| authorlink = Samuel S. Wagstaff, Jr.
| title      = The Joy of Factoring 
| publisher  = American Mathematical Society 
| year       = 2013 
| isbn       = 978-1-4704-1048-3 
| url        = https://www.ams.org/bookpages/stml-68 
}}

* 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==
{{reflist|refs=

<ref name=pcm>{{citation 
| author1    = Carl Pomerance | author1-link = Carl Pomerance
| editor1    = Timothy Gowers | editor1-link = Timothy Gowers
| title      = Computational Number Theory
| work       = The Princeton Companion to Mathematics
| publisher  = [[Princeton University Press]]
| year       = 2009
| url        = https://math.dartmouth.edu/~carlp/PDF/pcm0049.pdf
}}</ref>

<ref name=bachshallit>{{cite book
| author1   = Eric Bach | author1-link = Eric Bach
| author2   = Jeffrey Shallit | author2-link = Jeffrey Shallit
| title     = Algorithmic Number Theory, Volume 1: Efficient Algorithms
| publisher = MIT Press
| year      = 1996
| isbn      = 0-262-02405-5
}}</ref>

<ref name=cohen>{{cite book
| author    = Henri Cohen | author-link = Henri Cohen (number theorist)
| title     = A Course In Computational Algebraic Number Theory 
| year      = 1993
| isbn      = 0-387-55640-0
| publisher = [[Springer-Verlag]]
| series    = [[Graduate Texts in Mathematics]]
| volume    = 138
| doi = 10.1007/978-3-662-02945-9
}}</ref>
}}

==External links==
*{{Commonscatinline}}

{{Number-theoretic algorithms}}
{{Algebraic curves navbox}}
{{Number theory-footer}}

[[Category:Computational number theory| ]]
[[Category:Number theory]]
[[Category:Computational fields of study|Number theory]]