×

Block systems of a Galois group. (English) Zbl 0976.12006

From the text: The author describes an algorithm to compute subfields of an algebraic number field as block systems of its Galois group. The algorithm presented here has some advantages over others in the literature. It avoids unnecessarily hard computations (even though its worst case complexity may be the same) by embedding the algebraic extension in an appropriate \(p\)-adic field and building blocks from stabilizer orbits as suggested by [M. Schönert and Á. Seress, Proc. ISSAC ’94, 154-157 (1994; Zbl 0925.20009)]. It also avoids numerical approximations and relies on exact algebraic computations only. The final section compares the performance of previous algorithms with the one given here. The comparison includes a polynomial reduction algorithm [H. Cohen and F. Diaz y Diaz, Sém. Théorie Nombres Bord. Sér. II 3, 351-360 (1991; Zbl 0758.11053)] that runs very fast in general and sometimes, but not always, yields subfields.

MSC:

12Y05 Computational aspects of field theory and polynomials (MSC2010)
12F10 Separable extensions, Galois theory
20B40 Computational methods (permutation groups) (MSC2010)
11Y40 Algebraic number theory computations

Software:

PARI/GP; GAP; Maple
PDFBibTeX XMLCite
Full Text: DOI Euclid EuDML EMIS

References:

[1] Abbott J. A., Ph.D. thesis, in: ”On the factorization of polynomials over algebraic fields” (1989)
[2] DOI: 10.1007/BF01445238 · Zbl 0713.11036 · doi:10.1007/BF01445238
[3] Atkinson M., Math. Comp. pp 911– (1975) · doi:10.1090/S0025-5718-1975-0367030-3
[4] Batut C., User’s Guide to Pari-GP.
[5] Casperson David, Abstracts Amer. Math. Soc. 13 pp 405– (1992)
[6] Casperson David, ”An ideal decomposition algorithm” · Zbl 0849.68071
[7] Char B. W., Maple V Language Reference Manual and Maple V Library Reference Manual (1991) · doi:10.1007/978-1-4615-7386-9
[8] Cohen Henri, Séminaire de théorie des nombres de Bordeaux pp 351– (1991) · Zbl 0758.11053 · doi:10.5802/jtnb.55
[9] Dixon John D., J. Australian Math. Soc. 49 pp 434– (1990) · doi:10.1017/S1446788700032432
[10] Geyer Helmut, ”Programme zur Berechnung der Galoisgruppen von Polynomen 8. und 9. Grades” (1993)
[11] Landau Susan, SIGSAM Bull. 27 (3) (1993)
[12] Lenstra A. K., Computer algebra: EUROCAM ’82 144 pp 32– (1982) · doi:10.1007/3-540-11607-9_4
[13] Lenstra A. K., Computer algebra: EUROCAL ’83 pp 245– (1983)
[14] DOI: 10.1007/BF01457454 · Zbl 0488.12001 · doi:10.1007/BF01457454
[15] Landau Susan, J. Comp. Sys. Sci. 30 pp 179– (1985) · Zbl 0586.12002 · doi:10.1016/0022-0000(85)90013-3
[16] Lagarias J. C., Algebraic Number Fields (L-functions and Galois properties) pp 409– (1977)
[17] Lazard Daniel, Computational Algebraic Geometry pp 163– (1993) · doi:10.1007/978-1-4612-2752-6_11
[18] Mattman T. W., ”Computation of Galois groups over function fields” · Zbl 0946.12002
[19] Schönert M., GAP: Groups, Algorithms, and Programming (1994)
[20] Schönert Martin, ”Finding blocks of imprimitivity in small base groups in nearly linear time” (1994) · Zbl 0925.20009 · doi:10.1145/190347.190400
[21] Leonard H., J. Number Theory 20 pp 273– (1985) · Zbl 0579.12006 · doi:10.1016/0022-314X(85)90022-8
[22] Trager, Barry M. ”Algebraic factoring and rational function integration’. Proceedings of the 1976 ACM Symposium on symbolic and algebraic computation. Edited by: Jenks, R. D. pp.219–226. New York: ACM. [Trager 1976] · Zbl 0498.12005
[23] Tschebotareff Nikolaj, Math. Annalen 95 pp 191– (1925) · JFM 51.0149.04 · doi:10.1007/BF01206606
[24] Weinberger P. J., ACM Trans. Math. Software pp 335– (1976) · Zbl 0352.12003 · doi:10.1145/355705.355709
[25] Zippel R., J. Symb. Comp. pp 189– (1985) · Zbl 0574.12002 · doi:10.1016/S0747-7171(85)80014-6
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.