Théorie algébrique des nombres et calcul formel

Belabas, Karim

Journées Nationales de Calcul Formel. 14 – 18 Novembre 2011, Les cours du CIRM, no. 1 (2011), Exposé no. 1, 40 p.

La théorie algébrique des nombres est née du désir de résoudre certaines équations diophantiennes en nombres entiers (typiquement, l’équation de Fermat). Elle introduit et étudie des structures algébriques associées aux extensions algébriques de $\mathbb{Q}$ ou de ${𝔽}_q\left(t\right)$, en y retrouvant la trace des propriétés des entiers ordinaires, par exemple la factorisation unique en produit de nombres premiers, sous une forme affaiblie. Je motiverai l’introduction des objets correspondants (anneaux d’entiers, groupes de classes, unités, groupes de Galois, fonctions $L$), dans le cas des corps de nombres, et expliquerai comment les calculer en temps raisonnable. On citera des applications à la résolution algorithmique d’équations diophantiennes concrètes (équations aux normes, équations de Thue).

[1] L. M. Adleman & H. W. Lenstra, Jr., Finding irreducible polynomials over finite fields, 18th ACM Symposium on Theory of Computing (1986), pp. 350–355.

[2] M. Agrawal, N. Kayal, & N. Saxena, Primes is in P, Ann. of Math. (2) 160 (2004), no. 2, pp. 781–793.

[3] E. Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, pp. 355–380.

[4] E. Bach, Improved approximations for Euler products, in Number theory (Halifax, NS, 1994), Amer. Math. Soc., 1995, pp. 13–28.

[5] B. Beauzamy, Products of polynomials and a priori estimates for coefficients in polynomial decompositions : a sharp result, J. Symbolic Comput. 13 (1992), no. 5, pp. 463–472.

[6] K. Belabas, Topics in computational algebraic number theory, J. Théor. Nombres Bordeaux 16 (2004), no. 1, pp. 19–63.

[7] K. Belabas, L’algorithmique de la théorie algébrique des nombres, in Théorie algorithmique des nombres et équations diophantiennes, Ed. Éc. Polytech., Palaiseau, 2005, pp. 85–155.

[8] K. Belabas, M. van Hoeij, J. Klüners, & A. Steel, Factoring polynomials over global fields, preprint.

[9] E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), pp. 713–735.

[10] Y. Bilu & G. Hanrot, Solving Thue equations of high degree, J. Number Theory 60 (1996), no. 2, pp. 373–392.

[11] J. Buchmann & H. W. Lenstra, Jr., Approximating rings of integers in number fields, J. Théor. Nombres Bordeaux 6 (1994), no. 2, pp. 221–260.

[12] J. Buchmann, A subexponential algorithm for the determination of class groups and regulators of algebraic number fields, in Séminaire de Théorie des Nombres, Paris 1988–1989, Progr. Math., vol. 91, Birkhäuser, 1990, pp. 27–41.

[13] P. Bürgisser, M. Clausen, & M. A. Shokrollahi, Algebraic complexity theory, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 315, Springer-Verlag, Berlin, 1997, With the collaboration of Thomas Lickteig.

[14] A. L. Chistov, The complexity of the construction of the ring of integers of a global field, Dokl. Akad. Nauk SSSR 306 (1989), no. 5, pp. 1063–1067.

[15] H. Cohen & H. W. Lenstra, Jr., Heuristics on class groups of number fields, in Number theory, Noordwijkerhout 1983 (Berlin), Lecture Notes in Math., vol. 1068, Springer, Berlin, 1984, pp. 33–62.

[16] H. Cohen & J. Martinet, Études heuristiques des groupes de classes des corps de nombres, J. reine angew. Math. 404 (1990), pp. 39–76.

[17] H. Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993.

[18] R. Crandall & C. Pomerance, Prime numbers, second ed., Springer, New York, 2005, A computational perspective.

[19] H. Davenport & H. Heilbronn, On the density of discriminants of cubic fields (ii), Proc. Roy. Soc. Lond. A 322 (1971), pp. 405–420.

[20] Demailly, Analyse numérique et équations différentielles, Presses Universitaires de Grenoble, 1996.

[21] J.-G. Dumas, B. D. Saunders, & G. Villard, On efficient sparse integer matrix Smith normal form computations, J. Symbolic Comput. 32 (2001), no. 1-2, pp. 71–99, Computer algebra and mechanized reasoning (St. Andrews, 2000).

[22] J. Ellenberg & A. Venkatesh, The number of extensions of a number field with fixed degree and bounded discriminant, Annals of Math, à paraître.

[23] C. Fieker, Computing class fields via the Artin map, Math. Comp. 70 (2001), no. 235, pp. 1293–1303.

