# Approximatting rings of integers in number fields

Journal de théorie des nombres de Bordeaux (1994)

- Volume: 6, Issue: 2, page 221-260
- ISSN: 1246-7405

## Access Full Article

top## Abstract

top## How to cite

topBuchmann, J. A., and Lenstra, H. W.. "Approximatting rings of integers in number fields." Journal de théorie des nombres de Bordeaux 6.2 (1994): 221-260. <http://eudml.org/doc/247529>.

@article{Buchmann1994,

abstract = {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.},

author = {Buchmann, J. A., Lenstra, H. W.},

journal = {Journal de théorie des nombres de Bordeaux},

keywords = {maximal order; tame extensions; algorithm; computing the maximal order of an algebraic number field; survey; polynomial time algorithms},

language = {eng},

number = {2},

pages = {221-260},

publisher = {Université Bordeaux I},

title = {Approximatting rings of integers in number fields},

url = {http://eudml.org/doc/247529},

volume = {6},

year = {1994},

}

TY - JOUR

AU - Buchmann, J. A.

AU - Lenstra, H. W.

TI - Approximatting rings of integers in number fields

JO - Journal de théorie des nombres de Bordeaux

PY - 1994

PB - Université Bordeaux I

VL - 6

IS - 2

SP - 221

EP - 260

AB - 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.

LA - eng

KW - maximal order; tame extensions; algorithm; computing the maximal order of an algebraic number field; survey; polynomial time algorithms

UR - http://eudml.org/doc/247529

ER -

## References

top- [1] M.F. Atiyah, I. G. MacDONALD, Introduction to commutative algebra, Addison-Wesley, Reading, Mass, 1969. Zbl0175.03601MR242802
- [2] E. Bach, J. Driscoll, J.O. Shallit, Factor refinement, J. Algorithms15 (1993),199-222. Zbl0784.11058MR1231441
- [3] H. Bass, On the ubiquity of Goreinstein rings, Math. Z.82 (1963), 8-28. Zbl0112.26604MR153708
- [4] Z.I. Borevič, I.R. Safarevič, Teorija čisel, Izdat "Nauka", Moscow, 1964; English translation: Number theory, Academic Press, New York, 1966. MR170845
- [5] J.P. Buhler, H.W. Lenstra, Jr., C. Pomerance, Factoring integers with the number field sieve, [14], 50-94. Zbl0806.11067MR1321221
- [6] A.L. Chistov, The complexity of constructing the ring of integers of a global field, Dokl. Akad. Nauk SSSR306 (1989), 1063-1067; English translation: Soviet Math. Dokl.39 (1989), 597-600. Zbl0698.12001MR1014763
- [7] H. Cohen, A course in computational algebraic number theory, Springer-Verlag, Berlin, 1993. Zbl0786.11071MR1228206
- [8] M.R. Garey, D.S. Johnson, Computers and intractability, a guide to the theory of NP-completeness, Freeman, New York, 1979. Zbl0411.68039MR519066
- [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. Zbl0738.68050MR1135749
- [11] D.E. Knuth, The art of computer programming, vol. 2, second edition, Addison-Wesley, Reading, Mass., 1981. Zbl0477.65002MR633878
- [12] T.Y. Lam, Serre's conjecture, Lecture Notes in Math.635, Springer-Verlag, Berlin, 1978. Zbl0373.13004MR485842
- [13] S. Landau, Some remarks on computing the square parts of integers, Inform. and Comput.78 (1988), 246-253. Zbl0661.10007MR959811
- [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. Zbl0806.11065MR1321217
- [15] A.K. Lenstra, H.W. Lenstra, Jr., L. Lovász, Factoring polynomials with rational coefficients, Math. Ann.261 (1982), 515-534. Zbl0488.12001MR682664
- [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. Zbl0792.11055MR1182953
- [17] A.K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse, J.M. Pollard, The number field sieve, [14], 11-42. Zbl0806.11065MR1321219
- [18] H.W. Lenstra, Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc.26 (1992), 211-244. Zbl0759.11046MR1129315
- [19] H.W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), 649-673. Zbl0629.10006MR916721
- [20] H.W. Lenstra, Jr., Miller's primality test, Inform. Process. Lett. 8 (1979), 86-88. Zbl0399.10006MR520273
- [21] H.W. Lenstra, Jr., C. Pomerance, A rigorous time bound for factoring integers, J. Amer. Math. Soc.5 (1992), 483-516. Zbl0770.11057MR1137100
- [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. Zbl0508.10004MR700260
- [23] J.W. Sands, Generalization of a theorem of Siegel, Acta Arith.58 (1991), 47-57. Zbl0682.12010MR1111089
- [24] J. Teitelbaum, The computational complexity of the resolution of plane curve singularities, Math. Comp.54 (1990), 797-837. Zbl0716.14035MR1010602
- [25] E. Weiss, Algebraic number theory, McGraw-Hill, New York, 1963; reprinted, Chelsea, New York, 1976. Zbl0115.03601MR159805
- [26] H. Zassenhaus, Ein Algorithmus zur Berechnung einer Minimalbasis über gegebener Ordnung, in: L. Collatz, G. Meinardus, H. Unger (eds), Funktionalanalysis, Approximationstheorie, numerische Mathematik, Oberwolfach1965, Birkhäuser, Basel, 1967, 90-103. Zbl0153.36702MR227135
- [27] H.G. Zimmer, Computational problems, methods and results in algebraic number theory, Lecture Notes in Math.262, Springer-Verlag, Berlin, 1972. Zbl0231.12001MR323751

## Citations in EuDML Documents

top- Jordi Guàrdia, Jesús Montes, Enric Nart, Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields
- Qingquan Wu, Explicit construction of integral bases of radical function fields
- Karim Belabas, Théorie algébrique des nombres et calcul formel
- Karim Belabas, Topics in computational algebraic number theory

## NotesEmbed ?

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