On the last fall degree of Weil descent polynomial systems

Abstract

Given a polynomial system $\mathcal{F}$ over a finite field $k$ which is not necessarily of dimension zero, we consider the Weil descent ${\mathcal{F}}^{\prime }$ of $\mathcal{F}$ over a subfield $k^{\prime }$. We prove a theorem which relates the last fall degrees of ${\mathcal{F}}_1$ and ${\mathcal{F}}_1^{\prime }$, where the zero set of ${\mathcal{F}}_1$ corresponds bijectively to the set of $k$-rational points of $\mathcal{F}$, and the zero set of ${\mathcal{F}}_1^{\prime }$ is the set of $k^{\prime }$-rational points of the Weil descent ${\mathcal{F}}^{\prime }$. As an application we derive upper bounds on the last fall degree of ${\mathcal{F}}_1^{\prime }$ in the case where $\mathcal{F}$ is a set of linearized polynomials.