Solving polynomial systems
Ding J, Petzoldt A, Schmidt DS (2020)
Publication Type: Book chapter / Article in edited volumes
Publication year: 2020
Publisher: Springer
Edited Volumes: Multivariate Public Key Cryptosystems
Series: Advances in Information Security
City/Town: New York
Book Volume: 80
Pages Range: 185-248
ISBN: 978-1-0716-0987-3
DOI: 10.1007/978-1-0716-0987-3_8
Abstract
This chapter considers the known techniques to solve (systems of) nonlinear polynomial equations. After giving a historical overview of the topic, we describe algorithms to solve univariate polynomials of high degree. The remainder of the chapter deals with algorithms to solve systems of nonlinear multivariate polynomials. We describe the XL algorithm, give a short introduction into the theory of Gröbner bases and present the most important algorithms to compute these bases. After analyzing the complexity of these algorithms against various types of multivariate polynomial systems, we end this chapter by giving an overview of the known algorithms used to solve over and underdetermined systems of multivariate quadratic equations.
Authors with CRIS profile
Involved external institutions
United States (USA) (US)How to cite
APA:
Ding, J., Petzoldt, A., & Schmidt, D.S. (2020). Solving polynomial systems. In Jintai Ding, Albrecht Petzoldt, Dieter S. Schmidt (Eds.), Multivariate Public Key Cryptosystems. (pp. 185-248). New York: Springer.
MLA:
Ding, Jintai, Albrecht Petzoldt, and Dieter S. Schmidt. "Solving polynomial systems." Multivariate Public Key Cryptosystems. Ed. Jintai Ding, Albrecht Petzoldt, Dieter S. Schmidt, New York: Springer, 2020. 185-248.
BibTeX: Download