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 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.[1] Computational number theory has applications to cryptography, including 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 conjecture, the Sato-Tate conjecture, and explicit aspects of the Langlands program.[1][2][3]

## Contents

* 1 Software packages
* 2 Further reading
* 3 References
* 4 External links

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

* Algorithmic Number Theory, Volume 1: Efficient Algorithms. MIT Press. 1996. ISBN 0-262-02405-5. https://cs.uwaterloo.ca/~shallit/ant.html.

* David M. Bressoud (1989). Factorisation and Primality Testing. Springer-Verlag. ISBN 0-387-97040-1. https://archive.org/details/factorizationpri0000bres.

* Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography. MSRI Publications. 44. Cambridge University Press. 2008. ISBN 978-0-521-20833-8. https://www.cambridge.org/us/academic/subjects/mathematics/number-theory/algorithmic-number-theory-lattices-number-fields-curves-and-cryptography?format=HB&isbn=9780521808545.

* A Course In Computational Algebraic Number Theory. Graduate Texts in Mathematics. 138. Springer-Verlag. 1993. doi:10.1007/978-3-662-02945-9. ISBN 0-387-55640-0.

* Advanced Topics in Computational Number Theory. Graduate Texts in Mathematics. 193. Springer-Verlag. 2000. doi:10.1007/978-1-4419-8489-0. ISBN 0-387-98727-4.

* Number Theory – Volume I: Tools and Diophantine Equations. Graduate Texts in Mathematics. 239. Springer-Verlag. 2007. doi:10.1007/978-0-387-49923-9. ISBN 978-0-387-49922-2.

* Number Theory – Volume II: Analytic and Modern Tools. Graduate Texts in Mathematics. 240. Springer-Verlag. 2007. doi:10.1007/978-0-387-49894-2. ISBN 978-0-387-49893-5.

* Prime Numbers: A Computational Perspective. Springer-Verlag. 2001. doi:10.1007/978-1-4684-9316-0. ISBN 0-387-94777-9.

* Hans Riesel (1994). Prime Numbers and Computer Methods for Factorization. Progress in Mathematics. 126 (second ed.). Birkhäuser. ISBN 0-8176-3743-5.

* Victor Shoup (2012). A Computational Introduction to Number Theory and Algebra. Cambridge University Press. doi:10.1017/CBO9781139165464. ISBN 9781139165464. http://www.shoup.net/ntb/.

* Samuel S. Wagstaff, Jr. (2013). The Joy of Factoring. American Mathematical Society. ISBN 978-1-4704-1048-3. 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

1. ↑ 1.0 1.1 "Computational Number Theory", The Princeton Companion to Mathematics (Princeton University Press), 2009, https://math.dartmouth.edu/~carlp/PDF/pcm0049.pdf
2. ↑ Algorithmic Number Theory, Volume 1: Efficient Algorithms. MIT Press. 1996. ISBN 0-262-02405-5.
3. ↑ A Course In Computational Algebraic Number Theory. Graduate Texts in Mathematics. 138. Springer-Verlag. 1993. doi:10.1007/978-3-662-02945-9. ISBN 0-387-55640-0.

## External links

* v
* t
* e

Number-theoretic algorithms

Primality tests|

* AKS
* APR
* Baillie–PSW
* Elliptic curve
* Pocklington
* Fermat
* Lucas
* Lucas–Lehmer
* Lucas–Lehmer–Riesel
* Proth's theorem
* Pépin's
* Quadratic Frobenius
* Solovay–Strassen
* Miller–Rabin

Prime-generating|

* Sieve of Atkin
* Sieve of Eratosthenes
* Sieve of Sundaram
* Wheel factorization

Integer factorization|

* Continued fraction (CFRAC)
* Dixon's
* Lenstra elliptic curve (ECM)
* Euler's
* Pollard's rho
* p − 1
* p \+ 1
* Quadratic sieve (QS)
* General number field sieve (GNFS)
* Special number field sieve (SNFS)
* Rational sieve
* Fermat's
* Shanks's square forms
* Trial division
* Shor's

