Permutations Sets in Binary Finite Fields

by user0410   Last Updated September 11, 2019 13:20 PM

Let $a \in \mathbb{F}_{2^n}$ such that the multiplicative order of $a$ is r. Now consider the following two sets:

$$ {\bf A}=\{0,1,a,a^2,\cdots ,a^{r-1} \}, \quad {\bf B}=\{0,1,a+1,a^2+1,\cdots ,a^{r-1}+1 \}. $$

My question: How to prove that the set $\bf B$ is a permutation of the set $\bf A$?

Thanks for any help

Tags : finite-fields


Answers 1


This is false in general. Let $n=4$, $r=5$. If $\gamma$ is a zero of the polynomial $x^4+x+1$, then $a=\gamma^3$ is of order $r$. According to a table of the elements of $\Bbb{F}_{16}$ we then have $$ A=\{0,1,\gamma^3,\gamma^6=\gamma^3+\gamma^2,\gamma^9=\gamma^3+\gamma,\gamma^{12}=\gamma^3+\gamma^2+\gamma+1\}. $$ The presentation of an element of $\Bbb{F}_{16}$ as a polynomial in $\gamma$ of degree $<4$ is unique, so we immediately see that $B$ is a different set. For example $\gamma^3+1\in B, \gamma^3+1=\gamma^{14}\notin A$.

Jyrki Lahtonen
Jyrki Lahtonen
September 11, 2019 13:16 PM

Related Questions