Polynomial XL: A Variant of the XL Algorithm Using Macaulay Matrices over Polynomial Rings

arXiv:2112.05023v2 Announce Type: replace-cross
Abstract: Solving a system of $m$ multivariate quadratic equations in $n$ variables over finite fields (the MQ problem) is one of the important problems in the theory of computer science. The XL algorithm (XL for short) is a major approach for solving the MQ problem with linearization over a coefficient field. Furthermore, the hybrid approach with XL (h-XL) is a variant of XL guessing some variables beforehand. In this paper, we present a variant of h-XL, …

algorithm arxiv computer computer science cs.cr cs.sc important major problem problems rings science system theory