Obtaining some elements of Galois field $2^q$

Question

Consider an $n$-tuple $(\alpha_1,\alpha_2,\cdots, \alpha_n)$ where $\alpha_i$, $1\leq i \leq n$, are elements of the Galois field $GF(2^q)$. We know that the elementary symmetric polynomial $e_j$, $1\leq j \leq k$, over the $n$-tuple $(\alpha_1,\alpha_2,\cdots, \alpha_n)$ are defined as follows

\begin{eqnarray} e_1(\alpha_1,\alpha_2,\cdots, \alpha_n)&=&\sum_{1\leq j \leq n} \, \alpha_j\quad ,\\ \\ e_2(\alpha_1,\alpha_2,\cdots, \alpha_n)&=&\sum_{1\leq j<k \leq n} \, \alpha_j\, \alpha_k \quad ,\\ \\ e_k(\alpha_1,\alpha_2,\cdots, \alpha_n)&=&\sum_{1\leq j_1<j_2<\cdots <j_k \leq n} \, \alpha_{j_1}\cdots \alpha_{j_k} \quad . \end{eqnarray}

In my research, I need an example of eight-tuple $(\alpha_1,\alpha_2,\cdots, \alpha_8)$ where $\alpha_i$, $1\leq i \leq 8$, be elements of the Galois field $GF(2^8)$ such that $$ e_i(\alpha_1,\alpha_2,\cdots, \alpha_8)=0 \quad , \quad 1\leq i \leq 4 \quad . $$

I want to ask you to help me to obtain this example. If you find this example, please clarify with which primitive polynomial you have constructed the Galious field $GF(2^8)$.

I wrote a Maple code for obtaining this example, but because of there are $256 \choose 8$ cases for choosing $\alpha_i$'s and limitation of my computer CPU and RAM, I could not find an example. The JPG format of my Maple code is in the following form.

I would greatly appreciate for any assistance.

Edit:

Based on the efficient and excellent answers of Professor Robert Israel and Jyrki Lahtonen, I want to add an addition condition as follows

$$ e_i(\alpha_1,\alpha_2,\cdots, \alpha_8)=0 \quad , \quad 1\leq i \leq 4 \quad, \quad e_j(\alpha_1,\alpha_2,\cdots, \alpha_8)\neq0 \quad , \quad 5\leq j \leq 7\, .$$

Answer 1

With $GF(2^8)$ generated by a root $\beta$ of the polynomial $x^8+x^6+x^5+x^2+1$ over $GF(2)$, take $$\eqalign{0,\; {\beta}^{3}+\beta,\;{\beta}^{7}+{\beta}^{5}+{\beta}^{2},\;{\beta}^{6}+{ \beta}^{5}+\beta+1,\;{\beta}^{6}+{\beta}^{5}+{\beta}^{3}+1,\;\cr{\beta}^{7}+{ \beta}^{5}+{\beta}^{3}+{\beta}^{2}+\beta,\;{\beta}^{7}+{\beta}^{6}+{ \beta}^{2}+\beta+1,\;{\beta}^{7}+{\beta}^{6}+{\beta}^{3}+{\beta}^{2}+1 }$$

Maple code:

P:= x^8+x^6+x^5+x^2+1:
alias(beta = RootOf(P)):
randc:= proc() add(rand(0..1)()*beta^j,j=0..7) end proc:
for iter from 1 do
  Q:= x^8 + add(randc()*x^j,j=1..3);
  F:= (Factors(Q,beta) mod 2)[2];
  if nops(F) = 8 then
     print(map(t -> subs(x=0,t[1]), F));
     break
  fi
od:

Answer 2

Nothing wrong Robert Israel's answer. I simply cannot resist describing a bit of theory leading to some (but not all) solutions.

---

TL;DR; version: If $\beta$ is a primitive element of $GF(256)$, then $$ x^8+\beta^{85}x^2+x $$ has eight distinct zeros in $GF(256)$, and for them we have $e_1=e_2=e_3=e_4=e_5=0.$ On with the longer version...

---

Assume that $V\subset GF(2^q)$ is a 3-dimensional subspace (over $GF(2)$). Consider the octic polynomial that has zeros at the points of $V$: $$ L_V(x)=\prod_{z\in V}(x-z). $$ I will show that $L_v$ has only terms of degrees $1,2,4$ and $8$.

