Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Available in electronic format
Available in print format 		Bulletin of the American Mathematical Society
Bulletin of the American Mathematical Society
ISSN 1088-9485(e) ISSN 0273-0979(p)

     

Algorithms in algebraic number theory

Author(s): H. W. Lenstra
Journal: Bull. Amer. Math. Soc. 26 (1992), 211-244.
MSC (2000): Primary 11Y40; Secondary 11R27, 11R29
MathSciNet review: 1129315
Retrieve article in: PDF

Abstract | References | Similar articles | Additional information

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:

[1]
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.

[2]
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.

[3]
L. M. Adleman, C. Pomerance, and R. S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983), 173-206. MR 683806 (84e:10008)

[4]
Archimedes, The sand-reckoner, in: Opera quae quidem extant, J. Hervagius, Basel, 1544. (Greek and Latin)

[5]
A. O. L. Atkin and F. Morain, Elliptic curves and primality proving (to appear). MR 1199989 (93m:11136)

[6]
E. Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), 355-380. MR 1023756 (91m:11096)

[7]
E. Bach and J. O. Shallit, Factor refinement, J. Algorithms (to appear).

[8]
W. E. H. Berwick, Integral bases, Cambridge Univ. Press, Cambridge, 1927.

[9]
Z. I. Borevič and I. R. Šafarevič, Teorija čisel, Izdat. "Nauka", Moscow, 1964; English transl.: Number theory, Academic Press, New York, 1966.

[10]
W. Bosma and M. P. M. van der Hulst, Primality proving with cyclotomy, Academisch proefschrift, Universiteit van Amsterdam, 1990.

[11]
E. Brieskorn and H. Knörrer, Ebene algebraische Kurven, Birkhäuser, Basel, 1981.

[12]
J. Buchmann, Complexity of algorithms in algebraic number theory, Proceedings of the first conference of the Canadian Number Theory Association (R. A. Mollin, ed.), De Gruyter, Berlin, 1990, pp. 37-53. MR 1106649 (92f:11179)

[13]
-, 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 (C. Goldstein, ed.), Birkhäuser, Boston, 1990, pp. 27-41. MR 1104698 (92g:11125)

[14]
J. Buchmann and H. W. Lenstra, Jr., Manuscript in preparation.

[15]
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.

[16]
J. Buchmann and H. C. Williams, On the computation of the class number of an algebraic number field, Math. Comp. 53 (1989), 679-688. MR 979937 (90a:11128)

[17]
J. P. Buhler, H. W. Lenstra, Jr., and C. Pomerance, Factoring integers with the number field sieve, in preparation.

[18]
P. J. Cameron, Finite permutation groups and finite simple groups, Bull. London Math. Soc. 13(1981), 1-22. MR 599634 (83m:20008)

[19]
J. W. S. Cassels, Local fields, Cambridge Univ. Press, Cambridge, 1986. MR 861410 (87i:11172)

[20]
J. W. S. Cassels and A. Fröhlich (eds.), Algebraic number theory, Proceedings of an instructional conference, Academic Press, London, 1967. MR 0215665 (35:6500)

[21]
A. L. Chistov, Efficient factorization of polynomials over local fields, Dokl. Akad. Nauk SSSR 293 (1987), 1073-1077; English transl.: Soviet Math. Dokl. 35 (1987), 430-433. MR 890201 (88d:11118)

[22]
-, The complexity of constructing the ring of integers of a global field, Dokl. Akad. Nauk SSSR 306 (1989), 1063-1067; English transl.: Soviet Math. Dokl. 39 (1989), 597-600. MR 1014763 (90g:11170)

[23]
H. Cohen, A course in computational algebraic number theory, in preparation.

[24]
H. Cohen and A. K. Lenstra, Implementation of a new primality test, Math. Comp. 48 (1987), 103-121. MR 866102 (88c:11080)

[25]
H. Cohen and H. W. Lenstra, Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), 297-330. MR 726006 (86g:11078)

[26]
D. J. Ford and J. McKay, Computation of Galois groups from polynomials over the rationals, Computer Algebra (D. V. Chudnovsky and R. D. Jenks, eds.), Lecture Notes in Pure and Appl. Math., vol. 113, Marcel Dekker, New York, 1989, pp. 145-150. MR 1002982 (90h:11113)

[27]
D. Gordon, Discrete logarithms using the number field sieve (to appear).

[28]
J. L. Hafner and K. S. McCurley, A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc. 2 (1989), 837-850. MR 1002631 (91f:11090)

[29]
-, Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. (to appear). MR 1135749 (93d:15021)

[30]
R. Kannan. Algorithmic geometry of numbers, Annual Review of Computer Sciences, vol. 2 (J. F. Traub, B. J. Grosz, B. W. Lampson, N. J. Nilsson, eds.), Annual Reviews Inc., Palo Alto, 1987, pp. 231-267. MR 921497 (89a:11131)

