4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I suppose you don't want the obvious example: all $\alpha_j = 0$, or the slightly less obvious: all $\alpha_j$ equal. $\endgroup$ Mar 7, 2017 at 16:44
  • $\begingroup$ @RobertIsrael Yes you right. I need $\alpha_j$'s be distinct. Thanks Professor Israel for comment and wait for your answer. Thanks again. $\endgroup$
    – user0410
    Mar 7, 2017 at 17:14
  • $\begingroup$ @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". $\endgroup$
    – user0410
    Mar 7, 2017 at 17:16
  • $\begingroup$ @RobertIsrael In fact, I have no reason that are there $\alpha_j$'s in $GF(2^8)$ or not? $\endgroup$
    – user0410
    Mar 7, 2017 at 17:27

2 Answers 2

4
$\begingroup$

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:
$\endgroup$
5
  • $\begingroup$ Really Really Really thanks for your answer. Mr Professor Israel you are man of MAPLE. Thanks a Million. $\endgroup$
    – user0410
    Mar 7, 2017 at 18:17
  • $\begingroup$ I wish, I had 1000 reputation to present for your answer. Thanks again. $\endgroup$
    – user0410
    Mar 7, 2017 at 18:24
  • $\begingroup$ What a nice and efficient Maple code you have written. $\endgroup$
    – user0410
    Mar 7, 2017 at 18:36
  • $\begingroup$ 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. $\endgroup$
    – user0410
    Mar 14, 2017 at 8:21
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 14, 2017 at 15:04
2
$\begingroup$

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

$\endgroup$
8
  • 1
    $\begingroup$ 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)^*$. $\endgroup$ Mar 7, 2017 at 22:36
  • $\begingroup$ It is a great and excellent proof, Professor Jyrki Lahtonen. I have a question that I ask in the next comment. $\endgroup$
    – user0410
    Mar 7, 2017 at 22:42
  • 1
    $\begingroup$ Glad to hear you are interested. It is past midnight here, so I need to call it a day. $\endgroup$ Mar 7, 2017 at 22:47
  • $\begingroup$ Thanks again Professor Jyrki Lahtonen for complete post you made. $\endgroup$
    – user0410
    Mar 7, 2017 at 22:52
  • 1
    $\begingroup$ 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 :-) $\endgroup$ Mar 15, 2017 at 5:21

You must log in to answer this question.

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