Multiplication|

* Ancient Egyptian
* Long
* Karatsuba
* Toom–Cook
* Schönhage–Strassen
* Fürer's

Euclidean division|

* Binary
* Chunking
* Fourier
* Goldschmidt
* Newton-Raphson
* Long
* Short
* SRT

Discrete logarithm|

* Baby-step giant-step
* Pollard rho
* Pollard kangaroo
* Pohlig–Hellman
* Index calculus
* Function field sieve

Greatest common divisor|

* Binary
* Euclidean
* Extended Euclidean
* Lehmer's

Modular square root|

* Cipolla
* Pocklington's
* Tonelli–Shanks
* Berlekamp

Other algorithms|

* Chakravala
* Cornacchia
* Exponentiation by squaring
* Integer square root
* LLL
* Modular exponentiation
* Montgomery reduction
* Schoof's

* Italics indicate that algorithm is for numbers of special forms

* v
* t
* e

Topics in algebraic curves

Rational curves|

* Five points determine a conic
* Projective line
* Rational normal curve
* Riemann sphere
* Twisted cubic

Elliptic curves|

| Analytic theory|

* Elliptic function
* Elliptic integral
* Fundamental pair of periods
* Modular form

|

Arithmetic theory|

* Counting points on elliptic curves
* Division polynomials
* Hasse's theorem on elliptic curves
* Mazur's torsion theorem
* Modular elliptic curve
* Modularity theorem
* Mordell–Weil theorem
* Nagell–Lutz theorem
* Supersingular elliptic curve
* Schoof's algorithm
* Schoof–Elkies–Atkin algorithm

Applications|

* Elliptic curve cryptography
* Elliptic curve primality

Higher genus|

* De Franchis theorem
* Faltings's theorem
* Hurwitz's automorphisms theorem
* Hurwitz surface
* Hyperelliptic curve

Plane curves|

* AF+BG theorem
* Bézout's theorem
* Bitangent
* Cayley–Bacharach theorem
* Conic section
* Cramer's paradox
* Cubic plane curve
* Fermat curve
* Genus–degree formula
* Hilbert's sixteenth problem
* Nagata's conjecture on curves
* Plücker formula
* Quartic plane curve
* Real plane curve

Riemann surfaces|

* Belyi's theorem
* Bring's curve
* Bolza surface
* Compact Riemann surface
* Dessin d'enfant
* Differential of the first kind
* Klein quartic
* Riemann's existence theorem
* Riemann–Roch theorem
* Teichmüller space
* Torelli theorem

Constructions|

* Dual curve
* Polar curve
* Smooth completion

Structure of curves|

| Divisors on curves|

* Abel–Jacobi map
* Brill–Noether theory
* Clifford's theorem on special divisors
* Gonality of an algebraic curve
* Jacobian variety
* Riemann–Roch theorem
* Weierstrass point
* Weil reciprocity law

|

Moduli|

* ELSV formula
* Gromov–Witten invariant
* Hodge bundle
* Moduli of algebraic curves
* Stable curve

Morphisms|

* Hasse–Witt matrix
* Riemann–Hurwitz formula
* Prym variety
* Weber's theorem

Singularities|

* Acnode
* Crunode
* Cusp
* Delta invariant
* Tacnode

Vector bundles|

* Birkhoff–Grothendieck theorem
* Stable vector bundle
* Vector bundles on algebraic curves

* v
* t
* e

Number theory

Fields|

* Algebraic number theory
* Analytic number theory
* Geometric number theory
* Computational number theory
* Transcendental number theory
* Diophantine geometry
* Combinatorial number theory
* Arithmetic geometry
* Arithmetic topology
* Arithmetic dynamics

Key concepts|

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

Advanced concepts|

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

* Category
* List of topics
* List of recreational topics
* Wikibook
* Wikversity

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Computational number theory. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Computational_number_theory&oldid=3980459"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template