an algebraic extension which can both be computed in polynomial time. The delicate task being to control the size of the algebraic extensions occurring during the algorithm. In here, each coefficient of the two matrices are lying in an extension field of polynomial degree in $n$. Furthermore, these matrices allow us to test in polynomial time if $H_1,\ldots,H_m$ and $H_1',\ldots,H_m'$ are indeed equivalent. We then present a second simpler method based on the *generalized Jordan normal form* (see Section \[ss:sqrt\_char\_p\]) which works (in polynomial time) over finite fields. In general, it deals with algebraic extensions of smaller degree than the first one. Putting things together, we obtain our main result:

\[th:probmain\] Let ${{\mathbb}{K}}$ be a field with $\operatorname{char}{{\mathbb}{K}}\neq
  2$. Under Assumption \[as:regular\], there exists a randomized polynomial-time algorithm for solving quadratic-[`IP1S`]{}over an extension field of ${{\mathbb}{K}}$ of polynomial degree in $n$.

Let us note that the authentication scheme using [`IP1S`]{}requires to find a solution over the base field. However, it is not always necessary to find a solution in the base field (typically, in the context of a key-recovery for multivariate schemes). In [@BettaleFP2013], the authors recover an equivalent key over an extension for the multi-HFE scheme.

In addition, under 