A Variant of the XL Algorithm Using the Arithmetic over Polynomial Matrices (Computer Algebra : Foundations and Applications)

Abstract

Solving a system of multivariate polynomials is a classical but very important problem in many areas of mathematics and its applications, and in particular quadratic systems over finite fields play a major role in the multivariate public key cryptography. The XL algorithm is known to be one of the main approaches for solving a multivariate system, as well as Groebner basis approaches, and so far many variants of XL have been proposed. In this talk, we present a new variant of XL, which we name “Polynomial XL”, by using Macaulay matrices over polynomial rings.