Approximatting rings of integers in number fields

J. A. Buchmann; H. W. Lenstra

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

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

Abstract

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

How to cite

top

Buchmann, 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. [1] M.F. Atiyah, I. G. MacDONALD, Introduction to commutative algebra, Addison-Wesley, Reading, Mass, 1969. Zbl0175.03601MR242802
  2. [2] E. Bach, J. Driscoll, J.O. Shallit, Factor refinement, J. Algorithms15 (1993),199-222. Zbl0784.11058MR1231441
  3. [3] H. Bass, On the ubiquity of Goreinstein rings, Math. Z.82 (1963), 8-28. Zbl0112.26604MR153708
  4. [4] Z.I. Borevič, I.R. Safarevič, Teorija čisel, Izdat "Nauka", Moscow, 1964; English translation: Number theory, Academic Press, New York, 1966. MR170845
  5. [5] J.P. Buhler, H.W. Lenstra, Jr., C. Pomerance, Factoring integers with the number field sieve, [14], 50-94. Zbl0806.11067MR1321221
  6. [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. [7] H. Cohen, A course in computational algebraic number theory, Springer-Verlag, Berlin, 1993. Zbl0786.11071MR1228206
  8. [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. [9] G. Ge, Algorithms related to multiplicative representations of algebraic numbers, Ph. D. thesis, Department of Mathematics, University of California, Berkeley, May 1993. 
  10. [10] J.L. Hafner, K.S. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. 20 (1991), 1068-1083. Zbl0738.68050MR1135749
  11. [11] D.E. Knuth, The art of computer programming, vol. 2, second edition, Addison-Wesley, Reading, Mass., 1981. Zbl0477.65002MR633878
  12. [12] T.Y. Lam, Serre's conjecture, Lecture Notes in Math.635, Springer-Verlag, Berlin, 1978. Zbl0373.13004MR485842
  13. [13] S. Landau, Some remarks on computing the square parts of integers, Inform. and Comput.78 (1988), 246-253. Zbl0661.10007MR959811
  14. [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. [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. [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. [17] A.K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse, J.M. Pollard, The number field sieve, [14], 11-42. Zbl0806.11065MR1321219
  18. [18] H.W. Lenstra, Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc.26 (1992), 211-244. Zbl0759.11046MR1129315
  19. [19] H.W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), 649-673. Zbl0629.10006MR916721
  20. [20] H.W. Lenstra, Jr., Miller's primality test, Inform. Process. Lett. 8 (1979), 86-88. Zbl0399.10006MR520273
  21. [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. [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. [23] J.W. Sands, Generalization of a theorem of Siegel, Acta Arith.58 (1991), 47-57. Zbl0682.12010MR1111089
  24. [24] J. Teitelbaum, The computational complexity of the resolution of plane curve singularities, Math. Comp.54 (1990), 797-837. Zbl0716.14035MR1010602
  25. [25] E. Weiss, Algebraic number theory, McGraw-Hill, New York, 1963; reprinted, Chelsea, New York, 1976. Zbl0115.03601MR159805
  26. [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. [27] H.G. Zimmer, Computational problems, methods and results in algebraic number theory, Lecture Notes in Math.262, Springer-Verlag, Berlin, 1972. Zbl0231.12001MR323751

NotesEmbed ?

top

You must be logged in to post comments.