Making factor_equal_deg_prob to work for q=2

In my previous posts I described the variant of equal-degree splitting for odd prime powers. This algorithm requires some modification for fields with characteristic 2.

For $m\in \mathbb{N}$ define the $m$th trace polynomial over $F_2$ by $T_m=x^{2^{m-1}}+x^{2^{m-2}}+...+x^2+x.$  Let $q = 2^k$ for some $k\in \mathbb{N}$, $f\in F_q[x]$ squarefree of degree $n$, with $r\geq 2$ irreducible factors $f_1,...,f_r\in F_q[x], R=F_q[x]/<f>$

This modification exploits two facts:

Fact 1. $x^{2^m}+x = T_m(T_m+1) \Rightarrow T_m(\alpha)\in F_2 \,\,\forall \alpha\in F_{2^m}$
Fact 2. Let all irreducible factors of $f$ have degree $d$. Then $T_{kd}(\alpha) \mod f_i\in F_2 \,\,\forall i \,\,\forall \alpha\in R$

Now one can modify a probabilistic algorithm of equal-degree splitting: instead of computing $b=a^{(q^d-1)/2}\mathrm{rem} f$ one have to compute $b = T_{kd}(a)\mathrm{rem} f$.

_____________________

Proof of Fact 1.

1) First note that $(x_1+...+x_k)^{2^n} = x_1^{2^n}+...+x_k^{2^n} \,\, \forall x_i\in F_{2^m}$. It can be proved by induction on $n$. For $n=0$ and $n=1$ it is obvious. Assuming that this is true for $n-1$ one can get: $(x_1+...+x_k)^{2^n}=\left((x_1+...+x_k)^{2^{n-1}}\right)^2 = (x_1^{2^{n-1}}+...+x_k^{2^{n-1}})^2=x_1^{2^n}+...+x_k^{2^n}$

2) Then note that $a^q = a \,\, \forall a\in F_q$

3) Finally,    $T_m(\alpha)(T_m(\alpha)+1)=(T_m(\alpha))^2+T_m(\alpha) = $
                    $(\alpha^{2^{m-1}}+\alpha^{2^{m-1}}...+\alpha)^2+\alpha^{2^{m-1}}+...+\alpha^2+\alpha=$
                    $\alpha^{2^m}+\alpha^{2^{m-1}}...+\alpha^2+\alpha^{2^{m-1}}+...+\alpha^2+\alpha=$
                    $\alpha^{2^m}+\alpha=\alpha+\alpha=0 \,\, \forall \alpha\in F_{2^m}$
It means that $T_m(\alpha) = 0$ or $T_m(\alpha) = 1$, i.e. $T_m(\alpha)\in F_2\,\,\forall \alpha\in F_{2^m}$