Efficient Checking of Separating Indeterminates

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₁, ,xₙ] K [ x 1 , ⋯ , x n ] over a field K , this method searches for tuples Z=(z₁, ,zₛ) Z = ( z 1 , ⋯ , z s ) of indeterminates with the property that I contains polynomials of the form fᵢ = zᵢ - hᵢ f i = z i - h i for i=1, ,s i = 1 , ⋯ , s such that no term in hᵢ 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ᵢ f i . We also extend these algorithms to Boolean polynomials and apply them to cryptoanalyze round reduced versions of the AES cryptosystem more efficiently.