[24] D. Ford, S. Pauli, & X.-F. Roblot, A fast algorithm for polynomial factorization over ${\mathbb{Q}}_p$, J. Théor. Nombres Bordeaux 14 (2002), no. 1, pp. 151–169.

[25] X. Gourdon, Algorithmique du théorème fondamental de l’algèbre, Rapport de recherche 1852, INRIA, 1993.

[26] J. L. Hafner & K. S. McCurley, A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc. 2 (1989), no. 4, pp. 837–850.

[27] G. Hanrot, Quelques idées sur l’algorithmique des équations diophantiennes, in Théorie algorithmique des nombres et équations diophantiennes, Ed. Éc. Polytech., Palaiseau, 2005, pp. 157–185.

[28] H. Hasse, Zahlentheorie, Akademie-Verlag GmbH, 1949.

[29] P. Henrici, Applied and computational complex analysis, Wiley-Interscience [John Wiley & Sons], New York, 1974, Volume 1 : Power series—integration—conformal mapping—location of zeros, Pure and Applied Mathematics.

[30] J. C. Lagarias, H. L. Montgomery, & A. M. Odlyzko, A bound for the least prime ideal in the Chebotarev density theorem, Invent. Math. 54 (1979), no. 3, pp. 271–296.

[31] J. C. Lagarias & A. M. Odlyzko, Effective versions of the Chebotarev density theorem, in Algebraic number fields : $L$-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) (London), Academic Press, London, 1977, pp. 409–464.

[32] S. Lang, Algebraic number theory, second ed., Graduate Texts in Mathematics, vol. 110, Springer-Verlag, New York, 1994.

[33] A. K. Lenstra & H. W. Lenstra, Jr. (eds.), The development of the number field sieve, Lecture Notes in Math., vol. 1554, Springer-Verlag, Berlin, 1993.

[34] A. K. Lenstra, H. W. Lenstra, Jr., & L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, pp. 515–534.

[35] H. W. Lenstra, Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc. (N.S.) 26 (1992), no. 2, pp. 211–244.

[36] M. Mignotte, An inequality about factors of polynomials, Math. Comp. 28 (1974), pp. 1153–1157.

[37] A. Novocin, D. Stehlé, & G. Villard, An lll-reduction algorithm with quasi-linear time complexity, 2011, In Proceedings of STOC, pp. 403–412, version complète http://perso.ens-lyon.fr/damien.stehle/L1.html.

[38] J. Oesterlé, Le problème de gauss sur le nombre de classes, Enseign. Math. 34 (1988), pp. 43–67.

[39] C. H. Papadimitriou, Computational complexity, Addison-Wesley, 1994.

[40] C. Pernet & W. Stein, Fast computation of Hermite normal forms of random integer matrices, J. Number Theory 130 (2010), no. 7, pp. 1675–1683.

[41] F. Rouillier & P. Zimmermann, Efficient isolation of polynomial real roots, Journal of Computational and Applied Mathematics 162 (2003), no. 1, pp. 33–50.

[42] R. Schoof, Four primality algorithms, à paraître, http://www.mat.uniroma2.it/~schoof/millerrabinpom.pdf.

[43] R. Schoof, Computing Arakelov class groups, in Algorithmic number theory : lattices, number fields, curves and cryptography (Cambridge), Math. Sci. Res. Inst. Publ., vol. 44, Cambridge Univ. Press, Cambridge, 2008, pp. 447–495.

[44] S. Siksek, The modular approach to diophantine equations, preprint, http://igd.univ-lyon1.fr/~webeuler/ihp/LectureNotes_Siksek.dvi.

[45] P. Stevenhagen & H. W. Lenstra, Jr., Chebotarëv and his density theorem., Math. Intell. 18 (1996), no. 2, pp. 26–37.

[46] P. Stevenhagen, The arithmetic of number rings, in Algorithmic number theory : lattices, number fields, curves and cryptography (Cambridge), Math. Sci. Res. Inst. Publ., vol. 44, Cambridge Univ. Press, Cambridge, 2008, pp. 209–266.

[47] A. Storjohann, Algorithms for matrix canonical forms, Ph.D. thesis, ETH Zurich, 2000, http://www.cs.uwaterloo.ca/~astorjoh/dissA4.ps.

[48] T. Taniguchi & F. Thorne, Secondary terms in counting functions for cubic fields, 2011.

[49] N. Tzanakis & B. M. M. de Weger, On the practical solution of the Thue equation, J. Number Theory 31 (1989), no. 2, pp. 99–132.

[50] M. van Hoeij, Factoring polynomials and the knapsack problem, J. Number Theory 95 (2002), no. 2, pp. 167–189.

[51] J. von zur Gathen & J. Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999.