# Solutions of affine polynomials in characteristic $2$

I will give an example for expressing where I stuck about affine polynomials:

Let $$\alpha \in \mathbb F_{2^k}^*$$. Let $$L_{\alpha}(x)=x^4+x^2+\alpha x$$ be a linearized polynomial over $$\mathbb F_{2^n}$$ with $$k \mid n$$. What is $$\{x \in \mathbb F_{2^n} \: | \: L_\alpha(x)\in \mathbb F_{2^{m}}\}$$ where $$m \geq1$$ and $$k \mid m$$?

Process:

Firstly Since $$L_\alpha : \mathbb F_{2^n} \to \mathbb F_{2^n}$$, we have $$\{x \in \mathbb F_{2^n} \: | \: L_\alpha(x)\in \mathbb F_{2^{m}}\}=\{x \in \mathbb F_{2^n} \: | \: L_\alpha(x)\in \mathbb F_{2^{(m,n)}}\}$$. Therefore assume $$m \mid n$$.

There are $$3$$ possibilities for factorization of $$L_{\alpha}$$ in $$\mathbb F_{2^k}$$. (see factorization of $$x^3+x+b$$)

Now if $$x^3+x+\alpha$$ is irreducible over $$\mathbb F_{2^k}$$ we can write $$x^3+x+\alpha=(x-w)(x-w^{2^k})(x-w^{2^{2k}})$$ where $$w \in \mathbb F_{2^{3k}}$$. Since $$0,w,w^{2^k},w^{2^{2k}}$$ is root of $$L_\alpha$$, if $$3k \not \mid n$$, then $$\{x \in \mathbb F_{2^n} \: | \: L_\alpha(x)\in \mathbb F_{2^{m}}\}=\mathbb F_{2^m}$$ $$\{x \in \mathbb F_{2^n} \: | \: L_\alpha(x)\in \mathbb F_{2^{m}}\}=\{0+\mathbb F_{2^m},w+\mathbb F_{2^m},w^{2^k}+\mathbb F_{2^m},w^{2^{2k}}+\mathbb F_{2^m} \}$$ (abuse of set).

I just confused for the other cases: (maybe above case is wrong too?)

if $$x^3+x+\alpha$$ has one root in $$\mathbb F_{2^k}$$, $$\cdots$$

if $$x^3+x+\alpha$$ has three roots in $$\mathbb F_{2^k}$$, $$\cdots$$

see Morgan's answer: Since $$x^{2^{m+2}} + x^{2^{m+1}} + \alpha x^{2^{m}} + x^{4}+x^{2}+\alpha x$$ is linearized polynomial, the solution space is vector space over $$\mathbb F_2$$ and includes the $$\mathbb F_{2^m}$$. Since degree of the polynomial Morgan wrote is $$2^{m+2}$$. There are $$3$$ possibilities for dimension: $$m,m+1$$, or $$m+2$$. Moreover $$L_{\alpha}$$ has $$1=2^0,2=2^1$$, or $$4=2^2$$ solution(s). I think that this space need to be related with $$x^4+x^2+\alpha x$$ in easy way.

Furthermore, (symbolically) $$x^{2^{m+2}} + x^{2^{m+1}} + \alpha x^{2^{m}} + x^{4}+x^{2}+\alpha x =(x^{2^m}-x)\otimes L_{\alpha}(x)=L_\alpha(x)\otimes(x^{2^m}-x)$$.

I want to note that symbolically division works. I probably made a mistake in computation part.

An alternate approach: $L_{\alpha}(x) \in \mathbb{F}_{2^{m}}$ if and only if $(L_{\alpha}(x))^{2^{m}} = L_{\alpha}(x)$. Plugging this in we have $$x^{2^{m+2}} + x^{2^{m+1}} + \alpha x^{2^{m}} + x^{4}+x^{2}+\alpha x = 0.$$