Let $v\in GF(2^q)$. The polynomial $$p_v(x)=x^2-vx$$ obviously vanishes at $0$ and $v$. Furthermore, $p_v(x)$ is a so called linearized polynomial, meaning that $$ p_v(x+y)=p_v(x)+p_v(y). $$ Let $v_1,v_2,v_3$ be a basis of $V$. Because $p_{v_1}(x)$ is linearized, we see that $$p_{v_1}(v_2)=p_{v_1}(v_2)+p_{v_1}(v_1)=p_{v_1}(v_1+v_2).$$ Therefore the composition $$ p_{v_1,v_2}(x):=p_{p_{v_1}(v_2)}(p_{v_1}(x)) $$ vanishes at the points $0,v_1,v_2,v_1+v_2$. Furthermore, by the composition rule (and Freshman's dream in characteristic two) we see that $p_{v_1,v_2}(x)$ only has terms of degrees $1,2$ and $4$, and hence it, too, is a linearized polynomial.

Repeating the dose then shows that $$ p_{v_1,v_2,v_3}(x):=p_{p_{v_1,v_2}(v_3)}(p_{v_1,v_2}(x)) $$ vanishes at the points of $V$, only has terms of degrees $1,2,4$ and $8$, and hence is also linearized. Because this octic is also monic, it must be equal to $L_V(x)$.

Anyway, $$ L_V(x)=x^8+e_4(V)x^4+e_6(V)x^2+e_7(V)x, $$ where the $e_i$:s are the elementary symmetric polynomials of the set $V$. In particular, we automatically have $e_1(V)=e_2(V)=e_3(V)=0$ hopefully explaining why I wanted to explain this to you.

So selecting your elements $\alpha_i, i=1,2,\ldots,8,$ to be the elements of a subspace $V$ gives us $e_1=e_2=e_3=0$ automatically leaving us to deal with $e_4$. We are lead to look for subspaces $V$ such that $$ L_V(x)=x^8+ Ax^2+Bx, $$ when we will in addition to the above get $e_4=e_5=0$. To make the search simpler let us consider the effect of scaling. If we multiply the subspace $V$ by an element $\alpha\in GF(2^q)$, we get the subspace $$ \alpha V=\{\alpha z\mid z\in V\}. $$ Clearly $e_6(\alpha V)=\alpha^6 e_6(V)$ and $e_7(\alpha V)=\alpha^7e_7(V)$. As raising to seventh power is a bijection of $GF(2^8)$ we can, by selecting a suitable $\alpha$, without loss of generality assume that $e_7(V)=1$. We are thus left with polynomials of the form $$ L_a(x)=x^8+ax^2+x. $$ We need to select $a$ in such a way that $L_a(x)$ has eight zeros in $GF(2^8)$. Because all the elements of $GF(256)$ are zeros of $P(x)=x^{256}-x$, we want to check that $L_a(x)$ is a factor of $P(x)$. Using square-and-multiply (and Freshman's dream!!!) it is actually a pencil-and-paper calculation to find the remainder! It turns out that $$ P(x)\equiv(1+a^{42})x^4+(a^5+a^{33}+a^{40})x^2+(1+a^4+a^{32})x\pmod{L_a(x)}. $$ So $L_a(x)$ will give us what we want if all those three polynomials on $a$ vanish. It follows from Bill Dubuque's answer to another question that if $a$ is a primitive third root of unity, i.e. it satisfies the equation $a^2+a+1$, then we, indeed, get $$ L_a(x)\mid P(x). $$

Observe that already the field $GF(4)\subset GF(256)$ contains the primitive third roots of unity. If $\beta$ is a primitive element of the field $GF(256)$, then $\beta^{85}$ can serve in the role of $a$ in $L_a(x)$.

Furthermore, by linearity of $L_a(x)$, the cosets of the subspace $V:=\operatorname{Ker}(L_a)$ are zeros of polynomials of the form $L_a(x)+c$ for some $c\in GF(256)$. There are $32$ such cosets, so you get $8$ zeros in $GF(256)$ for $32$ different choices of $c$. Any of those $32$ cosets will serve as your set $\alpha_i, i=1,2,\ldots,8$.