|
Algorithms in Algebraic Number Theory
Author(s):
H.
W.
Lenstra Jr.
Journal:
Bull. Amer. Math. Soc.
26
(1992),
211-244.
MSC (1980):
Primary 11Y16, 11Y40
MathSciNet review:
1129315
Retrieve article in:
PDF
References |
Similar articles |
Additional information
References:
- [1]
- L. M. Adleman and M. A. Huang, Recognizing primes in random polynomialtime, Research report, Dept. of Computer Science, Univ. of Southern California, 1988. MR
- [2]
- L. M. Adleman and H. W. Lenstra, Jr., \emph{Finding irreducible polynomials over finite fields}, ACM, New York \nofrills, \nofrills (1986,350--355. MR
- [3]
- L. M. Adleman, C. Pomerance, and R. S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) \textbf{117} (1983), 173--206. MR 683806
- [4]
- Archimedes, \emph{The sand-reckoner}, J. Hervagius, Basel, 1544. (Greek and Latin) MR
- [5]
- A. O. L. Atkin and F. Morain, Elliptic curves and primality proving. MR
- [6]
- E. Bach, Explicit bounds for primality testing and related problems, Math. Comp. \textbf{55} (1990), 355--380. MR 1023756
- [7]
- E. Bach and J. O. Shallit, Factor refinement, J. Algorithms. MR
- [8]
- W. E. H. Berwick, Integral bases, Cambridge Univ. Press, Cambridge, 1927. MR
- [9]
- Z. I. Borevi\v c and I. R. \v Safarevi\v c, Teorija \v cisel, Izdat. ``Nauka'', Moscow, 1964. MR 170845
- [10]
- W. Bosma and M. P. M. van der Hulst, \emph{Primality proving with cyclotomy}, 1990. MR
- [11]
- E. Brieskorn and H. Kn\"orrer, Ebene algebraische Kurven, Birkh\"auser, Basel, 1981. MR 646612
- [12]
- J. Buchmann, \emph{Complexity of algorithms in algebraic number theory} (R. A. Mollin, ed.), De Gruyter, Berlin, 1990 pp.~37--53. MR 1106649
- [13]
- J. Buchmann, \emph{A subexponential algorithm for the determination of class groups and regulators of algebraic number fields} (C. Goldstein, ed.), Birkh\"auser, Boston, 1990 pp.~27--41. MR 1104698
- [14]
- J. Buchmann and H. W. Lenstra, Jr., Manuscript in preparation. MR
- [15]
- J. Buchmann and V. Shoup, Constructing nonresidues in finite fields and the extended Riemann hypothesis, in preparation \afterall Extended abstract: Proc. 23rd Ann. ACM Sympos. on Theory of Computing (STOC), ACM, New York 1991, pp. 72--79. MR
- [16]
- J. Buchmann and H. C. Williams, On the computation of the class number of an algebraic number field, Math. Comp. \textbf{53} (1989), \nofrills 679--688. MR 979937
- [17]
- J. P. Buhler, H. W. Lenstra, Jr., and C. Pomerance, Factoring integers with the number field sieve, in preparation. MR
- [18]
- P. J. Cameron, Finite permutation groups and finite simple groups, Bull. London Math. Soc. \textbf{13} (1981), 1--22. MR 599634
- [19]
- J. W. S. Cassels, Local fields, Cambridge Univ. Press, Cambridge, 1986. MR 861410
- [20]
- J. W. S. Cassels and A. Fr\"ohlich (eds.), \emph{Algebraic number theory}, Academic Press, London, 1967. MR 215665
- [21]
- A. L. Chistov, Efficient factorization of polynomials over local fields, Dokl. Akad. Nauk SSSR \textbf{293} (1987), 1073--1077. MR 890201
- [22]
- A. L. Chistov, The complexity of constructing the ring of integers of a global field, Dokl. Akad. Nauk SSSR \textbf{306} (1989), 1063--1067. MR 1014763
- [23]
- H. Cohen, A course in computational algebraic number theory, in preparation. MR
- [24]
- H. Cohen and A. K. Lenstra, Implementation of a new primality test, Math. Comp. \textbf{48} (1987), 103--121. MR 866102
- [25]
- H. Cohen and H. W. Lenstra, Jr., Primality testing and Jacobi sums, Math. Comp. \textbf{42} (1984), 297--330. MR 726006
- [26]
- D. J. Ford and J. McKay, \emph{Computation of Galois groups from polynomials over the rationals}, Lecture Notes in Pure and Appl. Math. vol.~113, Marcel Dekker, New York, 1989 pp.~145--150. MR 1002982
- [27]
- D. Gordon, Discrete logarithms using the number field sieve. MR
- [28]
- J. L. Hafner and K. S. McCurley, A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc. \textbf{2} (1989), 837--850. MR 1002631
- [29]
- J. L. Hafner and K. S. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. MR 1135749
- [30]
- R. Kannan, \emph{Algorithmic geometry of numbers}, Annual Reviews Inc., Palo Alto, 1987 pp.~231--267. MR 921497
- [31]
- W. M. Kantor, unpublished. MR
- [32]
- W. M. Kantor and E. M. Luks, \emph{Computing in quotient groups}, ACM, \nofrills New York, 1990 pp.~524--534. MR
- [33]
- D. E. Knuth, \emph{The art of computer programming}, Vol. 2, Addison-Wesley, Reading, MA, second edition, 1981. MR 633878
- [34]
- S. Landau, \emph{Polynomial time algorithms for Galois groups} (J. Fitch, ed.), Lecture Notes in Comput. Sci. vol.~174, Springer, Berlin, 1984 pp.~225--236. MR 779128
- [35]
- S. Landau, Factoring polynomials over algebraic number fields, SIAM J. Comput. \textbf{14} (1985), 184--195. MR 774938
- [36]
- S. Landau and G. L. Miller, Solvability by radicals is in polynomial time, J. Comput. System Sci. \textbf{30} (1985), 179--208. MR 801822
- [37]
- S. Lang, Algebraic number theory, Addison-Wesley, Reading, MA, 1970. MR 282947
- [38]
- A. K. Lenstra, \emph{Factorization of polynomials}, Math. Centre Tracts. vol.~154/155, Mathematisch Centrum Amsterdam, 1982 pp.~169--198. MR 700263
- [39]
- A. K. Lenstra, \emph{Factoring polynomials over algebraic number fields} ((J. A. van Hulzen, ed.) \nofrills, eds.), Lecture Notes in Comput. Sci. vol.~162, Springer, Berlin, 1983 pp.~245--254. MR 774816
- [40]
- A. K. Lenstra, Factoring multivariate polynomials over algebraic number fields, SIAM J. Comput. \textbf{16} (1987), 591--598. MR 889410
- [41]
- A. K. Lenstra and H. W. Lenstra, Jr., \emph{Algorithms in number theory} (J.~van Leeuwen, ed.), Elsevier, Amsterdam, 1990 pp.~673--715. MR 1127178
- [42]
- A. K. Lenstra, H. W. Lenstra, Jr., and L. Lov\'asz, Factoring polynomials with rational coefficients, Math. Ann. \textbf{261} (1982), 515--534. MR 682664
- [43]
- A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The factorization of the ninth Fermat number. MR
- [44]
- A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The number field sieve, in preparation \afterall Extended abstract: Proc. 22nd Ann. ACM Sympos. on Theory of Computing (STOC), ACM, New York 1990, pp. 564--572. MR
- [45]
- H. W. Lenstra, Jr., \emph{On the calculation of regulators and class numbers of quadratic fields} (J. Armitage, ed.), London Math. Soc. Lecture Note Ser. vol.~56, Cambridge Univ. Press, Cambridge, 1982 pp.~123--150. MR 697260
- [46]
- H. W. Lenstra, Jr., \emph{Galois theory and primality testing} (J. Armitage, eds.), Lecture Notes in Math. vol.~1142, Springer, Heidelberg, 1985 pp.~169--189. MR 812498
- [47]
- H. W. Lenstra, Jr., \emph{Algorithms for finite fields} (J. H. Loxton, eds.), London Math. Soc. Lecture Note Ser. vol.~154, Cambridge Univ. Press, Cambridge, 1990 pp.~76--85. MR 1055400
- [48]
- H. W. Lenstra, Jr., Finding isomorphisms between finite fields, Math. Comp. \textbf{56} (1991), 329--347. MR 1052099
- [49]
- H. W. Lenstra, Jr. and C. Pomerance, A rigorous time bound for factoring integers, J. Amer. Math. Soc. MR
- [50]
- H. W. Lenstra, Jr. and R. Tijdeman (eds.), \emph{Computational methods in number theory} vol.~154/155, Mathematisch Centrum, Amsterdam, 1982. MR
- [51]
- R. Lovorn, Rigorous, subexponential algorithms for discrete logarithms over finite fields, thesis, University of Georgia, in preparation. MR
- [52]
- A. McIver and P. M. Neumann, Enumerating finite groups, Quart. J. Math. Oxford Ser. (2) \textbf{38} (1987), 473--488. MR 916229
- [53]
- A. M. Odlyzko, \emph{Discrete logarithms in finite fields and their cryptographic significance}, Lecture Notes in Comput. Sci. vol.~209, Springer, Berlin, 1985 pp.~224--314. MR 825593
- [54]
- P. P. P\'alfy, A polynomial bound for the orders of primitive solvable groups, J. Algebra \textbf{77} (1982), 127--137. MR 665168
- [55]
- M. E. Pohst, \emph{Three principal tasks of computational algebraic number theory} (R. A. Mollin, ed.), Kluwer, Dordrecht, 1989 pp.~123--133. MR 1123072
- [56]
- M. Pohst and H. Zassenhaus, Algorithmic algebraic number theory, Cambridge Univ. Press, Cambridge, 1989. MR 1033013
- [57]
- C. Pomerance, \emph{Fast, rigorous factorization and discrete logarithm algorithms}, Academic Press, Orlando, 1987 pp.~119--143. MR 910929
- [58]
- R. Qu\^eme, Relations d'in\'egalit\'es effectives en th\'eorie alg\'ebrique des nombres, S\'em. Th\'eor. Nombres Bordeaux, (\nofrills 1987--1988,) 19-01--19-19. MR
- [59]
- J. W. Sands, Generalization of a theorem of Siegel, Acta Arith. \textbf{58} (1991), 47--57. MR 1111089
- [60]
- O. Schirokauer, Discrete logarithms and local units, in preparation. MR
- [61]
- R. J. Schoof, \emph{Quadratic fields and factorization}, Math. Centre Tracts. vol.~154/155, Mathematisch Centrum Amsterdam, 1982 pp.~235--286. MR 702519
- [62]
- R. J. Schoof, Elliptic curves over finite fields and the computation of square roots \RM {mod}\,$p$, Math. Comp. \textbf{44} (1985), 483--494. MR 777280
- [63]
- J-P. Serre, Arbres, amalgames, ${\roman { SL}}_2$, Ast\'erisque \textbf{46} (1977). MR 476875
- [64]
- J-P. Serre, Lectures on the Mordell-Weil theorem, Vieweg, Braunschweig, 1989. MR 1002324
- [65]
- D. Shanks, \emph{The infrastructure of a real quadratic field and its applications}, 1972 pp.~217--224. MR 389842
- [66]
- V. Shoup, New algorithms for finding irreducible polynomials over finite fields, Math. Comp. \textbf{54} (1990), 435--447. MR 993933
- [67]
- V. Shoup, On the deterministic complexity of factoring polynomials over finite fields, Inform. Process. Lett. \textbf{33} (1990), 261--267. MR 1049276
- [68]
- C. L. Siegel, \emph{Absch\"atzung von Einheiten}, 1969 pp.~71--86. MR 249395
- [69]
- R. P. Stauduhar, The determination of Galois groups, Math. Comp. \textbf{27} (1973), 981--996. MR 327712
- [70]
- L. Szpiro, \emph{Pr\'esentation de la th\'eorie d'Arak\'elov} (K. A. Ribet, ed.), Contemp. Math. vol.~67, Amer. Math. Soc., Providence, RI, 1987 pp.~279--293. MR 902599
- [71]
- J. Teitelbaum, The computational complexity of the resolution of plane curve singularities, Math. Comp. \textbf{54} (1990), 797--837. MR 1010602
- [72]
- N. Tzanakis and B. M. M. de Weger, How to solve explicitly a Thue-Mahler equation. MR
- [73]
- F. J. van der Linden, \emph{The computation of Galois groups}, Math. Centre Tracts. vol.~154/155, Mathematisch Centrum Amsterdam, 1982 pp.~199--211. MR 702517
- [74]
- P. van Emde Boas, \emph{Machine models, computational complexity and number theory}, Math. Centre Tracts. vol.~154/155, Mathematisch Centrum Amsterdam, 1982 pp.~7--42. MR 700256
- [75]
- E. Weiss, Algebraic number theory, McGraw-Hill, New York, 1963. MR 159805
- [76]
- H. Zantema, \emph{Class numbers and units}, Math. Centre Tracts. vol.~154/155, Mathematisch Centrum Amsterdam, 1982 pp.~212--234. MR 702518
- [77]
- H. Zassenhaus, \emph{Ein Algorithmus zur Berechnung einer Minimalbasis \"uber gegebener Ordnung}, Birkh\"auser, Basel, 1967 pp.~90--103. MR 227135
- [78]
- H. G. Zimmer, \emph{Computational problems, methods and results in algebraic number theory} vol.~262, Springer, Berlin, 1972. MR 323751
Similar Articles:
Retrieve articles in Bulletin of the American Mathematical Society
with MSC
(1980):
11Y16, 11Y40
Retrieve articles in all Journals with MSC
(1980):
11Y16, 11Y40
Additional Information:
DOI:
10.1090/S0273-0979-1992-00284-7
PII:
S 0273-0979(1992)00284-7
|
