1
$\begingroup$

I am trying to construct a polynomial $f \in \mathbb{F}_{2^k}$ of odd degree, such that $\forall x \in \mathbb{F}_{2^k} \exists \alpha \in \mathbb{F}_{2^k}$ such that $f(x)=\alpha ^2 -\alpha$.

Working with some normal basis $\{ \alpha ^{2^i} | 0 \le i \le k-1 \}$, the image of $x \to x^2 -x$ is $\{ \sum c_i \alpha ^{2^i} | \sum c_i = 0, c_i \in \mathbb{F}_{2} \}$. In other words, we require $f(\mathbb{F}_{2^k}) \subseteq Im(t^2-t)$, and this image is a subspace of dimension $k-1$ of the field.

It is easy to construct such $f$ of even degree: $f(x)=x^{2^{i+1}} - x^{2^i}$, for any $i$.

EDIT: I managed to find an example, but I don't like it much: taking $f(x) = x^{2^k + 1} - x$. For every $x \in \mathbb{F}_{2^k}$, $f(x)=x^2-x$.

  • 0
    francis-jamet points out an error in my reading of the question: $\alpha$ may depend on $x$.2012-07-07

1 Answers 1

1

Another way to state your condition is that, for every $\beta \in \mathbf{F}_{2^k}$, $f(\beta)$ has trace 0 over $\mathbf{F}_2$.

For $k=5$, an example is $f(x) = x^9 - x^5$. To see that this has trace 0 for any $\beta \in \mathbf{F}_{32}$:

$ \begin{align*} \mathop{Tr}(\beta^9 - \beta^5) &= \mathop{Tr}(\beta^9) - \mathop{Tr}(\beta^5) \\&= (\beta^9 + \beta^{18} + \beta^{36} + \beta^{72} + \beta^{144}) - (\beta^5 + \beta^{10} + \beta^{20} + \beta^{40} + \beta^{80}) \\&= (\beta^9 + \beta^{18} + \beta^{5} + \beta^{10} + \beta^{20}) - (\beta^5 + \beta^{10} + \beta^{20} + \beta^{9} + \beta^{18}) \\&= 0 \end{align*} $

In general, the condition means that

$ f(\beta) + f(\beta)^2 + \cdots + f(\beta)^{2^{k-1}} = 0 $

for every $\beta \in \mathbf{F}_{2^k}$, or equivalently,

$ f(x) + f^\sigma(x^2) + f^{\sigma^2}(x^4) + \cdots + f^{\sigma^{k-1}}(x^{2^{k-1}}) \equiv 0 \pmod{ x^{2^k} - x} $

where $f^\sigma$ is the polynomial formed by conjugating each coefficient of $f$ by the action $u \mapsto u^2$.

We can split the powers of $x$ into orbits under the action $x \mapsto x^2 \pmod{x^{2^k} - x}$ -- i.e. writing

$ f(x) = u + h(x) (x^{2^k} - x) + \sum_m g_m(x^m) $

where $u$ is a constant with trace 0, and each $g$ has the form

$g(x) = \sum_{j=0}^{k-1} c_j x^{2^j}.$

Each $g(x)$ must satisfy the constraint, and any choice of valid $g's$ gives a valid $f$. So,

$0 \equiv \sum_{i=0}^{k-1} g^{\sigma^i}(x^{2^i}) \equiv \sum_{i=0}^{k-1} \sum_{j=0}^{k-1} c_j^{2^i} x^{2^{i+j}} = \sum_{j=0}^{k-1} x^{2^{j}} \sum_{i=0}^{k-1} c_{j-i}^{2^{i}} \pmod{x^{2^k} - x} $

(there was a change of variable $j \mapsto j-i$) where the index on $c$ is taken modulo $k$. Each coefficient gives the same condition:

$\sum_{i=0}^{k-1} c_{k-1-i}^{2^i} = 0$

Now, how can we use this to find a polynomial of small, odd degree? Consider $k=5$. One of the orbits of powers of x is:

$ x^5, x^{10}, x^{20}, x^{40} \equiv x^9, x^{80} \equiv x^{18} $

By setting the coefficients on $x^9$ and a smaller term to $1$ and the rest to $0$ will satisfy the equation. This is the example at the top of my answer.

  • 0
    +1: Yes, this is a standard use of the trace function in finite fields of characteristic two. Well done!2012-07-07