A parallel multi-modular algorithm for computing Lagrange resolvents. (English) Zbl 1137.12302
Summary: The aim of this paper is to exploit the algorithms of paper [ the author and A. Valibouze, Exp. Math. 8, No. 4, 351–366 (1999; Zbl 1002.12004)] in order to produce a new algebraic method for computing efficiently absolute Lagrange resolvent, a fundamental tool in constructive algebraic Galois theory. This article is composed of two parts. The main idea of the first part is to break up the calculation of absolute resolvent into smaller computations. Since a multi-resolvent is a factor of a resolvent, the whole resolvent may be computed by means of several multi-resolvents. The idea of the second part is that an irreducible polynomial over \(\mathbb Z\) might be reducible over \(\mathbb Z/ p \mathbb Z\) for certain integer \(p\). So the first part can be applied and then, the Chinese remainder theorem allows to lift up the resolvent over \(\mathbb Z\).
MSC:
| 12F10 | Separable extensions, Galois theory |
| 12Y05 | Computational aspects of field theory and polynomials (MSC2010) |
| 68W10 | Parallel algorithms in computer science |
Citations:
Zbl 1002.12004Software:
GAPReferences:
| [1] | Arnaudiès, J.-M.; Valibouze, A., Lagrange resolvents, J. Pure Appl. Algebra, 117-118, 23-40 (1997) · Zbl 0945.12004 |
| [3] | Butler, G.; McKay, J., The transitive groups of degree up to eleven, Commun. Algebra, 11, 863-911 (1983) · Zbl 0518.20003 |
| [4] | Casperson, D.; McKay, J., Symmetric functions, \(m\)-sets, and Galois groups, Math. Comput., 63, 749-757 (1994) · Zbl 0839.05094 |
| [5] | Eichenlaub, Y.; Olivier, M., 1996. Galp sotfware |
| [6] | Encarnación, M. J., Factoring polynomial over algebraic number fields via norms, (Oliver, G., Proceedings of ISSAC’97 (1997), ACM Press), 265-270 · Zbl 0924.11101 |
| [7] | Geddes, K. O.; Czapor, S. R.; Labahn, G., Algorithm for Computer Algebra (1993), Kluwer Academic Publisher |
| [9] | Lagrange, J.-L., (Réflexions sur la Résolution Algébrique des Équations. Réflexions sur la Résolution Algébrique des Équations, Œuvres de Lagrange, vol. 3 (1869), Gauthier-Villars: Gauthier-Villars Paris), 205-421, Nouveaux Mémoires de l’Académie royale des Sciences et Belles-Lettres de Berlin, années 1770 et 1771 |
| [10] | Lehobey, F., Resolvent computations by resultants without extraneous powers, (Proceedings of ISSAC’97 (1997), ACM) · Zbl 1113.12301 |
| [12] | Mignotte, M., Some useful bounds. Computer Algebra, Symbolic and Algebraic Computation Comput. Suppl. (4) (1982), 259-263 · Zbl 0498.12019 |
| [13] | Rennert, N.; Valibouze, A., Calcul de résolvantes avec les modules de Cauchy, Experimental Math., 8 (1999) · Zbl 1002.12004 |
| [14] | Schönert, M., GAP—Groups, Algorithms, and Programming, Lehrstuhl D für Mathematik. Rheinisch Westfä lische Technische Hochschule (1995), Aachen: Aachen Germany |
| [15] | Stauduhar, R. P., The determination of Galois groups, Math. Comput., 27, 981-996 (1973) · Zbl 0282.12004 |
| [17] | Valibouze, A., SYM, symbolic computation with symmetric polynomials an extension to MACSYMA, (Computers and Mathematics (Proceeding of a Conference 13-17, 1989 Massachusetts Institute of Technology, Cambridge, MA) (1989), Springer-Verlag), 308-320 · Zbl 0694.68025 |
| [18] | Valibouze, A., Computation of the Galois groups of the resolvent factors for the direct and inverse Galois problems, (Cohen, G.; Giusti, M.; Mora, T., Proceedings of AAECC’95. Proceedings of AAECC’95, Lecture Notes in Computer Science, vol. 948 (1995), Springer-Verlag), 456-468 · Zbl 0887.12007 |
| [19] | Valibouze, A., Etude des relations algébriques entre les racines d’un polynôme d’une variable, Bull. Belgian Math. Soc., 6, 507-535 (1999) · Zbl 0943.12001 |
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.
