Polynomial selection for computing Gröbner bases
Takuma Ito, Atsushi Nitta, Yuta Hoshi, Naoyuki Shinohara, Shigenori Uchiyama · JSIAM Letters · 2021
In the security evaluation of multivariate public key cryptosystems (MPKCs), constructing algorithms to solve the problem of finding solutions of a system of multivariate quadratic polynomial equations (MQ problem) is an important topic of research. Algorithms for computing a Gröbner basis are often used as a method to solve MQ problems. In this article, we focus on solving MQ problems using Buchberger's algorithm which is a basic algorithm for computing a Gröbner basis. We propose a new method for selecting polynomials to efficiently compute a Gröbner basis for a set of polynomials, which is used for MPKCs.