Efficient Checking of Separating Indeterminates

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]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo>[</mml:mo> <mml:msub> <mml:mi>x</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>x</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> over a field K , this method searches for tuples $$Z=(z_1,\dots ,z_s)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Z</mml:mi> <mml:mo>=</mml:mo> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>z</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>z</mml:mi> <mml:mi>s</mml:mi> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> of indeterminates with the property that I contains polynomials of the form $$f_i = z_i - h_i$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>f</mml:mi> <mml:mi>i</mml:mi> </mml:msub> <mml:mo>=</mml:mo> <mml:msub> <mml:mi>z</mml:mi> <mml:mi>i</mml:mi> </mml:msub> <mml:mo>-</mml:mo> <mml:msub> <mml:mi>h</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> </mml:math> for $$i=1,\dots ,s$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>i</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>,</mml:mo> <mml:mi>s</mml:mi> </mml:mrow> </mml:math> such that no term in $$h_i$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>h</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:math> 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>f</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:math> . We also extend these algorithms to Boolean polynomials and apply them to cryptoanalyze round reduced versions of the AES cryptosystem more efficiently.