Niho APN prove that $gcd(d − 1, 2^n − 1)$ , where d is exponent

Question

in a finite field $F_{2^n}$

where $ d = \begin{cases} 2^t + 2^{t/2}-1 & \text{t even}\\ 2^t + 2^{(3t+1)/2}-1 & \text{t odd} \end{cases} $

and $n=2t+1$

How do you prove that $gcd(d-1,2^{n}-1)=1$

Answer 1

You're given that

$ d = \begin{cases} 2^t + 2^{t/2}-1 & t \text{ even}\\ 2^t + 2^{(3t+1)/2}-1 & t \text{ odd} \end{cases} $

and $n=2t+1$. You're asked to prove

$$\gcd(d-1,2^{n}-1)=1 \tag{1}\label{eq1}$$

This can be shown by confirming any possible prime factor of the gcd can never actually be a factor. To do this, first handle where $t$ is even. In that case,

$$d - 1 = 2^t + 2^{t/2} - 2 = 2\left(2^{t-1} + 2^{t/2 - 1} - 1\right) \tag{2}\label{eq2}$$

Since $2^n - 1$ is odd, $2$ can't be a factor of the gcd. Letting $k = 2^{t/2 - 1}$, then any prime $p$ dividing the gcd requires that

$$2k^2 + k - 1 \equiv 0 \pmod p \; \Rightarrow \; (2k - 1)(k + 1) \equiv 0 \pmod p \tag{3}\label{eq3}$$ $$32k^4 - 1 \equiv 0 \pmod p \tag{4}\label{eq4}$$

From \eqref{eq3}, $k \equiv -1 \pmod p$ or $2k \equiv 1 \pmod p$. Using the first value in \eqref{eq4} gives $31 \equiv 0 \pmod p$, i.e., $p = 31$. Since $2 ^ 5 = 32 \equiv 1 \pmod{31}$, then the $2^a \pmod{31}$ values will repeat with a period of $5$, and there is no power of $2$ where $2^a \equiv -1 \pmod{31}$. However, $k = 2^{t/2 - 1} \equiv -1 \pmod{31}$, so this is not possible.

With the second case of $2k \equiv 1 \pmod p$, taking the fourth power & then multiplying by $2$ gives $32k^4 \equiv 2 \pmod p$. However, using \eqref{eq4} gives that $2 \equiv 1 \pmod p$, which is not possible.

For the case where $t$ is odd,

$$d - 1 = 2^t + 2^{(3t+1)/2}-2 = 2\left(2^{t-1} + 2^{(3t-1)/2}-1\right) \tag{5}\label{eq5}$$

In this case, let $k = 2^{(t-1)/2}$, and proceed as before to get

$$2k^3 + k^2 - 1 \equiv 0 \pmod p \tag{6}\label{eq6}$$ $$8k^4 - 1 \equiv 0 \pmod p \tag{7}\label{eq7}$$

In this case, you can't easily factor \eqref{eq6}. Instead, I manipulated the $2$ equations to keep reducing the highest power in use until I finally got an integer only. First, \eqref{eq7} has $8k^4 \equiv 1 \pmod p$, so I used this in the $-1$ term of \eqref{eq6} to get

$$2k^3 + k^2 - 8k^4 \equiv 0 \pmod p \; \Rightarrow \; 8k^2 - 2k - 1 \equiv 0 \pmod p \tag{8}\label{eq8}$$

since $p$ can't divide $-k^2$ as it's a power of $2$ so I can remove that factor. Next, use $4$ times \eqref{eq6} and subtract $k$ times \eqref{eq8} to get

$$6k^2 + k - 4 \equiv 0 \pmod p \tag{9}\label{eq9}$$

Now, $4$ times \eqref{eq9} subtract $3$ times \eqref{eq8} gives

$$10k - 13 \equiv 0 \pmod p \; \Rightarrow \; 10k \equiv 13 \pmod p \tag{10}\label{eq10}$$

Multiplying \eqref{eq9} by $10$ and then substituting \eqref{eq10} gives

$$60k^2 + 13 - 40 \equiv 0 \pmod p \; \Rightarrow \; 60k^2 \equiv 27 \pmod p \tag{11}\label{eq11}$$

Multiplying both sides of \eqref{eq10} by $6k$ and using \eqref{eq11} gives that

$$78k \equiv 27 \pmod p \tag{12}\label{eq12}$$

Multiplying both sides of \eqref{eq10} by $8$ gives that

$$80k \equiv 104 \pmod p \tag{13}\label{eq13}$$

Next, \eqref{eq13} subtract \eqref{eq12} gives

$$2k \equiv 77 \pmod p \tag{14}\label{eq14}$$

Finally, multiplying both sides of \eqref{eq14} by $5$ and using \eqref{eq10} gives

$$385 \equiv 13 \pmod p \; \Rightarrow \; 372 \equiv 0 \pmod p \tag{15}\label{eq15}$$

Note there might be, and likely is, a simpler & easier way to get \eqref{eq15}. Since $372 = 2^2 \times 3 \times 31$, this means that $p$ must be $3$ or $31$. However, $2^n$, since $n$ is odd, is always congruent to $2$ modulo $3$. As mentioned before with $31$, for $2^n$ to be congruent to $1$ means that $n \equiv 0 \pmod 5$, i.e., $2t + 1 \equiv 0 \pmod 5 \; \Rightarrow \; t \equiv 2 \pmod 5$ and $t - 1 \equiv 1 \pmod{5}$. Since $t$ is odd, this means that $t \equiv 7 \pmod{10}$, so $(3t - 1)/2 \equiv 0 \pmod 5$. Thus, $2^{t-1} + 2^{(3t-1)/2}-1 \equiv 2 + 1 - 1 = 2 \pmod{31}$. This shows that $31$ can't be a factor of $d - 1$.

As this overall proves there's no prime factor of $p$ which divides the gcd value for $t$ being even or odd, then \eqref{eq1} is true for all cases.