Mathematics in Computer Science Прикладные компьютерные науки

Efficient Checking of Separating Indeterminates

Bernhard Andraschko, Martin Kreuzer, Le Ngoc Long
Springer Nature · 2025-08-14 · DOI 10.1007/s11786-025-00616-2

Аннотация

Abstract 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]$$ K [ x 1 , ⋯ , x n ] over a field K , this method searches for tuples $$Z=(z_1,\dots ,z_s)$$ Z = ( z 1 , ⋯ , z s ) of indeterminates with the property that I contains polynomials of the form $$f_i = z_i - h_i$$ f i = z i - h i for $$i=1,\dots ,s$$ i = 1 , ⋯ , s such that no term in $$h_i$$ h i is divisible by any 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 contains the desired polynomials $$f_i$$ f i . We also extend these algorithms to Boolean polynomials and apply them to cryptoanalyze round reduced versions of the AES cryptosystem more efficiently.

Читать у издателя →