Approximating rings of integers in number fields. (English) Zbl 0828.11075
This is a nice survey on the problem of computing the maximal order \(o_F\) of an algebraic number field \(F\). Starting from a result of A. L. Chistov [Sov. Math., Dokl. 39, No. 3, 597-600 (1989); English translation from Dokl. Akad. Nauk SSSR 306, No. 5, 1063-1067 (1989; Zbl 0698.12001)] the authors discuss polynomial time algorithms for constructing an order of \(F\) which is close to \(o_F\) in a precise sense.
Unfortunately the presentation is not very well balanced. Whereas several sections contain basic material from textbooks, others cover new ground - - at least from an algorithmic point of view. Notions like “factor refinement” are adopted uncritically although these ideals are certainly not new. They already were published by H. Zassenhaus in the seventies [Symp. Math. 15, Convegni 1973, 499-513 (1975; Zbl 0337.12014)]and are contained in textbooks since more than five years.
Unfortunately the presentation is not very well balanced. Whereas several sections contain basic material from textbooks, others cover new ground - - at least from an algorithmic point of view. Notions like “factor refinement” are adopted uncritically although these ideals are certainly not new. They already were published by H. Zassenhaus in the seventies [Symp. Math. 15, Convegni 1973, 499-513 (1975; Zbl 0337.12014)]and are contained in textbooks since more than five years.
Reviewer: M.Pohst (Berlin)
MSC:
| 11Y40 | Algebraic number theory computations |
| 11R33 | Integral representations related to algebraic numbers; Galois module structure of rings of integers |
| 11R54 | Other algebras and orders, and their zeta and \(L\)-functions |
Keywords:
computing the maximal order of an algebraic number field; survey; polynomial time algorithmsReferences:
| [1] | Atiyah, M.F., I. G. MacDONALD, Introduction to commutative algebra, Addison-Wesley, Reading, Mass, 1969. · Zbl 0175.03601 |
| [2] | Bach, E., Driscoll, J., Shallit, J.O., Factor refinement, J. Algorithms15 (1993),199-222. · Zbl 0784.11058 |
| [3] | Bass, H., On the ubiquity of Goreinstein rings, Math. Z.82 (1963), 8-28. · Zbl 0112.26604 |
| [4] | Borevič, Z.I., Safarevič, I.R., Teorija čisel, Izdat “Nauka”, Moscow, 1964; English translation: Number theory, Academic Press, New York, 1966. · Zbl 0121.04202 |
| [5] | Buhler, J.P., Lenstra, H.W., Jr., Pomerance, C., Factoring integers with the number field sieve, [14], 50-94. · Zbl 0806.11067 |
| [6] | Chistov, A.L., 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. · Zbl 0698.12001 |
| [7] | Cohen, H., A course in computational algebraic number theory, Springer-Verlag, Berlin, 1993. · Zbl 0786.11071 |
| [8] | Garey, M.R., Johnson, D.S., Computers and intractability, a guide to the theory of NP-completeness, Freeman, New York, 1979. · Zbl 0411.68039 |
| [9] | Ge, G., Algorithms related to multiplicative representations of algebraic numbers, Ph. D. thesis, Department of Mathematics, University of California, Berkeley, May 1993. |
| [10] | Hafner, J.L., McCurley, K.S., Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. 20 (1991), 1068-1083. · Zbl 0738.68050 |
| [11] | Knuth, D.E., The art of computer programming, vol. 2, second edition, Addison-Wesley, Reading, Mass., 1981. · Zbl 0477.65002 |
| [12] | Lam, T.Y., Serre’s conjecture, 635, Springer-Verlag, Berlin, 1978. · Zbl 0373.13004 |
| [13] | Landau, S., Some remarks on computing the square parts of integers, Inform. and Comput.78 (1988), 246-253. · Zbl 0661.10007 |
| [14] | A. K. LENSTRA, H. W. LENSTRA, Jr. (eds), The development of the number field sieve, 1554, Springer-Verlag, Berlin, 1993. · Zbl 0806.11065 |
| [15] | Lenstra, A.K., Lenstra, H.W., Jr., Lovász, L., Factoring polynomials with rational coefficients, Math. Ann.261 (1982), 515-534. · Zbl 0488.12001 |
| [16] | Lenstra, A.K., Lenstra, H.W., Jr., Manasse, M.S., Pollard, J.M., The factorization of the ninth Fermat number, Math. Comp.61 (1993), 319-349. · Zbl 0792.11055 |
| [17] | Lenstra, A.K., Lenstra, H.W., Jr., Manasse, M.S., Pollard, J.M., The number field sieve, [14], 11-42. · Zbl 0806.11065 |
| [18] | Lenstra, H.W., Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc.26 (1992), 211-244. · Zbl 0759.11046 |
| [19] | Lenstra, H.W., Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), 649-673. · Zbl 0629.10006 |
| [20] | Lenstra, H.W., Jr., Miller’s primality test, Inform. Process. Lett. 8 (1979), 86-88. · Zbl 0399.10006 |
| [21] | Lenstra, H.W., Jr., Pomerance, C., A rigorous time bound for factoring integers, J. Amer. Math. Soc.5 (1992), 483-516. · Zbl 0770.11057 |
| [22] | Pomerance, C.,, 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. · Zbl 0508.10004 |
| [23] | Sands, J.W., Generalization of a theorem of Siegel, Acta Arith.58 (1991), 47-57. · Zbl 0682.12010 |
| [24] | Teitelbaum, J., The computational complexity of the resolution of plane curve singularities, Math. Comp.54 (1990), 797-837. · Zbl 0716.14035 |
| [25] | Weiss, E., Algebraic number theory, McGraw-Hill, New York, 1963; reprinted, Chelsea, New York, 1976. · Zbl 0115.03601 |
| [26] | Zassenhaus, H., 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. · Zbl 0153.36702 |
| [27] | Zimmer, H.G., Computational problems, methods and results in algebraic number theory, 262, Springer-Verlag, Berlin, 1972. · Zbl 0231.12001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