From this it is clear that every element of $\mathbb{F}_{2^{m}}$ satisfies this equation. Furthermore, if $\omega$ is a root of $x^{4}+x^{2}+\alpha x$, then $\omega$ also satisfies this equation, as does $\omega + b$ for all $b \in \mathbb{F}_{2^{m}}$. So the dimension of $\{x \in \mathbb{F}_{2^{n}} \mid L_{\alpha}(x) \in \mathbb{F}_{2^{m}}\}$ depends on how many zeroes $x^{3}+x+\alpha$ has that are not in $\mathbb{F}_{2^{m}}$. (I'm not sure where $k$ comes into play.)

• Thanks. I actually transformed this one to the form in question. I couldn't find an easy way for finding all solution in this form. Oct 12, 2015 at 16:41
• Since it is linearized polynomial, the solution space is vector space over $\mathbb F_2$ and includes the $\mathbb F_{2^m}$. Since degree of the polynomial you wrote is $2^m+2$. There are $3$ possibilities for dimension: $2^m,2^m+1$, or $2^m+2$. Moreover $L_{\alpha}$ has $1,2$, or $4$. (i will also add this to question). Oct 12, 2015 at 17:01
• I actually think same but magma says: if $n=12,m=6$ and $\alpha=1$ then #=$2^8$. On the other hand, roots of $x^3+x+1$ in $\mathbb F_{2^{12}}$. (But it needed be $2^6$?) Am I doing wrong? (It is same for $n=24$, actually.) Oct 13, 2015 at 8:20
• I think dimension need to be the degree of $gcd(x^{m+2}+x^{m+1}+x^{m}+x^2+x+1,x^n+1)$. Oct 13, 2015 at 9:11
• I don't know offhand if it is equivalent, but the number of solutions is definitely equal to the degree of $gcd(x^{2^{m+2}}+x^{2^{m+1}}+\alpha x^{2^m} + x^{4}+x^{2}+\alpha x, x^{2^{n}}+x)$. Oct 13, 2015 at 10:39

For $K$ a finite field containing $\alpha$, let $\phi_K(x) = x^{|K|}$ and $\psi_K(x) = \phi_K(x)+x$.
$L_\alpha, \phi_K, \psi_K$ are all $\Bbb F_2$-linear maps on $\overline K$.

Let $G_\alpha = \{0,u,v,u+v\}$ be the group of solutions (in $\overline{K}$) to $x^4+x^2+\alpha x = 0$, so that $L_\alpha(x) = x(x+u)(x+v)(x+u+v)$.

For any $x \in \overline K$, the roots of $L_\alpha(X) + L_\alpha(x)$ are $\{x+g \mid g \in G_\alpha \}$, and

$\psi_K(x) \in G_\alpha \iff \phi_K(x) = x+g, g \in G_\alpha \iff L_\alpha(\phi_K(x)) = L_\alpha(x) \iff \phi_K(L_\alpha(x)) = L_\alpha(x) \iff L_\alpha(x) \in K$

If $L_\alpha(x) =L_\alpha(y)$ then $y=x+g$, and so $\psi_K(y) = \psi_K(x)+\psi_K(g)$.
For $y \in K$, $L_\alpha(X)+y$ has a root $x$ in $K$ if and only if there is an $x$ such that $L_\alpha(x) =y$ and $\psi_K(x) = 0$.

Hence we get an isomorphism $\chi_{\alpha,K} : K/L_\alpha(K) \to G_\alpha/\psi_K(G_\alpha)$, defined by $\chi_{\alpha,K}(L_\alpha(x)) = \psi_K(x)$, that takes an element $y \in K$ and tells us how $\phi_K$ acts on the root of $L_\alpha(X)+y$.

(note that $|G_\alpha / \psi_K(G_\alpha) | = | \ker \psi_K|_{G_\alpha} | = |G_\alpha \cap K|$, so those two are isomorphic, but not canonically as far as I know)

(also this screams cohomology : if $\mathcal G = Gal(\overline K / K)$,
we have a short exact sequence of $\mathcal G$-modules $0 \to G_\alpha \to \overline K \xrightarrow{L_\alpha} \overline K \to 0$. This gives a long exact sequence $0 \to G_\alpha \cap K \to K \xrightarrow{L_\alpha} K \xrightarrow{\chi_{\alpha,K}} H^1(G_\alpha) \to H^1(\overline K)=0$ hence the isomorphism )

If $G_\alpha \subset K$ then $\psi_K(G_\alpha)$ is trivial, $L_\alpha(K)$ is a subspace of $K$ of codimension $2$ and we have an isomorphism $K/L_\alpha(K) \to G_\alpha$. The polynomials $L_\alpha(X) + y$ completely split $1/4$ of the time, and have two quadratic factors $3/4$ of the time. $\chi_{\alpha,K}$ even tells us how to combine the roots to make the factors.

If $G_\alpha \cap K = \{0,u\}$ then $\psi_K(G_\alpha) = \{0,u\}$. $L_\alpha(K)$ is a subspace of codimension $1$. If $y \in L_\alpha(K)$ then $L_\alpha(X)+y$ has two roots $x,x+u \in K$ and a pair of roots $(x+v,x+u+v)$ in the quadratic extension of $K$. If not then it is irreducible, and $\phi_K$ acts like $(x \mapsto x+v \mapsto x+u \mapsto x+v+u \mapsto x)$

If $G_\alpha \cap K = \{0\}$ then $\phi_K$ permutes the nonzero elements of $G$ cyclically, $\psi_K(G_\alpha) = G_\alpha$, and $K = L_\alpha(K)$ so $L_\alpha(X)+y$ has one linear factor and one cubic factor, forall $y \in K$.