+ 1$ is a solution, since $\deg \lambda_1 < 5$ and $$\lambda_1 {\bm{S}} \equiv
      \left(x^{2} + 1,\ 1,\ x^{3} + 1\right)
      \mod x^5 \ .$$ $\lambda_2 = x^{3} + x$ is another solution, since $$\lambda_2 {\bm{S}} \equiv
      \left(x,\ x^{3} + x,\ x^4+x^3 + x\right)
      \mod x^5 \ .$$ These two solutions are linearly independent over ${\mathbb F_{2}\xspace}[x]$ and span all solutions.

Several previous algorithms for solving \[prob:sim\_pade\] are more ambitious and produce an entire *basis* of solutions that satisfy the first output condition $\lambda S_i \equiv \phi_i \mod g_i$ for $i=1,\ldots,n$, including solutions that do not satisfy the degree bounds stipulated by the second output condition. Our algorithms are slightly more restricted in that we only return the sub-basis that generates the set of solutions that satisfy both output requirements of \[prob:sim\_pade\]. Formally:

\[prob:sim\_pade\_basis\] Given an instance of \[prob:sim\_pade\], find a matrix $A \in {{\mathsf{K}}}[x]^{* \times (n+1)}$ such that:

-   Each row of $A$ is a solution to the instance.

-   All solutions are in the ${{\mathsf{K}}}[x]$-row space of $A$.

-   $A$ is $(-{\bm{N}})$-row reduced[^2].

The last condition ensures that $A$ is minimal, in a sense, according to the degree bounds ${\bm{N}}$, and that we can easily parametrise which linear 