staple
Avec cedram.org

Rechercher dans le site

Table des matières de ce fascicule | Article précédent | Article suivant
J. A. Buchmann; H. W. Lenstra
Approximatting rings of integers in number fields
Journal de théorie des nombres de Bordeaux, 6 no. 2 (1994), p. 221-260, doi: 10.5802/jtnb.113
Article PDF | Analyses MR 1360644 | Zbl 0828.11075 | 5 citations dans Cedram
Mots clés: maximal order, tame extensions, algorithm

Résumé - Abstract

Nous étudions dans cet article le problème algorithmique de la détermination de l’anneau des entiers d’un corps de nombres algébriques donné. En pratique, ce problème est souvent considéré comme résolu mais des résultats théoriques montrent que sa résolution ne peut être menée à terme lorsque le corps étudié est défini par les équations dont les coefficients sont très gros. Or de tels corps apparaissent dans l’algorithme du crible algébrique utilisé pour factoriser les entiers naturels. En appliquant une variante d’un algorithme standard donnant l’anneau des entiers, on obtient un sous-anneau du corps de nombres qui peut être regardé comme le meilleur candidat possible pour l’anneau des entiers. Ce meilleur candidat est probablement souvent le bon. Notre propos est d’exposer ce qui peut être prouvé sur ce sous-anneau. Nous montrons que sa structure locale est transparente et rappelle celle des extensions modérément ramifiées de corps locaux. La plus grande partie de cet article est consacrée à l’étude des anneaux qui sont «modérés» en un sens plus général que celui habituel. Chemin faisant nous établissons des résultats de complexité qui prolongent un théorème de Chistov. L’article inclut également une section qui discute des algorithmes en temps polynomial pour les groupes abéliens de type fini.

Bibliographie

[1] M.F. Atiyah, I. G. MacDONALD, Introduction to commutative algebra, Addison-Wesley, Reading, Mass, 1969.  MR 242802 |  Zbl 0175.03601
[2] E. Bach, J. Driscoll, J.O. Shallit, Factor refinement, J. Algorithms 15 (1993),199-222.  MR 1231441 |  Zbl 0784.11058
[3] H. Bass, On the ubiquity of Goreinstein rings, Math. Z. 82 (1963), 8-28.  MR 153708 |  Zbl 0112.26604
[4] Z.I. Borevič, I.R. Safarevič, Teorija čisel, Izdat "Nauka", Moscow, 1964; English translation: Number theory, Academic Press, New York, 1966.  MR 170845
[5] J.P. Buhler, H.W. Lenstra, Jr., C. Pomerance, Factoring integers with the number field sieve, [14], 50-94.  MR 1321221 |  Zbl 0806.11067
[6] A.L. Chistov, The complexity of constructing the ring of integers of a global field, Dokl. Akad. Nauk SSSR 306 (1989), 1063-1067; English translation: Soviet Math. Dokl. 39 (1989), 597-600.  MR 1014763 |  Zbl 0698.12001
[7] H. Cohen, A course in computational algebraic number theory, Springer-Verlag, Berlin, 1993.  MR 1228206 |  Zbl 0786.11071
[8] M.R. Garey, D.S. Johnson, Computers and intractability, a guide to the theory of NP-completeness, Freeman, New York, 1979.  MR 519066 |  Zbl 0411.68039
[9] G. Ge, Algorithms related to multiplicative representations of algebraic numbers, Ph. D. thesis, Department of Mathematics, University of California, Berkeley, May 1993.
[10] J.L. Hafner, K.S. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. 20 (1991), 1068-1083.  MR 1135749 |  Zbl 0738.68050
[11] D.E. Knuth, The art of computer programming, vol. 2, second edition, Addison-Wesley, Reading, Mass., 1981.  MR 633878 |  Zbl 0477.65002
[12] T.Y. Lam, Serre's conjecture, Lecture Notes in Math. 635, Springer-Verlag, Berlin, 1978.  MR 485842 |  Zbl 0373.13004
[13] S. Landau, Some remarks on computing the square parts of integers, Inform. and Comput. 78 (1988), 246-253.  MR 959811 |  Zbl 0661.10007
[14] A. K. LENSTRA, H. W. LENSTRA, Jr. (eds), The development of the number field sieve, Lecture Notes in Math. 1554, Springer-Verlag, Berlin, 1993.  MR 1321217 |  Zbl 0806.11065
[15] A.K. Lenstra, H.W. Lenstra, Jr., L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515-534.  MR 682664 |  Zbl 0488.12001
[16] A.K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse, J.M. Pollard, The factorization of the ninth Fermat number, Math. Comp. 61 (1993), 319-349.  MR 1182953 |  Zbl 0792.11055
[17] A.K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse, J.M. Pollard, The number field sieve, [14], 11-42.  MR 1321219 |  Zbl 0806.11065
[18] H.W. Lenstra, Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc. 26 (1992), 211-244.  MR 1129315 |  Zbl 0759.11046
[19] H.W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), 649-673.  MR 916721 |  Zbl 0629.10006
[20] H.W. Lenstra, Jr., Miller's primality test, Inform. Process. Lett. 8 (1979), 86-88.  MR 520273 |  Zbl 0399.10006
[21] H.W. Lenstra, Jr., C. Pomerance, A rigorous time bound for factoring integers, J. Amer. Math. Soc. 5 (1992), 483-516.  MR 1137100 |  Zbl 0770.11057
[22] C. Pomerance,, Analysis and comparison of some integer factoring algorithms, in: H. W. Lenstra, Jr., R. Tijdeman (eds), Computational methods in number theory, Mathematical Centre Tracts 154/155, Mathematisch Centrum, Amsterdam, 1982, 89-139.  MR 700260 |  Zbl 0508.10004
[23] J.W. Sands, Generalization of a theorem of Siegel, Acta Arith. 58 (1991), 47-57.  MR 1111089 |  Zbl 0682.12010
[24] J. Teitelbaum, The computational complexity of the resolution of plane curve singularities, Math. Comp. 54 (1990), 797-837.  MR 1010602 |  Zbl 0716.14035
[25] E. Weiss, Algebraic number theory, McGraw-Hill, New York, 1963; reprinted, Chelsea, New York, 1976.  MR 159805 |  Zbl 0115.03601
[26] H. Zassenhaus, Ein Algorithmus zur Berechnung einer Minimalbasis über gegebener Ordnung, in: L. Collatz, G. Meinardus, H. Unger (eds), Funktionalanalysis, Approximationstheorie, numerische Mathematik, Oberwolfach 1965, Birkhäuser, Basel, 1967, 90-103.  MR 227135 |  Zbl 0153.36702
[27] H.G. Zimmer, Computational problems, methods and results in algebraic number theory, Lecture Notes in Math. 262, Springer-Verlag, Berlin, 1972.  MR 323751 |  Zbl 0231.12001