# Obtaining some elements of Galois field $2^q$

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\, .$$

• I suppose you don't want the obvious example: all $\alpha_j = 0$, or the slightly less obvious: all $\alpha_j$ equal. Mar 7, 2017 at 16:44
• @RobertIsrael Yes you right. I need $\alpha_j$'s be distinct. Thanks Professor Israel for comment and wait for your answer. Thanks again. Mar 7, 2017 at 17:14
• @RobertIsrael In Maple I used $choose([0..27],8)$ but I did not find answer. For interval bigger than $[0..27]$ Maple made error that "object is too big". Mar 7, 2017 at 17:16
• @RobertIsrael In fact, I have no reason that are there $\alpha_j$'s in $GF(2^8)$ or not? Mar 7, 2017 at 17:27

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)):
for iter from 1 do
F:= (Factors(Q,beta) mod 2);
if nops(F) = 8 then
print(map(t -> subs(x=0,t), F));
break
fi
od:

• Really Really Really thanks for your answer. Mr Professor Israel you are man of MAPLE. Thanks a Million. Mar 7, 2017 at 18:17
• I wish, I had 1000 reputation to present for your answer. Thanks again. Mar 7, 2017 at 18:24
• What a nice and efficient Maple code you have written. Mar 7, 2017 at 18:36
• Dear Professor B.Israel, I want to ask you to help me in the following question. How to modify your maple code such that find an eight tuple $x=(\alpha_1,\alpha_2,\cdots,\alpha_8)$, in the following form $$e_1(x) =e_2(x)=\cdots=e_7(x)=0$$. If thers is no such $x$ in $GF(2^8)$, is it possible to tell how to change your Maple code for $GF(2^{16})$ in order to generate the mentioned eight tuple $x$ where $$e_i(x)=0\, , \, 1\leq i \leq 7$$ I really appreciate your help in resolving the problem. Mar 14, 2017 at 8:21
• An $8$-tuple so that $e_1(x) = \ldots = e_7(x) = 0$ means $\prod_{i=1}^8 (X - \alpha_i) = X^8 + c$. But this being characteristic $2$, every member of your field is an $8$'th power, so $X^8 + c$ always splits as $(X+d)^8$ for some $d$. Thus the only solutions over $GF(2^m)$ have all $\alpha_i$ equal. Mar 14, 2017 at 15:04

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

• What I say in the last paragraphs also applies, of course, to the scaled versions $$x^8+\gamma^6\beta^{85}x^2+\gamma^7x$$ for any $\gamma\in GF(256)^*$. Mar 7, 2017 at 22:36
• It is a great and excellent proof, Professor Jyrki Lahtonen. I have a question that I ask in the next comment. Mar 7, 2017 at 22:42
• Glad to hear you are interested. It is past midnight here, so I need to call it a day. Mar 7, 2017 at 22:47
• Thanks again Professor Jyrki Lahtonen for complete post you made. Mar 7, 2017 at 22:52
• Well spotted @user0410! I did not bring that up, because that case only happens when $3\mid q$. And, please, don't call me a professor, I'm not :-) And, this site is quite egalitarian in many way. Admittedly there are a few users I am inclined to only address with a honorific tagged on - prof. Lubin springs to mind :-) Mar 15, 2017 at 5:21