Paper 2025/793 Original: eprint.iacr.org/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 appear in the XL method and its variants and investigate input parameters that yield desired outputs such as Gr\"{o}bner bases. In particular, by revisiting the standard degree setting and formulating a framework without fixing a specific monomial order, we provide a foundation for extending the analysis to the multi-degree case.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2026-03-06: last updated
- 2025-05-04: published
- Short URL
- https://ia.cr/2025/793
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}