Paper 2025/793

Solving systems of polynomial equations via Macaulay matrices

Shuhei Nakamura, Ibaraki University
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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
solving polynomial systemsMacaulay matrixGroebner basisXL algorithmmulti-degree
Contact author(s)
shuhei nakamura research @ gmail com
History
2025-05-05: approved
2025-05-04: received
See all versions
Short URL
https://ia.cr/2025/793
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/793,
      author = {Shuhei Nakamura},
      title = {Solving systems of polynomial equations via Macaulay matrices},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/793},
      year = {2025},
      url = {https://eprint.iacr.org/2025/793}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.