[31]
W. M. Kantor, unpublished.

[32]
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.

[33]
D. E. Knuth, The art of computer programming, Vol. 2, Seminumerical Algorithms, Addison-Wesley, Reading, MA, second edition, 1981. MR 633878 (83i:68003)

[34]
S. Landau, Polynomial time algorithms for Galois groups, Eurosam 84 (J. Fitch, ed.), Lecture Notes in Comput. Sci., vol. 174, Springer, Berlin, 1984, pp. 225-236. MR 779128 (87a:12001)

[35]
-, Factoring polynomials over algebraic number fields, SIAM J. Comput. 14 (1985), 184-195. MR 774938 (86d:11102)

[36]
S. Landau and G L. Miller, Solvability by radicals is in polynomial time, J. Comput. System Sci. 30 (1985), 179-208. MR 801822 (86k:12001)

[37]
S. Lang, Algebraic number theory, Addison-Wesley, Reading, MA, 1970. MR 0282947 (44:181)

[38]
A. K. Lenstra, Factorization of polynomials, Computational Methods in Number Theory (H. W. Lenstra, Jr. and R. Tijdeman, eds.), Math. Centre Tracts., vol. 154/155, Mathematisch Centrum Amsterdam, 1982, pp. 169-198. MR 700263 (85a:12002)

[39]
-, Factoring polynomials over algebraic number fields, Computer Algebra (J. A. van Hulzen, ed.) Lecture Notes in Comput. Sci., vol. 162, Springer, Berlin, 1983, pp. 245-254. MR 774816 (86g:12001b)

[40]
-, Factoring multivariate polynomials over algebraic number fields, SIAM J. Comput. 16 (1987), 591-598. MR 889410 (88j:12001)

[41]
A. K. Lenstra and H. W. Lenstra, Jr., Algorithms in number theory, Handbook of Theoretical Computer Science, Vol. A, Algorithms and Complexity (J. van Leeuwen, ed.), Elsevier, Amsterdam, 1990, pp. 673-715. MR 1127178

[42]
A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515-534. MR 682664 (84a:12002)

[43]
A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The factorization of the ninth Fermat number (to appear).

[44]
-, 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.

[45]
H. W. Lenstra, Jr., On the calculation of regulators and class numbers of quadratic fields, Journées Arithmétiques 1980 (J. Armitage, ed.), London Math. Soc. Lecture Note Ser., vol. 56, Cambridge Univ. Press, Cambridge, 1982, pp. 123-150. MR 697260 (86g:11080)

[46]
-, Galois theory and primality testing, Orders and Their Applications (I. Reiner, K. Roggenkamp, eds.), Lecture Notes in Math., vol. 1142, Springer, Heidelberg, 1985, pp. 169-189. MR 812498 (87g:11171)

[47]
-, Algorithms for finite fields, Number Theory and Cryptography (J. H. Loxton, ed.), London Math. Soc. Lecture Note Ser., vol. 154, Cambridge Univ. Press, Cambridge, 1990, pp. 76-85. MR 1055400 (92b:11091)

[48]
-, Finding isomorphisms between finite fields, Math. Comp. 56 (1991), 329-347. MR 1052099 (91d:11151)

[49]
H. W. Lenstra, Jr. and C. Pomerance, A rigorous time bound for factoring integers, J. Amer. Math. Soc. (to appear). MR 1137100 (92m:11145)

[50]
H. W. Lenstra, Jr. and R. Tijdeman (eds.), Computational methods in number theory, Mathematical Centre Tracts, vol. 154/155, Mathematisch Centrum, Amsterdam, 1982.

[51]
R. Lovorn, Rigorous, subexponential algorithms for discrete logarithms over finite fields, thesis, University of Georgia, in preparation.

[52]
A. McIver and P. M. Neumann, Enumerating finite groups, Quart. J. Math. Oxford Ser. (2) 38(1987), 473-488. MR 916229 (89a:11097)

[53]
A. M. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, Advances in Cryptology (T. Beth, N. Cot, and I. Ingemarsson, eds.), Lecture Notes in Comput. Sci., vol. 209, Springer, Berlin, 1985, pp. 224-314. MR 825593 (87g:11022)

[54]
P. P. Pálfy, A polynomial bound for the orders of primitive solvable groups, J. Algebra 77 (1982), 127-137. MR 665168 (84c:20007)

[55]
M. E. Pohst, Three principal tasks of computational algebraic number theory, Number Theory and Applications (R. A. Mollin, ed.), Kluwer, Dordrecht, 1989, pp. 123-133. MR 1123072 (92f:11182)

[56]
M. Pohst and H. Zassenhaus, Algorithmic algebraic number theory, Cambridge Univ. Press, Cambridge, 1989. MR 1033013 (92b:11074)

[57]
C. Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, Discrete Algorithms and Complexity (D. S. Johnson, T. Nishizeki, A. Nozaki, and H. S. Wilf, eds.), Academic Press, Orlando, 1987, pp. 119-143. MR 910929 (88m:11109)

[58]
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.

[59]
J. W. Sands, Generalization of a theorem of Siegel, Acta Arith. 58 (1991), 47-57. MR 1111089 (92c:11134)

[60]
O. Schirokauer, Discrete logarithms and local units, in preparation.

[61]
R. J. Schoof, Quadratic fields and factorization, Computational Methods in Number Theory (H. W. Lenstra, Jr. and R. Tijdeman, eds.), Math. Centre Tracts., vol. 154/155, Mathematisch Centrum Amsterdam, 1982, pp. 235-286. MR 702519 (85g:11118b)

[62]
-, Elliptic curves over finite fields and the computation of square roots $ {\bmod \; p}$, Math. Comp. 44 (1985), 483-494. MR 777280 (86e:11122)

[63]
J-P. Serre, Arbres, amalgames, $ {\text{S}}{{\text{L}}_2}$, Astérisque 46 (1977).

[64]
-, Lectures on the Mordell-Weil theorem, Vieweg, Braunschweig, 1989. MR 1002324 (90e:11086)

[65]
D. Shanks, The infrastructure of a real quadratic field and its applications, Proceedings of the 1972 number theory conference, Univ. of Colorado, Boulder, CO, 1972, pp. 217-224. MR 0389842 (52:10672)

[66]
V. Shoup, New algorithms for finding irreducible polynomials over finite fields, Math. Comp. 54(1990), 435-447. MR 993933 (90j:11135)

[67]
-, On the deterministic complexity of factoring polynomials over finite fields, Inform. Process. Lett. 33 (1990), 261-267. MR 1049276 (91f:11088)

[68]
C. L. Siegel, Abschätzung von Einheiten, Nachr. Akad. Wiss. Göttingen Math.-Phys. K1. 1969, pp. 71-86; Gesammelte Abhandlungen, Band IV, Springer, Berlin, 1979, pp. 66-81. MR 0249395 (40:2640)

[69]
R. P. Stauduhar, The determination of Galois groups, Math. Comp. 27 (1973), 981-996. MR 0327712 (48:6054)

[70]
L. Szpiro, Présentation de la théorie d'Arakélov, Current Trends in Arithmetical Algebraic Geometry (K. A. Ribet, ed.), Contemp. Math., vol. 67, Amer. Math. Soc, Providence, RI, 1987, pp. 279-293. MR 902589 (88c:14001)

[71]
J. Teitelbaum, The computational complexity of the resolution of plane curve singularities, Math. Comp. 54 (1990), 797-837. MR 1010602 (90j:14007)

[72]
N. Tzanakis and B. M. M. de Weger, How to solve explicitly a Thue-Mahler equation (to appear).

[73]
F. J. van der Linden, The computation of Galois groups, Computational Methods in Number Theory (H. W. Lenstra, Jr. and R. Tijdeman, eds.), Math. Centre Tracts., vol. 154/155, Mathematisch Centrum Amsterdam, 1982, pp. 199-211. MR 702517 (85f:11078)

[74]
P. van Emde Boas, Machine models, computational complexity and number theory, Computational Methods in Number Theory (H. W. Lenstra, Jr. and R. Tijdeman, eds.), Math. Centre Tracts., vol. 154/155, Mathematisch Centrum Amsterdam, 1982, pp. 7-42. MR 700256 (85d:68028)

[75]
E. Weiss, Algebraic number theory, McGraw-Hill, New York, 1963; reprinted, Chelsea, New York, 1976. MR 0159805 (28:3021)

[76]
H. Zantema, Class numbers and units, Computational Methods in Number Theory (H. W. Lenstra, Jr. and R. Tijdeman, eds.), Math. Centre Tracts., vol. 154/155, Mathematisch Centrum Amsterdam, 1982, pp. 212-234. MR 702518 (85g:11118a)

[77]
H. Zassenhaus, Ein Algorithmus zur Berechnung einer Minimalbasis über gegebener Ordnung, Funktionalanalysis, Approximationstheorie, numerische Mathematik, Oberwolfach 1965 (L. Collatz, G. Meinardus, and H. Unger, eds.), Birkhäuser, Basel, 1967, pp. 90-103. MR 0227135 (37:2720)

[78]
H. G. Zimmer, Computational problems, methods and results in algebraic number theory, Lecture Notes in Math., vol. 262, Springer, Berlin, 1972. MR 0323751 (48:2107)

Similar Articles:

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2000): 11Y40, 11R27, 11R29

Retrieve articles in all Journals with MSC (2000): 11Y40, 11R27, 11R29

Additional Information:

DOI: 10.1090/S0273-0979-1992-00284-7
PII: S 0273-0979(1992)00284-7
Keywords: Algebraic number theory, algorithms, complexity theory
Copyright of article: Copyright 1992, American Mathematical Society




AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia