Krdytkyu

Kaisa Nyberg provided a proof of number of zeros in inverse mapping in finite field ref. The proof is clear for me except the final step where she proved that the following equation has two solution when n is odd in $GF(2^n)$ and 4 solutions when n is even:

$x(x^3 +alpha^3)= 0$

Q1) she applied $gcd(3,2^n-1)=1$ for her proof. could you please explain how to use gcd in finding zeros in $GF(2^n)$?

Q2) I extended her approach to apply for $(x+alpha)^{-2} - x^{-2}=beta$ and obtained $x^{2}(x^6 +alpha^6)= 0$ in $GF(2^n)$ . I got stuck to prove the number of zeros when n is odd and even. i took this approach to understand the mathematical motivation taken for one of the Aria cipher sbox ($x^{247}=x^{-8}$). could you please help me to continue proof number of solutions?

Q1

From the equation
$$
x(x^3+alpha^3)=0
$$
we know that one of the roots is $x=0$, for the rest we want to solve
$$
x^3+alpha^3=0 Longleftrightarrow x^3 = -alpha^3 = alpha^3
$$
If $g$ is a generator of $GF(2^n)$, then $alpha = g^v$ for some integer $0leq v < 2^n-1$ (since $alphaneq 0$). We may also write $x=g^u$ for some integer $0leq u<2^n-1$, so the equation becomes
$$
g^{3u} = g^{3v} in GF(2^n) Longleftrightarrow 3uequiv 3v pmod{2^n-1}
$$
Now if $3$ does not divide $2^n-1$, which is where the $gcd(3,2^n-1)=1$ comes from, then we can multiply by inverse of $3$ to get
$$
u equiv v pmod{2^n-1}
$$
Since both $u,v$ are in $[0,2^n-1)$, there is only 1 distinct root possible, which is $u=v$. This is the obvious root $x=g^u=g^v = alpha$. Hence there are only two roots in total, $0$ and $alpha$.

I think it is quite common to shorten these type of argument like the following:

Let $G$ be a cyclic multiplicative group with order $m$ and $alphain G$. Then
$$x^k = alpha^k$$
has only 1 root if $gcd(k,m)=1$".

For the other case where $3mid 2^n-1$, let $m=2^n-1 = 3d$. The equation is now
$$
begin{align}
3u &equiv 3v pmod{3d}\
u &equiv v pmod d
end{align}
$$
Let $requiv v pmod d$ such that $0leq r < d$. Then $u$ can take 3 solutions $u=r, r+d, r+2d$. Since $0leq r,r+d,r+2d < 3d = 2^n-1$, we know that the elements $g^r,g^{r+d},g^{r+2d}$ are distinct. So we have 4 roots in total: $x=0,g^r,g^{r+d},g^{r+2d}$.

Finally: When $n$ is odd $3$ does not divide $2^n-1$ so by the first part there are two solution. Otherwise $n$ is even, $3$ divies $2^n-1$ so by the second part there are four solutions.

The text writes $d=(2^n-1)/3$ and suggests that the two other roots are $x=alpha^{1+d}$ and $x=alpha^{1+2d}$. Now these roots do satisfy the equation, say:
$$
x^3+alpha^3 = (alpha^{1+d})^3+alpha^3 = alpha^{3+m}+alpha^3 = alpha^3 + alpha^3 = 0
$$
(Since $alpha^m=1$ by Lagrange's Theorem.) The same happens for $x=alpha^{1+2d}$. However I don't think it's quite right since these roots can be repeated, for example if $alpha=1$ then following the text you get the roots $0,1,1,1$. Using the method above you first get $alpha = 1 = g^0$, then the roots are $0,g^0,g^d,g^{2d}$. Maybe I am missing some context where repeated roots cannot happen.

Q2

Similarly, for the equation
$$
x^2(x^6 + alpha^6)=0
$$
we see immediately a (repeated) root of $x=0$. The rest of the roots lie in
$$
x^6 + alpha^6 = 0
$$
Since the field is characteristic two, we have
$$
(x^3+alpha^3)^2 = x^6+alpha^6 = 0
$$
Therefore we are reduced to
$$
x^3 + alpha^3 = 0
$$
This has exactly the same roots as before, depending on whether $n$ is odd or even.