Centre de diffusion de revues académiques mathématiques

 
 
 
 

Les cours du CIRM

Table des matières de ce fascicule | Article précédent | Article suivant
Karim Belabas
Théorie algébrique des nombres et calcul formel
Les cours du CIRM, 2 no. 1: Journées Nationales de Calcul Formel (2011), Exp. No. 1, 40 p., doi: 10.5802/ccirm.13
Article PDF

Résumé - Abstract

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 ${\mathbb{F}}_q(t)$, 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).

Bibliographie

[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.  MR 2123939 |  Zbl 1071.11070
[3] E. Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, pp. 355–380.  MR 1023756 |  Zbl 0701.11075
[4] E. Bach, Improved approximations for Euler products, in Number theory (Halifax, NS, 1994), Amer. Math. Soc., 1995, pp. 13–28.  MR 1353917 |  Zbl 0842.11046
[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.  MR 1170091 |  Zbl 0757.30002
[6] K. Belabas, Topics in computational algebraic number theory, J. Théor. Nombres Bordeaux 16 (2004), no. 1, pp. 19–63. Cedram |  MR 2145572 |  Zbl 1078.11071
[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.  MR 2224342 |  Zbl 1121.11080
[8] K. Belabas, M. van Hoeij, J. Klüners, & A. Steel, Factoring polynomials over global fields, preprint.  MR 2537701
[9] E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), pp. 713–735.  MR 276200 |  Zbl 0247.12014
[10] Y. Bilu & G. Hanrot, Solving Thue equations of high degree, J. Number Theory 60 (1996), no. 2, pp. 373–392.  MR 1412969 |  Zbl 0867.11017
[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. Cedram |  MR 1360644 |  Zbl 0828.11075
[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.  MR 1104698 |  Zbl 0727.11059
[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.  MR 1440179 |  Zbl 1087.68568
[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.  MR 1014763 |  Zbl 0698.12001
[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.  MR 756082 |  Zbl 0558.12002
[16] H. Cohen & J. Martinet, Études heuristiques des groupes de classes des corps de nombres, J. reine angew. Math. 404 (1990), pp. 39–76.  MR 1037430 |  Zbl 0699.12016
[17] H. Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993.  MR 1228206 |  Zbl 0786.11071
[18] R. Crandall & C. Pomerance, Prime numbers, second ed., Springer, New York, 2005, A computational perspective.  MR 2156291 |  Zbl 1088.11001
[19] H. Davenport & H. Heilbronn, On the density of discriminants of cubic fields (ii), Proc. Roy. Soc. Lond. A 322 (1971), pp. 405–420.  MR 491593 |  Zbl 0212.08101
[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).  MR 1840386 |  Zbl 1050.65044
[22] J. Ellenberg & A. Venkatesh, The number of extensions of a number field with fixed degree and bounded discriminant, Annals of Math, à paraître.  Zbl 1099.11068
[23] C. Fieker, Computing class fields via the Artin map, Math. Comp. 70 (2001), no. 235, pp. 1293–1303.  MR 1826583 |  Zbl 0982.11074
[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. Cedram |  MR 1925995 |  Zbl 1032.11053
[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.  MR 1002631 |  Zbl 0702.11088
[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.  MR 2224343 |  Zbl 1119.11025
[28] H. Hasse, Zahlentheorie, Akademie-Verlag GmbH, 1949.  MR 34400 |  Zbl 0035.02002
[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.  MR 372162 |  Zbl 0313.30001
[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.  MR 553223 |  Zbl 0401.12014
[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.  MR 447191 |  Zbl 0362.12011
[32] S. Lang, Algebraic number theory, second ed., Graduate Texts in Mathematics, vol. 110, Springer-Verlag, New York, 1994.  MR 1282723 |  Zbl 0811.11001
[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.  MR 1321217 |  Zbl 0806.11065
[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.  MR 682664 |  Zbl 0488.12001
[35] H. W. Lenstra, Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc. (N.S.) 26 (1992), no. 2, pp. 211–244. arXiv |  MR 1129315 |  Zbl 0759.11046
[36] M. Mignotte, An inequality about factors of polynomials, Math. Comp. 28 (1974), pp. 1153–1157.  MR 354624 |  Zbl 0299.12101
[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.  MR 960192 |  Zbl 0668.12005
[39] C. H. Papadimitriou, Computational complexity, Addison-Wesley, 1994.  MR 1251285 |  Zbl 0833.68049
[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.  MR 2645245 |  Zbl 1206.15027
[41] F. Rouillier & P. Zimmermann, Efficient isolation of polynomial real roots, Journal of Computational and Applied Mathematics 162 (2003), no. 1, pp. 33–50.  MR 2043496 |  Zbl 1040.65041
[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.  MR 2467554 |  Zbl 1188.11076
[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.  MR 1395088 |  Zbl 0885.11005
[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.  MR 2467548 |  Zbl 1216.11099
[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.  MR 987566 |  Zbl 0657.10014
[50] M. van Hoeij, Factoring polynomials and the knapsack problem, J. Number Theory 95 (2002), no. 2, pp. 167–189.  MR 1924096 |  Zbl 1081.11080
[51] J. von zur Gathen & J. Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999.  MR 1689167 |  Zbl 1055.68168
Copyright Cellule MathDoc 2017 | Crédit | Plan du site