Approximatting rings of integers in number fields

Buchmann, J. A.; Lenstra, H. W.

Journal de théorie des nombres de Bordeaux, Tome 6 (1994) no. 2, pp. 221-260.

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.

In this paper we study the algorithmic problem of finding the ring of integers of a given algebraic number field. In practice, this problem is often considered to be well-solved, but theoretical results indicate that it is intractable for number fields that are defined by equations with very large coefficients. Such fields occur in the number field sieve algorithm for factoring integers. Applying a variant of a standard algorithm for finding rings of integers, one finds a subring of the number field that one may view as the “best guess” one has for the ring of integers. This best guess is probably often correct. Our main concern is what can be proved about this subring. We show that it has a particularly transparent local structure, which is reminiscent of the structure of tamely ramified extensions of local fields. A major portion of the paper is devoted to the study of rings that are “tame” in our more general sense. As a byproduct, we prove complexity results that elaborate upon a result of Chistov. The paper also includes a section that discusses polynomial time algorithms related to finitely generated abelian groups.

Mots clés : maximal order, tame extensions, algorithm

[1] M.F. Atiyah, I. G. MacDONALD, Introduction to commutative algebra, Addison-Wesley, Reading, Mass, 1969. | MR | Zbl

[2] E. Bach, J. Driscoll, J.O. Shallit, Factor refinement, J. Algorithms 15 (1993),199-222. | MR | Zbl

[3] H. Bass, On the ubiquity of Goreinstein rings, Math. Z. 82 (1963), 8-28. | MR | Zbl

[4] Z.I. Borevič, I.R. Safarevič, Teorija čisel, Izdat "Nauka", Moscow, 1964; English translation: Number theory, Academic Press, New York, 1966. | MR

[5] J.P. Buhler, H.W. Lenstra, Jr., C. Pomerance, Factoring integers with the number field sieve, [14], 50-94. | MR | Zbl

[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 | Zbl

[7] H. Cohen, A course in computational algebraic number theory, Springer-Verlag, Berlin, 1993. | MR | Zbl

[8] M.R. Garey, D.S. Johnson, Computers and intractability, a guide to the theory of NP-completeness, Freeman, New York, 1979. | MR | Zbl

[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 | Zbl

[11] D.E. Knuth, The art of computer programming, vol. 2, second edition, Addison-Wesley, Reading, Mass., 1981. | MR | Zbl

[12] T.Y. Lam, Serre's conjecture, Lecture Notes in Math. 635, Springer-Verlag, Berlin, 1978. | MR | Zbl

[13] S. Landau, Some remarks on computing the square parts of integers, Inform. and Comput. 78 (1988), 246-253. | MR | Zbl

[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 | Zbl

[15] A.K. Lenstra, H.W. Lenstra, Jr., L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515-534. | MR | Zbl

[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 | Zbl

[17] A.K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse, J.M. Pollard, The number field sieve, [14], 11-42. | MR | Zbl

[18] H.W. Lenstra, Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc. 26 (1992), 211-244. | MR | Zbl

[19] H.W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), 649-673. | MR | Zbl

[20] H.W. Lenstra, Jr., Miller's primality test, Inform. Process. Lett. 8 (1979), 86-88. | MR | Zbl

[21] H.W. Lenstra, Jr., C. Pomerance, A rigorous time bound for factoring integers, J. Amer. Math. Soc. 5 (1992), 483-516. | MR | Zbl

[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 | Zbl

[23] J.W. Sands, Generalization of a theorem of Siegel, Acta Arith. 58 (1991), 47-57. | MR | Zbl

[24] J. Teitelbaum, The computational complexity of the resolution of plane curve singularities, Math. Comp. 54 (1990), 797-837. | MR | Zbl

[25] E. Weiss, Algebraic number theory, McGraw-Hill, New York, 1963; reprinted, Chelsea, New York, 1976. | MR | Zbl

[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 | Zbl

[27] H.G. Zimmer, Computational problems, methods and results in algebraic number theory, Lecture Notes in Math. 262, Springer-Verlag, Berlin, 1972. | MR | Zbl