Multi-modular algorithm for computing the splitting field of a polynomial

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Multi-modular algorithm for computing the splitting field of a polynomial

Full text

Pdf (328 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the twenty-first international symposium on Symbolic and algebraic computation table of contents

Linz/Hagenberg, Austria

SESSION: Contributed papers table of contents

Pages 247-254

Year of Publication: 2008

ISBN:978-1-59593-904-3

Authors

Guénaël Renault	INRIA SALSA Project/LIP6/UPMC, Univ. Paris 06, Paris, France
Kazuhiro Yokoyama	Rikkyo University, Tokyo, Japan

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 38, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1390768.1390803 What is a DOI?

ABSTRACT

Let f be a univariate monic integral polynomial of degree n and let (α₁, ..., α_n) be an n-tuple of its roots in an algebraic closure Q of Q. Obtaining an algebraic representation of the splitting field Q(α₁, ..., α_n) of f is a question of first importance in effective Galois theory. For instance, it allows us to manipulate symbolically the roots of f. In this paper, we propose a new method based on multi-modular strategy. Actually, we provide algorithms for this task which return a triangular set encoding the splitting ideal of f. We examine the ability/practicality of the method by experiments on a real computer and study its complexity.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	I. Abdeljaouad-Tej , S. Orange , G. Renault , A. Valibouze, Computation of the Decomposition Group of a Triangular Ideal, Applicable Algebra in Engineering, Communication and Computing, v.15 n.3, p.279-294, November 2004 [doi>10.1007/s00200-004-0160-x]
	2	J.-M. Arnaudiès and A. Valibouze. Lagrange resolvents. J. Pure Appl. Algebra, 117/118:23--40, 1997. Algorithms for algebra (Eindhoven, 1996).
	3	H. Anai , M. Noro , K. Yokoyama, Computation of the splitting fields and the Galois groups of polynomials, Algorithms in algebraic geometry and applications, Birkhauser Verlag, Basel, Switzerland, 1996
	4	Becker, T., and Weispfenning, V. Gröbner bases, vol. 141 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1993.
	5	Wieb Bosma , John Cannon , Catherine Playoust, The MAGMA algebra system I: the user language, Journal of Symbolic Computation, v.24 n.3-4, p.235-265, Sept./Oct. 1997 [doi>10.1006/jsco.1996.0125]
	6	Xavier Dahan , Éric Schost, Sharp estimates for triangular sets, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.103-110, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005302]
	7	Fieker, C. and Graaf, W. Integral linear dependencies of algebraic numbers and algebraic Lie algebras. LMS J. Comput. Math., 10 (2007), 271--287
	8	Joachim Von Zur Gathen , Jurgen Gerhard, Modern Computer Algebra, Cambridge University Press, New York, NY, 2003
	9	Geissler, K. Berechnung von Galoisgruppen über Zhal- und Funktionenkörpern. PhD thesis, Univ. Berlin, 2003.
	10	Katharina Geissler , Jürgen Klüners, Galois group computation for rational polynomials, Journal of Symbolic Computation, v.30 n.6, p.653-674, Dec. 2000 [doi>10.1006/jsco.2000.0377]
	11	Klüners, J., and Malle, G. A database for field extensions of the rationals. LMS J. Comput. Math. 4 (2001), 182--196 (electronic).
	12	D. Lazard, Solving zero-dimensional algebraic systems, Journal of Symbolic Computation, v.13 n.2, p.117-131, Feb. 1992 [doi>10.1016/S0747-7171(08)80086-7]
	13	Lederer, M., Explicit constructions in splitting fields of polynomials. Riv. Mat. Univ. Parma (7), 3* (2004), 233--244.
	14	John McKay , Richard Stauduhar, Finding relations among the roots of an irreducible polynomial, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.75-77, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258752]
	15	Xinmao Wang , Victor Y. Pan, Acceleration of Euclidean Algorithm and Rational Number Reconstruction, SIAM Journal on Computing, v.32 n.2, p.548-556, 2003 [doi>10.1137/S0097539702408636]
	16	M. Pohst , H. Zassenhaus, Algorithmic algebraic number theory, Cambridge University Press, New York, NY, 1989
	17	Guénaël Renault, Computation of the splitting field of a dihedral polynomial, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145816]
	18	Renault, G., and Yokoyama, K. A modular method for computing the splitting field of a polynomial. In Proc. of the 7th Algorithmic Number Theory Symposium ANTS-VII, Berlin, Germany, 2006, LNCS 4076, Springer, pp. 124--140.
	19	N. Rennert and A. Valibouze. Calcul de résolvantes avec les modules de Cauchy. Exp. Math., 8(4):351--366, 1999.
	20	Tchebotarev, N. Gründzüge des Galois'shen Theorie. P. Noordhoff, 1950.
	21	Yokoyama, K. A modular method for computing the Galois groups of polynomials. J. Pure Appl. Algebra 117/118 (1997), 617--636.