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$

  • 1
    $\begingroup$ The way I solved it was by contradiction. I assumed there is a prime factor in the gcd. Then I set $k = 2^{t/2 - 1}$ for $t$ even and $k = 2^{(t - 1)/2}$ for $t$ odd, determine the resulting equations in terms of $k$, manipulate them to get a limited set of possible values for this prime factor of the gcd, and then prove that none of them are possible. There may be other ways, but this method worked for me. Give this a try to see what you can come up with. In the meantime, I will start writing up my solution, and will adjust it as needed depending on what you come up with. $\endgroup$ – John Omielan Apr 12 at 3:52
  • 1
    $\begingroup$ For the even case: $$2x^4-1\equiv 11-10x\pmod{x^2+x-2}.$$ Plugging in $x=2^{t/2}$ tells us that any gcd of $2^n-1$ and $d-1$ is also a factor of $11-10\cdot2^{t/2}$. Keep going... $\endgroup$ – Jyrki Lahtonen Apr 12 at 3:58
  • 1
    $\begingroup$ I also approve of John Omielan's ideas. Niho exponents are heavily tailored, and this part is a bit dull. The fun begins when proving the APN property (or proving that you have found a good decimation of the sequence in the original Niho stuff on sequences and their correlations). $\endgroup$ – Jyrki Lahtonen Apr 12 at 4:07
  • 1
    $\begingroup$ continuing on @JyrkiLahtonen concept : multiply $x^2+x-2$ by 100 , then $gcd(100x^2+100x-200,10x-11)$ = $gcd(10x-11,31)$ $\endgroup$ – hardyrama Apr 12 at 5:57
  • 1
    $\begingroup$ @hardyrama Thanks for showing your effort. You are correct that for even $t$ that the only prime factor possible in the gcd is $31$. As you can see in my answer, I determine the same thing in a somewhat different fashion. This shows there is more than one way to solve this problem. You may wish to try a different way than what I've done to see if it's simpler & easier for you, or at least "better" in some way as far as you're concerned. $\endgroup$ – John Omielan Apr 12 at 6:04

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.

  • $\begingroup$ could you please explain how is 32 obtained in $32𝑘^4−1≡0(mod𝑝)$? $\endgroup$ – hardyrama Apr 13 at 6:37
  • 1
    $\begingroup$ @hardyrama Since $k = 2^{t/2-1}$ in that case, then $k^4 = 2^{4(t/2-1)} = 2^{2t - 4}$, so multiplying both sides by $2^5 = 32$ gives $32k^4 = 2^{2t-4+5} = 2^{2t+1}$. Since $n = 2t+1$, this means that $2^n - 1 = 32k^4 - 1$. Is this clear now? $\endgroup$ – John Omielan Apr 13 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.