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
HTML articles powered by AMS MathViewer

by Bill Allombert PDF

Math. Comp. 73 (2004), 359-375 Request permission

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.

References

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 10.1090/S0025-5718-99-01084-4
List of polynomials of the benchmark, http://www.math.u-bordeaux.fr/~allomber/nfgaloisconj_benchmark.html
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
Marshall Hall Jr., The theory of groups, The Macmillan Company, 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 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 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.