Abstract
A survey of computational number theory viewed through the prism of my own experience and the Pari/GP software.
For Catriona Byrne, with thanks
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
M. Agrawal, N. Kayal, and N. Saxena. PRIMES is in P. Ann. Math.160, 781–793 (2004).
P. Akhilesh. Double tails of multiple zeta values. J. Number Theory170, 228–249 (2017).
Algorithmic Number Theory Symposia I to IX. Lecture Notes in Computer Science 877 (1994), 1122 (1996), 1423 (1998), 1838 (2000), 2369 (2002), 3076 (2004), 4076 (2006), 5011 (2008), 6197 (2010), Springer-Verlag; X, XIII, and XIV, Open Book Series 1 (2012), 2 (2018), 4 (2020), XI and XII, J. of Computation and Math.17A (2014), 19A (2016), London Math. Soc.
B. Allombert. An efficient algorithm for the computation of Galois automorphisms. Math. Comp.73, 359–375 (2001).
B. Allombert. Explicit computation of isomorphisms between finite fields. Finite Fields Appl.8, 332–342 (2002).
T. Anderson et al., Improved bounds on number fields of small degree, arXiv:2204.01651 (2022).
J. Arias de Reyna. High precision computation of Riemann’s zeta function by the Riemann–Siegel formula, I. Math. Comp.80 (2011), 995–1009, and II, arXiv:2201.00342 (2022).
O. Atkin and J. Lehner. Hecke operators on Γ0(m). Math. Annalen185, 134–160 (1970).
O. Atkin and F. Morain. Elliptic curves and primality proving. Math. Comp.61, 29–68 (1993).
O. Atkin and P. Swinnerton-Dyer. Modular forms on congruence subgroups. Proc. Sympos. Pure Math. 19, American Math. Soc. 1–25 (1971).
A. Baily. On the density of discriminants of quartic fields. J. reine angew. Math.315, 190–210 (1980).
R. Balasubramanian, J.-M. Deshouillers and F. Dress. Problème de Waring pour les bicarrés. I. Comptes Rendus Acad. Sci Paris303 85–88, and II 161–163 (1986).
A. Bartel, H. Johnston and H. W. Lenstra, Jr. Galois module structure of oriented Arakelov class groups. arXiv:2005.11533 (2020).
F. Beukers, H. Cohen and A. Mellit. Finite hypergeometric functions. Pure Appl. Math. Q.11, 559–589 (2015).
K. Belabas. A fast algorithm to compute cubic fields. Math. Comp.66, 1213–1237 (1997).
K. Belabas. A relative van Hoeij algorithm over number fields. J. Symbolic Computation37, 641–668 (2004).
K. Belabas and H. Cohen. Modular forms in Pari/GP. In: Research in the Math. Sciences5, Springer, 46–64 (2018).
K. Belabas and H. Cohen. Numerical Algorithms for Number Theory Using Pari/GP. Math. surveys and monographs 254, American Math. Soc. (2021).
K. Belabas, F. Diaz y Diaz and E. Friedman. Small generators of the ideal class group. Math. Comp.77, 1185–1197 (2008).
K. Belabas and B. Perrin-Riou. Overconvergent modular symbols and p-adic L-functions. arXiv:2101.06960 (2021).
K. Belabas, M. Van Hoeij, J. Klüners and A. Steel. Factoring polynomials over global fields. J. Théor. Nombres Bordeaux21, 15–39 (2009).
M. Bhargava. Higher composition laws I, II, III, and IV. Ann. Math.159, 217–250, 865–886, 1329–1360 (2004) and 172, 1559–1591 (2010).
M. Bhargava. The density of discriminants of quartic rings and fields. Ann. Math.162, 1031–1063 (2005).
M. Bhargava. The density of discriminants of quintic rings and fields. Ann. Math.172, 1559–1591 (2010).
M. Bhargava, A. Shankar, T. Taniguchi, F. Thorne, J. Tsimerman and Y. Zhao. Bounds on 2-torsion in class groups of number fields and integral points on elliptic curves. J. Amer. Math. Soc.33, 1087–1099 (2020).
M Bhargava, A. Shankar, and X. Wang, An improvement on Schmidt’s bound on the number of number fields of bounded discriminant and small degree, arXiv:2204.01331 (2022).
Y. Bilu and G. Hanrot. Solving Thue equations of high degree. J. Number Theory60, 373–392 (1996).
B. Birch and P. Swinnerton-Dyer. Notes on elliptic curves I and II. J. reine angew. Math.212, 7–25 (1963), 218, 79–108 (1965).
B. Birch and W. Kuyk (eds). Modular forms in one variable IV. Lecture Notes in Math. 476, Springer-Verlag (1975).
A. Booker. Artin’s conjecture, Turing’s method, and the Riemann hypothesis. Experiment. Math.15, 385–407 (2006).
A. Booker, A. Strömbergsson and A. Venkatesh. Effective computation of Maass cusp forms. Int. Math. Res. Not., Art. ID 71281, 34 (2006).
W. Bosma, J. Cannon and C. Playoust. The Magma algebra system I. The user language. J. Symbolic Comput.24, 235–265 (1997).
J. Buchmann. On the computation of units and class numbers by a generalization of Lagrange’s algorithm. J. Number Theory26, 8–30(1987).
J. Buchmann, C. Thiel and H. Williams. Short representations of quadratic integers. In: Math. and its applications325, Kluwer, 159–185 (1995).
J. Buhler. Icosahedral Galois representations. Lecture Notes in Math. 654, Springer–Verlag (1978).
A. Brumer and K. Kramer. Paramodular abelian varieties of odd conductor. Trans. Amer. Math. Soc.366, 2463–2516 (2014).
H. Cohen. A Course in Computational Algebraic Number Theory (fourth corrected printing). Graduate Texts in Math. 138, Springer-Verlag (2000).
H. Cohen. Advanced Topics in Computational Number Theory. Graduate Texts in Math. 193, Springer-Verlag (2000).
H. Cohen. Number Theory I, Tools and Diophantine Equations. Graduate Texts in Math. 239, Springer-Verlag (2007).
H. Cohen. Number Theory II, Analytic and Modern Tools. Graduate Texts in Math. 240, Springer-Verlag (2007).
H. Cohen. Computing L-functions: A survey. J. Th. Nombres Bordeaux27, 699–726 (2015).
H. Cohen. Computational number theory in relation with L-functions. In: I. Inam and E. Büyükaşik (eds.), International Autumn School on Computational Number Theory, 171–266, Birkhäuser (2019).
H. Cohen, F. Diaz y Diaz and M. Olivier. Computing ray class groups, conductors, and discriminants., Math. Comp.67, 773–795 (1998).
H. Cohen, F. Diaz y Diaz and M. Olivier. A table of totally complex number fields of small discriminant. In: Proceedings ANTS XIII, Lecture Notes in Computer Science 1423, Springer-Verlag, 381–391 (1998).
H. Cohen, F. Diaz y Diaz and M. Olivier. Enumerating quartic dihedral extensions of \({\mathbb Q}\). Compositio Math.133, 65–93 (2002).
H. Cohen, F. Diaz y Diaz and M. Olivier. Constructing complete tables of quartic fields using Kummer theory. Math. Comp.72, 941–951 (2003).
H. Cohen and G. Frey (eds). Handbook of elliptic and elliptic and hyperelliptic curve cryptography. CRC Press (2006).
H. Cohen and H.W. Lenstra, Jr. Primality testing and Jacobi sums. Math. Comp.42, 297–330 (1984).
H. Cohen and A.K. Lenstra. Implementation of a new primality test. Math. Comp.48, 103–121 and S1–S4 (1987).
H. Cohen and H.W. Lenstra, Jr. Heuristics on class groups of number fields. Lecture Notes in Math. 1068, 33–62, Springer-Verlag (1984).
H. Cohen and J. Martinet. Étude heuristique des groupes de classes des corps de nombres. J. für die reine und angew. Math.404, 39–76 (1990).
H. Cohn. The density of abelian cubic fields. Proc. Amer. Math. Soc.5, 476–477 (1954).
D. Corwin. From Chabauty’s method to Kim’s non-abelian Chabauty’s method. Unpublished manuscript, 41 pp, (2021).
J.-M. Couveignes. Enumerating number fields. Ann. Math.192, 487–497 (2020) and arXiv:1907.13617 (2019).
J. Cremona. Hyperbolic tessellations, modular symbols, and elliptic curves over complex quadratic fields. Compositio Math.51, 275–324 (1984).
J. Cremona. Algorithms for modular elliptic curves (2nd ed.) Cambridge Univ. Press (1997).
J. Cremona. The L-functions and modular forms database project. Found. Comp. Math.16, 1541–1553 (2016).
H. Davenport and H. Heilbronn. On the density of discriminants of cubic fields I. Bull. London Math. Soc.1, 345–348 (1969), and II, Proc. Royal Soc. A322, 405–420 (1971).
L. Dembélé and J. Voight. Explicit methods for Hilbert modular forms. In: Elliptic curves, Hilbert modular forms, and Galois deformations, 135–198, Birkhäuser (2013).
J.-M. Deshouillers, F. Hennecart and B. Landreau. Waring’s problem for sixteen biquadrates - Numerical results. J. Th. Nombres Bordeaux12, 411–422 (2000).
T. Dokchitser. Computing special values of motivic L-functions. Exp. Math.13, 137–149 (2004).
B. Edixhoven and J.-M. Couveignes (eds.) Computational aspects of modular forms and Galois representations. Annals of Math. Studies 176, Princeton Univ. Press (2011).
N. Elkies. Elliptic and modular curves over finite fields and related computational issues. In: Computational perspectives in number theory7, 21–76, American Math. Soc. (1998).
N. Elkies. Three lectures on elliptic surfaces and curves of high rank. arXiv:0709.2908 (2007).
J. Ellenberg and A. Venkatesh. Reflection principles and bounds for class group torsion. Int. Math. Res. Not.1 (2007).
A. Enge. Computing modular polynomials in quasi-linear time. Math. Comp.78, 1809–1824 (2009).
A. Enge and F. Johansson. paritwine 0.1. INRIA (2019). https://www.multiprecision.org/paritwine/.
A. Enge and A. Sutherland. Class invariants by the CRT method. In: Proceedings ANTS IX, Lecture Notes in Comp. Science 6197, 142–156 (2010).
D. Farmer, S. Koutsioliotas and S. Lemurell. Maass forms on \( \operatorname {\mathrm {GL}}(3)\) and \( \operatorname {\mathrm {GL}}(4)\)., Int. research notices22 and arXiv:1212.4544 (2012).
K. Fischer. The Zetafast algorithm for computing zeta functions. arXiv:1703.01414v7 (2017).
F. Fité, K. Kedlaya and A. Sutherland. Sato–Tate groups of abelian threefolds: a preview of the classification. Contemp. Math.770, 103–129 (2021).
E. Fouvry and J. Klüners. On the 4-rank of class groups of quadratic number fields. Invent. Math.167, 455–513 (2007).
F. Gerth. The 4-class ranks of quadratic fields. Invent. Math.77, 489–515 (1984).
D. Goldfeld. Gauss’ class number problem for imaginary quadratic fields. Bull. Amer. Math. Soc.13, 23–37 (1985).
X. Gourdon. Algorithmique du théorème fondamental de l’algèbre. Rapport de recherche 1852 INRIA (1993).
L. Grenié and G. Molteni. Explicit versions of the prime ideal theorem for Dedekind zeta functions under GRH. Math. Comp.85, 889–906 (2016).
J. Hafner and K. McCurley. A rigorous subexponential algorithm for computation of class groups. J. American Math. Soc.2, 837–850 (1989).
D. Harvey. Counting points on hyperelliptic curves in average polynomial time. Ann. Math.179, 783–803 (2014).
D. Harvey. Computing zeta functions of arithmetic schemes. Proc. London Math. Soc.111, 1379–1401 (2015).
D. Harvey and J. van der Hoeven. Integer multiplication in time \(O(n\log (n))\). Annals of Math.193, 563–617 (2021).
D. Hejhal. The Selberg trace formula for\( \operatorname {\mathrm {PSL}}_2({\mathbb R})\). I and II, Lecture Notes in Math. 548 and 1001, Springer-Verlag (1976 and 1983).
H. Helfgott. The ternary Goldbach problem. arXiv:1501.05438v2 (2015).
F. Johansson. Arb: efficient arbitrary-precision midpoint-radius interval arithmetic. IEEE Trans. on Computers66, 1281–1292 (2017).
C. Jeannerod, C. Pernet and A. Storjohann. Rank-profile revealing Gaussian elimination and the CUP matrix decomposition. J. Symbolic Comput.56, 46–68 (2013).
K. Kedlaya. Counting points on hyperelliptic curves using Monsky–Washnitzer cohomology. J. Ramanujan Math. Soc.16, 318–330 (2001) and 18, 417–418 (2003).
K. Khuri-Makdisi. Asymptotically fast group operations on Jacobians of general curves. Math. Comp.76, 2213–2239 (2007).
D.H. Lehmer. Factorization of certain cyclotomic functions. Ann. Math. (2)34, 461–479 (1933).
R. Lemke Oliver and F. Thorne. Upper bounds on number fields of given degree and bounded discriminant. arXiv:2005.14110v2 (2020).
H.W. Lenstra, Jr. Factoring integers with elliptic curves. Annals of Math.126, 649–673 (1987).
A.K. Lenstra and H.W. Lenstra, Jr. (eds.) The development of the number field sieve. Lecture Notes in Math. 1554, Springer-Verlag (1993).
A.K. Lenstra, H.W. Lenstra, Jr. and L. Lovász. Factoring polynomials with rational coefficients. Math. Ann.261, 515–534 (1982).
H.W. Lenstra and R. Tijdeman (eds). Computational methods in number theory. Math. Center Tracts 154/155, Math. Centrum Amsterdam (1982).
The LMFDB collaboration. The L-function and modular form database. http://www.lmfdb.org and http://beta.lmfdb.org.
Q. Liu. Modèles minimaux des courbes de genre deux. J. für die reine und angew. Math.453, 137–164 (1994).
W. McCallum and B. Poonen. The method of Chabauty and Coleman. In: Panoramas et synthèses36, Soc. Math. de France, 99–117 (2012).
S. Mäki. The conductor density of abelian number fields. J. London Math. Soc. (2) 47, 18–30 (1993).
G. Malle. On the distribution of Galois groups I., J. Number Theory92, 315–322 (2002), and II., Exp. Math.13, 129–135 (2004).
J.-F. Mestre. Unpublished, but see Section 17.3.2.b in [47].
P. Molin and A. Page. Computing groups of Hecke characters. arXiv:2210.02716.
P. Nguyen and D. Stehlé. Floating-point LLL revisited. In: Proceedings Eurocrypt ’2005, Springer-Verlag (2005).
P. Nguyen and B. Vallée (eds). The LLL algorithm: Survey and applications. Information Security and Cryptography, Springer (2010).
A. Odlyzko. Bounds for discriminants and related estimates for class numbers, regulators, and zeros of zeta functions: a survey of recent results. J. Th. Nombres Bordeaux2, 114–141 (1990).
A. Odlyzko and A. Schönhage. Fast algorithms for multiple evaluations of the Riemann zeta function. Trans. Amer. Math. Soc.309, 797–809 (1988).
The PARI Group. PARI/GPversion 2.15.1. Univ. Bordeaux (2022). http://pari.math.u-bordeaux.fr/.
W. Plesken and B. Souvignier. Computing isometries of lattices. J. Symbolic Comp.24, 327–334 (1997).
M. Pohst and H. Zassenhaus. Algorithmic algebraic number theory (3rd ed.) Cambridge Univ. Press (1993).
R. Pollack and G. Stevens. Overconvergent modular symbols and p-adic L-functions. Ann. Sci. ENS44, 1–42 (2011).
C. Pomerance. The quadratic sieve factoring algorithm. In: EUROCRYPT, Lecture Notes in Comp. Science 209, 169–182, Springer-Verlag (1984).
A. Pethö, M. Pohst, H. Williams and H. Zimmer (eds). Computational number theory, Walter de Gruyter (1991).
B. Poonen. Heuristics for the arithmetic of elliptic curves. arXiv:1711.10112v2 (2017).
B. Poonen and E. Rains. Random maximal isotropic subspaces and Selmer groups. J. Amer. Math. Soc.25, 245–269 (2012).
C. Poor and D. Yuen. Paramodular cusp forms. Math. Comp.84, 1401–1438 (2015).
D. Roberts and F. Rodriguez-Villegas. Hypergeometric motives. arXiv:2109.00027 (2021).
The Sage Developers. SageMath, the Sage Mathematics Software System version 9.7 (2022). https://www.sagemath.org.
T. Satoh. The canonical lift of an ordinary elliptic curve over a finite field and its point counting. J. Ramanujan Math. Soc.15, 247–270 (2000).
R. Schoof. Elliptic curves over finite fields and the computation of square roots mod p. Math. Comp.44, 483–494 (1985).
D. Shanks. Class number, a theory of factorization, and genera. In: Proc. Sympos. Pure Math.20, 415–440, American Math. Soc. (1971).
P. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. arXiv:quant-ph/9508027v2 (1996).
C.-L. Siegel. Contributions to the theory of the Dirichlet L-series and the Epstein zeta-functions. Ann. of Math. (2)44, 143–172 (1943).
A. Silvester, M. Jacobson and H. Williams. Shorter compact representations in real quadratic fields. In: Number Theory and Cryptography, Lecture Notes in Computer Science 8260, 50–72 (2013).
N. Smart. The algorithmic resolution of Diophantine equations. London Math. Soc. student texts 41 (1998).
A. Smith. 2∞-Selmer groups, 2∞-class groups, and Goldfeld’s conjecture. arXiv:1702.02325v2 (2017).
C. Smyth. The Mahler measure of algebraic numbers: a survey. In: J. McKee and C. Smyth (eds.), Number theory and polynomials, 322–349, Cambridge Univ. Press (2008).
H. Stark. L-functions at s = 1 I, II, III, IV. Adv. Math.7, 301–343 (1971), 17, 60–92 (1975), 22, 64–84 (1976), 35, 197–235 (1980).
H. Stark. Fourier coefficients of Maass waveforms. In: Modular forms, R. Rankin ed., 263–269, Ellis Horwood (1984).
W. Stein. Modular forms, a computational approach. Graduate Studies in Math. 79, American Math. Soc. (2007).
M. Stoll, Documentation for the ratpoints program, arXiv:0803.3165v5 (2022).
A. Sutherland. Computing Hilbert class polynomials with the Chinese remainder theorem. Math. Comp.80, 501–538 (2011).
A. Sutherland. On the evaluation of modular polynomials. In: Proceedings ANTS X, 531–555, Open Book Series 1, msp (2013).
A. Sutherland. Sato–Tate distributions. Contemp. Math.740, 197–248 (2019).
A. Sutherland. Counting points on superelliptic curves in average polynomial time. In: Proceedings ANTS XIV, 403–422, Open Book Series 4, msp (2020), or arXiv:2004.10189v4.
D. Tingley. Elliptic curves uniformized by modular functions. Ph.D. thesis, Univ. of Oxford (1975).
A. Turing. Some calculations of the Riemann zeta-function. Proc. London Math. Soc.3, 99–117 (1953).
W. Wang and M. Matchett Wood. Moments and interpretations of the Cohen–Lenstra–Martinet heuristics. arXiv:1907.11201v2 (2020).
M. Watkins. Some remarks on Heegner point computations. In: Panoramas et synthèses36, 81–97, Soc. Math. de France (2012).
M. Watkins. A discursus on 21 as a bound for ranks of elliptic curves over \({\mathbb Q}\), and sundry related topics. http://magma.maths.usyd.edu.au/~watkins/papers/DISCURSUS.pdf (2015).
M. Watkins. Class numbers of imaginary quadratic fields. Math. Comp.73, 907–938 (2004).
A.-E. Wilke. Thesis, in preparation.
S. Wong. Densities of quartic fields with even Galois groups. Proc. Amer. Math. Soc.133, 2873–2881 (2005).
H. Zimmer. Computational problems, methods, and results in algebraic number theory. Lecture Notes in Math. 262, Springer–Verlag (1972).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this chapter
Cite this chapter
Cohen, H. (2023). Computational Number Theory, Past, Present, and Future. In: Morel, JM., Teissier, B. (eds) Mathematics Going Forward . Lecture Notes in Mathematics, vol 2313. Springer, Cham. https://doi.org/10.1007/978-3-031-12244-6_38
Download citation
DOI: https://doi.org/10.1007/978-3-031-12244-6_38
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-12243-9
Online ISBN: 978-3-031-12244-6
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)