Abstract
Let \({\mathbb {Q}(\alpha _1,\cdots ,\alpha _n)}\) be an algebraic number field. In this paper, we present a modular gcd algorithm for computing the monic gcd, g, of two polynomials \(f_1,f_2\in \mathbb {Q}(\alpha _1,\ldots ,\alpha _n)[x_1,\ldots ,x_k]\). To improve the efficiency of our algorithm, we use linear algebra to find an isomorphism between \(\mathbb {Q}(\alpha _1,\ldots ,\alpha _n)\) and \(\mathbb {Q}(\gamma )\), where \(\gamma \) is a primitive element of \(\mathbb {Q}(\alpha _1,\ldots ,\alpha _n)\). This conversion is performed modulo a prime to prevent expression swell. Next, we use a sequence of evaluation points to convert the multivariate polynomials to univariate polynomials, enabling us to employ the monic Euclidean algorithm. We currently use dense interpolation to recover \(x_2,\dots ,x_k\) in the gcd. In order to reconstruct the rational coefficients in g, we apply the Chinese remaindering and the rational number reconstruction. We present an analysis of the expected time complexity of our algorithm. We have implemented our algorithm in Maple using a recursive dense representation for polynomials.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ben-Or, M., Tiwari, P.: A deterministic algorithm for sparse multivariate polynomial interpolation. In: Proceedings of STOC 1988, pp. 301–309. ACM (1988)
Brown, W.S.: On Euclid’s algorithm and the computation of polynomial greatest common divisors. J. ACM 18, 478–504 (1971)
Collins, G.E.: Subresultants and reduced polynomial remainder sequences. J. ACM 14, 128–142 (1967)
Encarnación, M.J.: Computing GCDs of polynomials over algebraic number fields. J. Symb. Comput. 20, 299–313 (1995)
Fateman, R.: Comparing the speed of programs for sparse polynomial multiplication. SIGSAM Bull. 37(1), 4–15 (2003)
Jiaxiong, H., Monagan, M.: A fast parallel sparse polynomial GCD algorithm. Symb. Comput. 105(1), 28–63 (2021)
Langemyr, L., McCallum, S.: The computation of polynomial greatest common divisors over an algebraic number field. J. Symb. Comput. 8(5), 429–448 (1989)
Lin, X., Maza, M.M., Schost, É.: Fast arithmetic for triangular sets: from theory to practice. J. Symb. Comput. 44(7), 891–907 (2009)
Monagan, M.: Maximal quotient rational reconstruction: an almost optimal algorithm for rational reconstruction. In: Proceedings of ISSAC 2004, pp. 243–249. ACM (2004)
Monagan, M., et al.: Maple 8 Introductory Programming Guide (2003)
Poteaux, A., Schost, É.: Modular composition modulo triangular sets and applications. Comput. Complex. 22, 463–516 (2013)
Poteaux, A., Schost, É.: On the complexity of computing with zero-dimensional triangular sets. J. Symb. Comput. 50, 110–138 (2013)
Smedley, T.: A new modular algorithm for computation of algebraic number polynomial GCDs. In: Proceedings of ISSAC 1989, pp. 91–94. ACM (1989)
Trager, B.M.: Algebraic factoring and rational function integration. In: Proceedings of the Third ACM Symposium on Symbolic and Algebraic Computation, SYMSAC 1976, pp. 219–226. ACM (1976)
van der Hoeven, J., Lecerf, G.: Accelerated tower arithmetic. J. Complex. 55, 101402 (2019)
van der Hoeven, J., Lecerf, G.: Directed evaluation. J. Complex. 60, 101498 (2020)
van Hoeij, M., Monagan, M.: A modular GCD algorithm over number fields presented with multiple extensions. In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ISSAC 2002, pp. 109–116. ACM (2002)
Wang, P., Guy, M.J.T., Davenport, J.H.: P-adic reconstruction of rational numbers. SIGSAM Bull. 16(2), 2–3 (1982)
Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, E.W. (ed.) Symbolic and Algebraic Computation. LNCS, vol. 72, pp. 216–226. Springer, Heidelberg (1979). https://doi.org/10.1007/3-540-09519-5_73
Acknowledgment
This work was supported by Maplesoft and the National Science and Engineering Research Council (NSERC) of Canada.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Ansari, M., Monagan, M. (2023). Computing GCDs of Multivariate Polynomials over Algebraic Number Fields Presented with Multiple Extensions. In: Boulier, F., England, M., Kotsireas, I., Sadykov, T.M., Vorozhtsov, E.V. (eds) Computer Algebra in Scientific Computing. CASC 2023. Lecture Notes in Computer Science, vol 14139. Springer, Cham. https://doi.org/10.1007/978-3-031-41724-5_1
Download citation
DOI: https://doi.org/10.1007/978-3-031-41724-5_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-41723-8
Online ISBN: 978-3-031-41724-5
eBook Packages: Computer ScienceComputer Science (R0)