Efficiently Checking Separating Indeterminates
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915078281887744 |
|---|---|
| author | Andraschko, Bernhard Kreuzer, Martin Long, Le Ngoc |
| author_facet | Andraschko, Bernhard Kreuzer, Martin Long, Le Ngoc |
| contents | In this paper we continue the development of a new technique for computing elimination ideals by substitution which has been called $Z$-separating re-embeddings. Given an ideal $I$ in the polynomial ring $K[x_1,\dots,x_n]$ over a field $K$, this method searches for tuples $Z=(z_1,\dots,z_s)$ of indeterminates with the property that $I$ contains polynomials of the form $f_i = z_i - h_i$ for $i=1,\dots,s$ such that no term in $h_i$ is divisible by an indeterminate in $Z$. As there are frequently many candidate tuples $Z$, the task addressed by this paper is to efficiently check whether a given tuple $Z$ has this property. We construct fast algorithms which check whether the vector space spanned by the generators of $I$ or a somewhat enlarged vector space contain the desired polynomials $f_i$. We also extend these algorithms to Boolean polynomials and apply them to cryptoanalyse round reduced versions of the AES cryptosystem faster. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_18369 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficiently Checking Separating Indeterminates Andraschko, Bernhard Kreuzer, Martin Long, Le Ngoc Commutative Algebra Algebraic Geometry 14Q20 (Primary) 14R10, 13E15, 13P10 (Secondary) In this paper we continue the development of a new technique for computing elimination ideals by substitution which has been called $Z$-separating re-embeddings. Given an ideal $I$ in the polynomial ring $K[x_1,\dots,x_n]$ over a field $K$, this method searches for tuples $Z=(z_1,\dots,z_s)$ of indeterminates with the property that $I$ contains polynomials of the form $f_i = z_i - h_i$ for $i=1,\dots,s$ such that no term in $h_i$ is divisible by an indeterminate in $Z$. As there are frequently many candidate tuples $Z$, the task addressed by this paper is to efficiently check whether a given tuple $Z$ has this property. We construct fast algorithms which check whether the vector space spanned by the generators of $I$ or a somewhat enlarged vector space contain the desired polynomials $f_i$. We also extend these algorithms to Boolean polynomials and apply them to cryptoanalyse round reduced versions of the AES cryptosystem faster. |
| title | Efficiently Checking Separating Indeterminates |
| topic | Commutative Algebra Algebraic Geometry 14Q20 (Primary) 14R10, 13E15, 13P10 (Secondary) |
| url | https://arxiv.org/abs/2412.18369 |