Algorithms in algebraic number theory
HTML articles powered by AMS MathViewer
- by H. W. Lenstra PDF
- Bull. Amer. Math. Soc. 26 (1992), 211-244 Request permission
Abstract:
In this paper we discuss the basic problems of algorithmic algebraic number theory. The emphasis is on aspects that are of interest from a purely mathematical point of view, and practical issues are largely disregarded. We describe what has been done and, more importantly, what remains to be done in the area. We hope to show that the study of algorithms not only increases our understanding of algebraic number fields but also stimulates our curiosity about them. The discussion is concentrated of three topics: the determination of Galois groups, the determination of the ring of integers of an algebraic number field, and the computation of the group of units and the class group of that ring of integers.References
-
L. M. Adleman and M. A. Huang, Recognizing primes in random polynomial time, Research report, Dept. of Computer Science, Univ. of Southern California, 1988; Lecture Notes in Math., Springer, Heidelberg (to appear). Extended abstract: Proc. 19th Ann. ACM Sympos. on Theory of Computing (STOC), ACM, New York 1987, pp. 462-469.
L. M. Adleman and H. W. Lenstra, Jr., Finding irreducible polynomials over finite fields, Proc. 18th Ann. ACM Sympos. on Theory of Computing (STOC), ACM, New York (1986, pp. 350-355.
- Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983), no. 1, 173–206. MR 683806, DOI 10.2307/2006975 Archimedes, The sand-reckoner, in: Opera quae quidem extant, J. Hervagius, Basel, 1544. (Greek and Latin)
- A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), no. 203, 29–68. MR 1199989, DOI 10.1090/S0025-5718-1993-1199989-X
- Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355–380. MR 1023756, DOI 10.1090/S0025-5718-1990-1023756-8 E. Bach and J. O. Shallit, Factor refinement, J. Algorithms (to appear). W. E. H. Berwick, Integral bases, Cambridge Univ. Press, Cambridge, 1927. Z. I. Borevič and I. R. Šafarevič, Teorija čisel, Izdat. "Nauka", Moscow, 1964; English transl.: Number theory, Academic Press, New York, 1966. W. Bosma and M. P. M. van der Hulst, Primality proving with cyclotomy, Academisch proefschrift, Universiteit van Amsterdam, 1990. E. Brieskorn and H. Knörrer, Ebene algebraische Kurven, Birkhäuser, Basel, 1981.
- Johannes Buchmann, Complexity of algorithms in algebraic number theory, Number theory (Banff, AB, 1988) de Gruyter, Berlin, 1990, pp. 37–53. MR 1106649
- Johannes Buchmann, A subexponential algorithm for the determination of class groups and regulators of algebraic number fields, Séminaire de Théorie des Nombres, Paris 1988–1989, Progr. Math., vol. 91, Birkhäuser Boston, Boston, MA, 1990, pp. 27–41. MR 1104698 J. Buchmann and H. W. Lenstra, Jr., Manuscript in preparation. J. Buchmann and V. Shoup, Constructing nonresidues in finite fields and the extended Riemann hypothesis, in preparation. Extended abstract: Proc. 23rd Ann. ACM Sympos. on Theory of Computing (STOC), ACM, New York 1991, pp. 72-79.
- Johannes Buchmann and H. C. Williams, On the computation of the class number of an algebraic number field, Math. Comp. 53 (1989), no. 188, 679–688. MR 979937, DOI 10.1090/S0025-5718-1989-0979937-4 J. P. Buhler, H. W. Lenstra, Jr., and C. Pomerance, Factoring integers with the number field sieve, in preparation.
- Peter J. Cameron, Finite permutation groups and finite simple groups, Bull. London Math. Soc. 13 (1981), no. 1, 1–22. MR 599634, DOI 10.1112/blms/13.1.1
- J. W. S. Cassels, Local fields, London Mathematical Society Student Texts, vol. 3, Cambridge University Press, Cambridge, 1986. MR 861410, DOI 10.1017/CBO9781139171885
- J. W. S. Cassels and A. Fröhlich (eds.), Algebraic number theory, Academic Press, London; Thompson Book Co., Inc., Washington, D.C., 1967. MR 0215665
- A. L. Chistov, Efficient factorization of polynomials over local fields, Dokl. Akad. Nauk SSSR 293 (1987), no. 5, 1073–1077 (Russian). MR 890201
- A. L. Chistov, The complexity of the construction of the ring of integers of a global field, Dokl. Akad. Nauk SSSR 306 (1989), no. 5, 1063–1067 (Russian); English transl., Soviet Math. Dokl. 39 (1989), no. 3, 597–600. MR 1014763 H. Cohen, A course in computational algebraic number theory, in preparation.
- H. Cohen and A. K. Lenstra, Implementation of a new primality test, Math. Comp. 48 (1987), no. 177, 103–121, S1–S4. MR 866102, DOI 10.1090/S0025-5718-1987-0866102-2
- H. Cohen and H. W. Lenstra Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), no. 165, 297–330. MR 726006, DOI 10.1090/S0025-5718-1984-0726006-X
- David J. Ford and John McKay, Computation of Galois groups from polynomials over the rationals, Computer algebra (New York, 1984) Lecture Notes in Pure and Appl. Math., vol. 113, Dekker, New York, 1989, pp. 145–150. MR 1002982 D. Gordon, Discrete logarithms using the number field sieve (to appear).
- James L. Hafner and Kevin S. McCurley, A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc. 2 (1989), no. 4, 837–850. MR 1002631, DOI 10.1090/S0894-0347-1989-1002631-0
- James L. Hafner and Kevin S. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. 20 (1991), no. 6, 1068–1083. MR 1135749, DOI 10.1137/0220067
- Ravi Kannan, Algorithmic geometry of numbers, Annual review of computer science, Vol. 2, Annual Reviews, Palo Alto, CA, 1987, pp. 231–267. MR 921497 W. M. Kantor, unpublished. W. M. Kantor and E. M. Luks, Computing in quotient groups, Proc. 22nd Ann. ACM Sympos. on Theory of Computing (STOC), ACM, New York 1990, pp. 524-534.
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
- Susan Landau, Polynomial time algorithms for Galois groups, EUROSAM 84 (Cambridge, 1984) Lecture Notes in Comput. Sci., vol. 174, Springer, Berlin, 1984, pp. 225–236. MR 779128, DOI 10.1007/BFb0032845
- Susan Landau, Factoring polynomials over algebraic number fields, SIAM J. Comput. 14 (1985), no. 1, 184–195. MR 774938, DOI 10.1137/0214015
- Susan Landau and Gary Lee Miller, Solvability by radicals is in polynomial time, J. Comput. System Sci. 30 (1985), no. 2, 179–208. MR 801822, DOI 10.1016/0022-0000(85)90013-3
- Serge Lang, Algebraic number theory, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Don Mills, Ont., 1970. MR 0282947
- A. K. Lenstra, Factorization of polynomials, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 169–198. MR 700263
- A. K. Lenstra, Factoring multivariate integral polynomials, Theoret. Comput. Sci. 34 (1984), no. 1-2, 207–213. MR 774045, DOI 10.1016/0304-3975(84)90117-8
- Arjen K. Lenstra, Factoring multivariate polynomials over algebraic number fields, SIAM J. Comput. 16 (1987), no. 3, 591–598. MR 889410, DOI 10.1137/0216040
- A. K. Lenstra and H. W. Lenstra Jr., Algorithms in number theory, Handbook of theoretical computer science, Vol. A, Elsevier, Amsterdam, 1990, pp. 673–715. MR 1127178
- A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, DOI 10.1007/BF01457454 A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The factorization of the ninth Fermat number (to appear). —, The number field sieve, in preparation. Extended abstract: Proc. 22nd Ann. ACM Sympos. on Theory of Computing (STOC), ACM, New York 1990, pp. 564-572.
- H. W. Lenstra Jr., On the calculation of regulators and class numbers of quadratic fields, Number theory days, 1980 (Exeter, 1980) London Math. Soc. Lecture Note Ser., vol. 56, Cambridge Univ. Press, Cambridge, 1982, pp. 123–150. MR 697260
- H. W. Lenstra Jr., Galois theory and primality testing, Orders and their applications (Oberwolfach, 1984) Lecture Notes in Math., vol. 1142, Springer, Berlin, 1985, pp. 169–189. MR 812498, DOI 10.1007/BFb0074800
- H. W. Lenstra Jr., Algorithms for finite fields, Number theory and cryptography (Sydney, 1989) London Math. Soc. Lecture Note Ser., vol. 154, Cambridge Univ. Press, Cambridge, 1990, pp. 76–85. MR 1055400
- H. W. Lenstra Jr., Finding isomorphisms between finite fields, Math. Comp. 56 (1991), no. 193, 329–347. MR 1052099, DOI 10.1090/S0025-5718-1991-1052099-2
- H. W. Lenstra Jr. and Carl Pomerance, A rigorous time bound for factoring integers, J. Amer. Math. Soc. 5 (1992), no. 3, 483–516. MR 1137100, DOI 10.1090/S0894-0347-1992-1137100-0 H. W. Lenstra, Jr. and R. Tijdeman (eds.), Computational methods in number theory, Mathematical Centre Tracts, vol. 154/155, Mathematisch Centrum, Amsterdam, 1982. R. Lovorn, Rigorous, subexponential algorithms for discrete logarithms over finite fields, thesis, University of Georgia, in preparation.
- Annabelle McIver and Peter M. Neumann, Enumerating finite groups, Quart. J. Math. Oxford Ser. (2) 38 (1987), no. 152, 473–488. MR 916229, DOI 10.1093/qmath/38.4.473
- A. M. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, Advances in cryptology (Paris, 1984) Lecture Notes in Comput. Sci., vol. 209, Springer, Berlin, 1985, pp. 224–314. MR 825593, DOI 10.1007/3-540-39757-4_{2}0
- P. P. Pálfy, A polynomial bound for the orders of primitive solvable groups, J. Algebra 77 (1982), no. 1, 127–137. MR 665168, DOI 10.1016/0021-8693(82)90281-2
- M. E. Pohst, Three principal tasks of computational algebraic number theory, Number theory and applications (Banff, AB, 1988) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 265, Kluwer Acad. Publ., Dordrecht, 1989, pp. 123–133. MR 1123072
- M. Pohst and H. Zassenhaus, Algorithmic algebraic number theory, Encyclopedia of Mathematics and its Applications, vol. 30, Cambridge University Press, Cambridge, 1989. MR 1033013, DOI 10.1017/CBO9780511661952
- Carl Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, Discrete algorithms and complexity (Kyoto, 1986) Perspect. Comput., vol. 15, Academic Press, Boston, MA, 1987, pp. 119–143. MR 910929 R. Quême, Relations d’inégalités effectives en théorie algébrique des nombres, Sém. Théor. Nombres Bordeaux, 1987-1988, 19-01-19-19.
- Jonathan W. Sands, Generalization of a theorem of Siegel, Acta Arith. 58 (1991), no. 1, 47–57. MR 1111089, DOI 10.4064/aa-58-1-47-57 O. Schirokauer, Discrete logarithms and local units, in preparation.
- H. Zantema, Class numbers and units, Computational methods in number theory, Part II, Math. Centre Tracts, vol. 155, Math. Centrum, Amsterdam, 1982, pp. 213–234. MR 702518
- René Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp. 44 (1985), no. 170, 483–494. MR 777280, DOI 10.1090/S0025-5718-1985-0777280-6 J-P. Serre, Arbres, amalgames, ${\text {S}}{{\text {L}}_2}$, Astérisque 46 (1977).
- Jean-Pierre Serre, Lectures on the Mordell-Weil theorem, Aspects of Mathematics, E15, Friedr. Vieweg & Sohn, Braunschweig, 1989. Translated from the French and edited by Martin Brown from notes by Michel Waldschmidt. MR 1002324, DOI 10.1007/978-3-663-14060-3
- Daniel Shanks, The infrastructure of a real quadratic field and its applications, Proceedings of the Number Theory Conference (Univ. Colorado, Boulder, Colo., 1972) Univ. Colorado, Boulder, Colo., 1972, pp. 217–224. MR 0389842
- Victor Shoup, New algorithms for finding irreducible polynomials over finite fields, Math. Comp. 54 (1990), no. 189, 435–447. MR 993933, DOI 10.1090/S0025-5718-1990-0993933-0
- Victor Shoup, On the deterministic complexity of factoring polynomials over finite fields, Inform. Process. Lett. 33 (1990), no. 5, 261–267. MR 1049276, DOI 10.1016/0020-0190(90)90195-4
- Carl Ludwig Siegel, Abschätzung von Einheiten, Nachr. Akad. Wiss. Göttingen Math.-Phys. Kl. II 1969 (1969), 71–86 (German). MR 249395
- Richard P. Stauduhar, The determination of Galois groups, Math. Comp. 27 (1973), 981–996. MR 327712, DOI 10.1090/S0025-5718-1973-0327712-4
- Kenneth A. Ribet (ed.), Current trends in arithmetical algebraic geometry, Contemporary Mathematics, vol. 67, American Mathematical Society, Providence, RI, 1987. MR 902589, DOI 10.1090/conm/067
- Jeremy Teitelbaum, The computational complexity of the resolution of plane curve singularities, Math. Comp. 54 (1990), no. 190, 797–837. MR 1010602, DOI 10.1090/S0025-5718-1990-1010602-1 N. Tzanakis and B. M. M. de Weger, How to solve explicitly a Thue-Mahler equation (to appear).
- F. J. van der Linden, The computation of Galois groups, Computational methods in number theory, Part II, Math. Centre Tracts, vol. 155, Math. Centrum, Amsterdam, 1982, pp. 199–211. MR 702517
- P. van Emde Boas, Machine models, computational complexity and number theory, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 7–42. MR 700256
- Edwin Weiss, Algebraic number theory, McGraw-Hill Book Co., Inc., New York-San Francisco-Toronto-London, 1963. MR 0159805
- H. Zantema, Class numbers and units, Computational methods in number theory, Part II, Math. Centre Tracts, vol. 155, Math. Centrum, Amsterdam, 1982, pp. 213–234. MR 702518
- Hans Zassenhaus, Ein Algorithmus zur Berechnung einer Minimalbasis über gegebener Ordnung, Funktionalanalysis, Approximationstheorie, Numerische Mathematik (Oberwolfach, 1965) Birkhäuser, Basel, 1967, pp. 90–103 (German). MR 0227135
- Horst G. Zimmer, Computational problems, methods, and results in algebraic number theory, Lecture Notes in Mathematics, Vol. 262, Springer-Verlag, Berlin-New York, 1972. MR 0323751
Additional Information
- © Copyright 1992 American Mathematical Society
- Journal: Bull. Amer. Math. Soc. 26 (1992), 211-244
- MSC (2000): Primary 11Y40; Secondary 11R27, 11R29
- DOI: https://doi.org/10.1090/S0273-0979-1992-00284-7
- MathSciNet review: 1129315