A Permutation Associated With GF $(2^n)$

Abstract

If $\alpha$ is a primitive root of the finite field $GF(2^n)$, we define a function ${\pi }_n$ on the set $E_n=\{1,2,\dots ,2^n–2\}$ by
$${\pi }_{\alpha }(i)=j\text{iff}{\alpha }^i=1+{\alpha }^j.$$
Then ${\pi }_{\alpha }$ is a permutation of $E_n$ of order $2$. The path-length of $\pi$, denoted $PL(\pi )$, is the sum of all the quantities $|\pi (i)–i|$,
and the rank of $\pi$ is the number of pairs $(i,j)$ with $i\pi (j)$. We show that $PL(\pi )=2(2^n–1)(2^{n-1}–1)/3$, and the rank of $\pi$ is $(2^{n-1}–1{)}^2$.

If $gcd(k,2^n–1)=1$, then $M_k(x)=kx(\mathrm{mod}{2}^n–1)$ is a permutation of $E_n$. We show that a necessary condition for the function $f_i(x)=1+x+\cdots +x^i$ to be a permutation of $GF(2^n)$, is that the function $g_k(r)=\pi (M_{k+1}(r))–\pi (r)$ be a permutation of $E_n$ such that exactly half the members $r$ of $E_n$ satisfy $g_k(r)r$.