Théorie algébrique des nombres et calcul formel

Karim Belabas[1]

  • [1] Université Bordeaux 1 351 cours de la Libération F-33405 Talence, France

Les cours du CIRM (2011)

  • Volume: 2, Issue: 1, page 1-40
  • ISSN: 2108-7164

Abstract

top
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 ℚ ou de 𝔽 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).

How to cite

top

Belabas, Karim. "Théorie algébrique des nombres et calcul formel." Les cours du CIRM 2.1 (2011): 1-40. <http://eudml.org/doc/219728>.

@article{Belabas2011,
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).},
affiliation = {Université Bordeaux 1 351 cours de la Libération F-33405 Talence, France},
author = {Belabas, Karim},
journal = {Les cours du CIRM},
language = {fre},
number = {1},
pages = {1-40},
publisher = {CIRM},
title = {Théorie algébrique des nombres et calcul formel},
url = {http://eudml.org/doc/219728},
volume = {2},
year = {2011},
}

TY - JOUR
AU - Belabas, Karim
TI - Théorie algébrique des nombres et calcul formel
JO - Les cours du CIRM
PY - 2011
PB - CIRM
VL - 2
IS - 1
SP - 1
EP - 40
AB - 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).
LA - fre
UR - http://eudml.org/doc/219728
ER -

References

top
  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. Zbl1071.11070MR2123939
  3. E. Bach, Explicit bounds for primality testing and related problems, Math. Comp.55 (1990), no. 191, pp. 355–380. Zbl0701.11075MR1023756
  4. E. Bach, Improved approximations for Euler products, in Number theory (Halifax, NS, 1994), Amer. Math. Soc., 1995, pp. 13–28. Zbl0842.11046MR1353917
  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. Zbl0757.30002MR1170091
  6. K. Belabas, Topics in computational algebraic number theory, J. Théor. Nombres Bordeaux16 (2004), no. 1, pp. 19–63. Zbl1078.11071MR2145572
  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. Zbl1121.11080MR2224342
  8. K. Belabas, M. van Hoeij, J. Klüners, & A. Steel, Factoring polynomials over global fields, preprint. Zbl1254.11116MR2537701
  9. E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp.24 (1970), pp. 713–735. Zbl0247.12014MR276200
  10. Y. Bilu & G. Hanrot, Solving Thue equations of high degree, J. Number Theory60 (1996), no. 2, pp. 373–392. Zbl0867.11017MR1412969
  11. J. Buchmann & H. W. Lenstra, Jr., Approximating rings of integers in number fields, J. Théor. Nombres Bordeaux6 (1994), no. 2, pp. 221–260. Zbl0828.11075MR1360644
  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. Zbl0727.11059MR1104698
  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. Zbl1087.68568MR1440179
  14. A. L. Chistov, The complexity of the construction of the ring of integers of a global field, Dokl. Akad. Nauk SSSR306 (1989), no. 5, pp. 1063–1067. Zbl0698.12001MR1014763
  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. Zbl0558.12002MR756082
  16. H. Cohen & J. Martinet, Études heuristiques des groupes de classes des corps de nombres, J. reine angew. Math.404 (1990), pp. 39–76. Zbl0699.12016MR1037430
  17. H. Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. Zbl0786.11071MR1228206
  18. R. Crandall & C. Pomerance, Prime numbers, second ed., Springer, New York, 2005, A computational perspective. Zbl1088.11001MR2156291
  19. H. Davenport & H. Heilbronn, On the density of discriminants of cubic fields (ii), Proc. Roy. Soc. Lond. A322 (1971), pp. 405–420. Zbl0212.08101MR491593
  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). Zbl1050.65044MR1840386
  22. J. Ellenberg & A. Venkatesh, The number of extensions of a number field with fixed degree and bounded discriminant, Annals of Math, à paraître. Zbl1099.11068
  23. C. Fieker, Computing class fields via the Artin map, Math. Comp.70 (2001), no. 235, pp. 1293–1303. Zbl0982.11074MR1826583
  24. D. Ford, S. Pauli, & X.-F. Roblot, A fast algorithm for polynomial factorization over ℚ p , J. Théor. Nombres Bordeaux14 (2002), no. 1, pp. 151–169. Zbl1032.11053MR1925995
  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. Zbl0702.11088MR1002631
  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. Zbl1119.11025MR2224343
  28. H. Hasse, Zahlentheorie, Akademie-Verlag GmbH, 1949. Zbl0035.02002MR34400
  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. Zbl0313.30001MR372162
  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. Zbl0401.12014MR553223
  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. Zbl0362.12011MR447191
  32. S. Lang, Algebraic number theory, second ed., Graduate Texts in Mathematics, vol. 110, Springer-Verlag, New York, 1994. Zbl0811.11001MR1282723
  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. Zbl0806.11065MR1321217
  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. Zbl0488.12001MR682664
  35. H. W. Lenstra, Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc. (N.S.)26 (1992), no. 2, pp. 211–244. Zbl0759.11046MR1129315
  36. M. Mignotte, An inequality about factors of polynomials, Math. Comp.28 (1974), pp. 1153–1157. Zbl0299.12101MR354624
  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. Zbl1288.68294
  38. J. Oesterlé, Le problème de gauss sur le nombre de classes, Enseign. Math.34 (1988), pp. 43–67. Zbl0668.12005MR960192
  39. C. H. Papadimitriou, Computational complexity, Addison-Wesley, 1994. Zbl0833.68049MR1251285
  40. C. Pernet & W. Stein, Fast computation of Hermite normal forms of random integer matrices, J. Number Theory130 (2010), no. 7, pp. 1675–1683. Zbl1206.15027MR2645245
  41. F. Rouillier & P. Zimmermann, Efficient isolation of polynomial real roots, Journal of Computational and Applied Mathematics162 (2003), no. 1, pp. 33–50. Zbl1040.65041MR2043496
  42. R. Schoof, Four primality algorithms, à paraître, http://www.mat.uniroma2.it/~schoof/millerrabinpom.pdf. Zbl1196.11169
  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. Zbl1188.11076MR2467554
  44. S. Siksek, The modular approach to diophantine equations, preprint, http://igd.univ-lyon1.fr/~webeuler/ihp/LectureNotes_Siksek.dvi. Zbl06308165
  45. P. Stevenhagen & H. W. Lenstra, Jr., Chebotarëv and his density theorem., Math. Intell.18 (1996), no. 2, pp. 26–37. Zbl0885.11005MR1395088
  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. Zbl1216.11099MR2467548
  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. Zbl1294.11192
  49. N. Tzanakis & B. M. M. de Weger, On the practical solution of the Thue equation, J. Number Theory31 (1989), no. 2, pp. 99–132. Zbl0657.10014MR987566
  50. M. van Hoeij, Factoring polynomials and the knapsack problem, J. Number Theory95 (2002), no. 2, pp. 167–189. Zbl1081.11080MR1924096
  51. J. von zur Gathen & J. Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. Zbl1055.68168MR1689167

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.