Paper 2025/793
Solving systems of polynomial equations via Macaulay matrices
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
-
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}
}
