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


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

How to cite


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.


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