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$?


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.


2 Answers 2


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.)

  • $\begingroup$ 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. $\endgroup$
    – vudu vucu
    Oct 12, 2015 at 16:41
  • 1
    $\begingroup$ 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). $\endgroup$
    – vudu vucu
    Oct 12, 2015 at 17:01
  • $\begingroup$ 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.) $\endgroup$
    – vudu vucu
    Oct 13, 2015 at 8:20
  • $\begingroup$ 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)$. $\endgroup$
    – vudu vucu
    Oct 13, 2015 at 9:11
  • $\begingroup$ 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)$. $\endgroup$
    – xxxxxxxxx
    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$.

This should be enough to answer your questions.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .