Attacking the Polynomials in the Maze of Finite Fields problem
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908868224745472 |
|---|---|
| author | Barbero, Àngela Freij-Hollanti, Ragnar Hollanti, Camilla Raddum, Håvard Ytrehus, Øyvind Øygarden, Morten |
| author_facet | Barbero, Àngela Freij-Hollanti, Ragnar Hollanti, Camilla Raddum, Håvard Ytrehus, Øyvind Øygarden, Morten |
| contents | In April 2025 GMV announced a competition for finding the best method to solve a particular polynomial system over a finite field. In this paper we provide a method for solving the given equation system significantly faster than what is possible by brute-force or standard Gröbner basis approaches. The method exploits the structured sparsity of the polynomial system to compute a univariate polynomial in the associated ideal through successive computations of resultants. A solution to the system can then be efficiently recovered from this univariate polynomial. Pseudocode is given for the proposed ResultantSolver algorithm, along with experiments and comparisons to rival methods. We also discuss further potential improvements, such as parallelizing parts of the computations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_05054 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Attacking the Polynomials in the Maze of Finite Fields problem Barbero, Àngela Freij-Hollanti, Ragnar Hollanti, Camilla Raddum, Håvard Ytrehus, Øyvind Øygarden, Morten Computational Complexity In April 2025 GMV announced a competition for finding the best method to solve a particular polynomial system over a finite field. In this paper we provide a method for solving the given equation system significantly faster than what is possible by brute-force or standard Gröbner basis approaches. The method exploits the structured sparsity of the polynomial system to compute a univariate polynomial in the associated ideal through successive computations of resultants. A solution to the system can then be efficiently recovered from this univariate polynomial. Pseudocode is given for the proposed ResultantSolver algorithm, along with experiments and comparisons to rival methods. We also discuss further potential improvements, such as parallelizing parts of the computations. |
| title | Attacking the Polynomials in the Maze of Finite Fields problem |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2603.05054 |