Welcome to the resource topic for 2025/793
Title:
Solving systems of polynomial equations via Macaulay matrices
Authors: Shuhei Nakamura
Abstract:One approach to solving polynomial systems is to multiply each equation by monomials, which creates a larger system with the coefficient matrix known as the Macaulay matrix.
The eXtended Linearization (XL) method, introduced by Courtois, Klimov, Patarin, and Shamir in 2000, is one such approach and includes a sub-algorithm that performs Gaussian elimination on the Macaulay matrix.
Due to the simplicity of the method, several improvements and variations have been proposed since its introduction, and it remains an active area of research.
In this paper, we focus on sub-algorithms based on Macaulay matrices that are used in the XL method and its variants and investigate the input parameters that produce the desired output, such as a Gr"{o}bner basis.
In particular, by summarizing some known facts about the standard degree, we provide a foundation for extending the XL method to the multi-degree case.
ePrint: https://eprint.iacr.org/2025/793
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .