An efficient algorithm for the computation of Galois automorphisms

Allombert, Bill

doi:10.1090/S0025-5718-03-01476-5

An efficient algorithm for the computation of Galois automorphisms

Author: Bill Allombert
Journal: Math. Comp. 73 (2004), 359-375
MSC (2000): Primary 11Y40
DOI: https://doi.org/10.1090/S0025-5718-03-01476-5
Published electronically: July 17, 2003
MathSciNet review: 2034127
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We describe an algorithm for computing the Galois automorphisms of a Galois extension which generalizes the algorithm of Acciaro and Klüners to the non-Abelian case. This is much faster in practice than algorithms based on LLL or factorization.

John Abbott, Victor Shoup and Paul Zimmerman, Factorization in $\mathbb {Z}[x]$: The Searching Phase (Carlo Traverso, ed.), Proc. ISSAC 2000, ACM Press, 2000, pp. 1–7. http://www.shoup.net/papers/asz.ps.Z.

Vincenzo Acciaro and Jürgen Klüners, Computing automorphisms of abelian number fields, Math. Comp. 68 (1999), no. 227, 1179–1186. MR 1648426, DOI https://doi.org/10.1090/S0025-5718-99-01084-4

List of polynomials of the benchmark, http://www.math.u-bordeaux.fr/~allomber/nfgaloisconj_{b}enchmark.html

Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206

Marshall Hall Jr., The theory of groups, The Macmillan Co., New York, N.Y., 1959. MR 0103215

Jürgen Klüners, Über die Berechnung von Automorphismen und Teilkörpern algebraischer Zahlkörper, Thesis, Technischen Universitat Berlin, 1997.

Jürgen Klüners, On computing subfields. A detailed description of the algorithm, J. Théor. Nombres Bordeaux 10 (1998), no. 2, 243–271 (English, with English and French summaries). MR 1828244

Jürgen Klüners and Gunter Malle, Explicit Galois realization of transitive groups of degree up to 15, J. Symbolic Comput. 30 (2000), no. 6, 675–716. Algorithmic methods in Galois theory. MR 1800033, DOI https://doi.org/10.1006/jsco.2000.0378

M. Daberkow, C. Fieker, J. Klüners, M. Pohst, K. Roegner, M. Schörnig, and K. Wildanger, KANT V4, J. Symbolic Comput. 24 (1997), no. 3-4, 267–283. Computational algebra and number theory (London, 1993). MR 1484479, DOI https://doi.org/10.1006/jsco.1996.0126

W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: The user language, J. Symb. Comput., 24, 1997, 235–265.

PARI, C. Batut, K. Belabas, D. Bernardi, H. Cohen and M. Olivier, User’s Guide to PARI-GP, version 2.2.1.

Xavier Roblot, Algorithmes de factorisation dans les extensions relatives et applications de la conjecture de Stark à la construction de corps de classes de rayon, Thesis, Université Bordeaux I, 1997.