Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Computing automorphisms
of abelian number fields

Authors: Vincenzo Acciaro and Jürgen Klüners
Journal: Math. Comp. 68 (1999), 1179-1186
MSC (1991): Primary 11R37; Secondary 11Y40
Published electronically: February 8, 1999
MathSciNet review: 1648426
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $L=\mathbb{Q}(\alpha)$ be an abelian number field of degree $n$. Most algorithms for computing the lattice of subfields of $L$ require the computation of all the conjugates of $\alpha$. This is usually achieved by factoring the minimal polynomial $m_{\alpha}(x)$ of $\alpha$ over $L$. In practice, the existing algorithms for factoring polynomials over algebraic number fields can handle only problems of moderate size. In this paper we describe a fast probabilistic algorithm for computing the conjugates of $\alpha$, which is based on $p$-adic techniques. Given $m_{\alpha}(x)$ and a rational prime $p$ which does not divide the discriminant $\operatorname{disc} (m_{\alpha}(x))$ of $m_{\alpha}(x)$, the algorithm computes the Frobenius automorphism of $p$ in time polynomial in the size of $p$ and in the size of $m_{\alpha}(x)$. By repeatedly applying the algorithm to randomly chosen primes it is possible to compute all the conjugates of $\alpha$.

References [Enhancements On Off] (What's this?)

  • 1. V. Acciaro, The probability of generating some common families of finite groups, Utilitas Mathematica 49 (1996), 243-254. MR 97c:20106
  • 2. E. Bach and J. Sorenson, Explicit bounds for primes in residue classes, Math. Comp. 65 (1996), 1717-1735. MR 97a:11143
  • 3. H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, Berlin, 1993. MR 94i:11105
  • 4. G.E. Collins and M.J. Encarnación, Efficient rational number reconstruction, J. Symb. Comput. 20 (1995), 287-297. MR 97c:11116
  • 5. M. Daberkow, C. Fieker, J. Klüners, M. Pohst, K. Roegner, M. Schörnig, K. Wildanger, KANT V4, J. Symb. Comput. 24 (1997), 267-283. CMP 98:05
  • 6. J.D. Dixon, Computing subfields in algebraic number fields, J. Austral. Math. Soc. 49 (1990), 434-448. MR 91h:11156
  • 7. J. Klüners and M. Pohst, On computing subfields, J. Symb. Comput. 24 (1997), 385-397. MR 98k:11161
  • 8. J.C. Lagarias and A.M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic number fields (A. Fröhlich, ed.), Academic Press, 1977, 409-464. MR 56:5506
  • 9. S. Landau, Factoring polynomials over algebraic number fields, SIAM J. Comput. 14 (1985), 184-195; errata, ibid. 20 (1991), 998. MR 86d:11102; MR 92f:11181
  • 10. S. Lang, Algebra, Addison-Wesley, Reading, Massachusetts, 1984. MR 86j:00003
  • 11. S. Lang, Algebraic Number Theory, 2nd ed., Springer-Verlag, Berlin, 1994. MR 95f:11085
  • 12. H.W. Lenstra, Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc. 26 (1992), 211-244. MR 93g:11131
  • 13. K. Mahler, An inequality for the discriminant of a polynomial, Michigan Math. J. 11 (1964), 257-262. MR 29:3465
  • 14. M. Mignotte, Mathematics for Computer Algebra, Springer-Verlag, New York, 1992. MR 92i:68071
  • 15. P.S. Wang, Factoring multivariate polynomials over algebraic number fields, Math. Comp. 30 (1976), 324-336. MR 58:27887a
  • 16. M.E. Pohst and H. Zassenhaus, Algorithmic Algebraic Number Theory, Cambridge University Press, Cambridge, 1989. MR 92b:11074

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11R37, 11Y40

Retrieve articles in all journals with MSC (1991): 11R37, 11Y40

Additional Information

Vincenzo Acciaro
Affiliation: Dipartimento di Informatica, Università degli Studi di Bari, via E. Orabona 4, Bari 70125, Italy

Jürgen Klüners
Affiliation: Universität Heidelberg, Im Neuenheimer Feld 368, 69120 Heidelberg, Germany

Keywords: Computational number theory, abelian number fields, automorphisms
Received by editor(s): December 6, 1995
Received by editor(s) in revised form: July 29, 1996
Published electronically: February 8, 1999
Article copyright: © Copyright 1999 American Mathematical Society

American Mathematical Society