First let me tell you some background. Consider $p\equiv 13 \bmod 32$, therefore, $p\equiv 5\bmod 8$. That means, 2 is a none-quadratic residue in $GF(p)$. Therefore, we are able to build up $\newcommand\F{\mathbb F} \F_{p^{16}}:=GF(p^{16})\cong \F_p[x]/(x^{16}-2)$.

That means we have the identity $x^{16}=2$ and $2^{\frac{p-1}{2}}\equiv -1\bmod p$ (Quadratic reciprocity, 2nd supplement). Now we have

For any $A\in\F_{p^{16}}$ there are $a_0,...,a_{15}\in\F_p$ such that $A=\sum_{i=0}^{15} a_ix^i$.

Now consider the p-Frobenius:

$\pi_p(a)=A^p= \sum_{i=0}^{15} a_i \left(x^i\right)^p$, since $a_i^p \equiv a_i \bmod p$ from Fermats little theorem.

That means, all we have to do is to produce valid output for $x^{ip}$ for any $1\leq i \leq 15$.

Let me start with i=15 (the easy one..):

$\left( x^{15} \right)^p = \left( x^{16} \right)^{\frac{p-1}{2}}x^2=-x^2$ Edit: {Oh, I did wrong. This is not equal. I cannot take out the $x^2$ part in this way...}


Now I'm out of ideas to deal with the rest where the Question starts. This might be solved by computer-power, but I don't know how to. Hints for some steps would be great. I do not need a complete solution, I would like to master this for my own.


My aim is always: Reaching an expression $(x^{16})^{\frac{p-1}{2}}$ or $(x^{16})^{\frac{p^2-1}{8}}$ which will be equivalent to -1.

Sage attemption with the lates suggested prime for KSS16 in pairings:

Defining $R16 := GF(p^{16})$


R = GF(p) 
_.<x> = PolynomialRing(R)
R16.<x> = R.extension(x^16 - 2, 'x')




599280983495543796770673976542410445676498658176691546033897360530150567095232487071355883922261646714 * x^3

which is different from the one I figured out.

Edit newest attemption

First we have: $p\equiv 13\bmod 16$ then $\left( x^{15} \right)^p = \left( x^{15\cdot 16} \right)^{\frac{p-13}{16}}x^{13} = 2^{15\cdot \frac{p-13}{16}}x^{13}$ which won't lead to the sage-expression.

  • 2
    $\begingroup$ Let $p=16k+13$, then it should be $$(x^{15})^p=\bigl(x^{15\cdot16}\bigr)^kx^{\color{red}{15\cdot}13}=2^{15k}\bigl(2^{12}x^3\bigr)=2^{15k+12}x^3=-2^{7k+6}x^3.$$ $\endgroup$ – Mercury Aug 31 '17 at 1:00
  • $\begingroup$ How did you do this formating in the comments? This calculation will lead me to the end. Thank you :) Maybe it was to late for doing such work :( It is totally clear. $\endgroup$ – Shalec Aug 31 '17 at 9:47
  • $\begingroup$ I just use $\$\ldots\$$ and $\$\$\ldots\$\$$ as usual. Do you have problem with that? $\endgroup$ – Mercury Aug 31 '17 at 11:03
  • $\begingroup$ Ah, I didn't know the dbl-$ sign. Thank you :) $\endgroup$ – Shalec Aug 31 '17 at 12:17

You didn't prove that $x^{16}-2 \in \mathbb{F}_p[x]$ is irreducible whenever $p\equiv 13 \bmod 32$.

If $\alpha^{16} = 2$ then ` $$x^{16}-2 = \prod_{k=1}^{16} (x-\zeta_{16}^k \alpha)$$

and there is a primitive $16$-th root of unity such that $\pi_p(\alpha) = \zeta_{16} \alpha$, $\pi_p^2(\alpha) = \pi_p(\zeta_{16})\zeta_{16} \alpha = \zeta_{16}^{p+1}\alpha$, $\pi_p^m(\alpha)=\zeta_{16}^{(p^m-1)/(p-1)}\alpha$ and the minimal polynomial of $\alpha$ is $$f(x) = \prod_{m=1}^N (x-\pi_p^m(\alpha)) = \prod_{m=1}^N (x-\zeta_{16}^{(p^m-1)/(p-1)} \alpha) \quad \in \mathbb{F}_p[x]$$ where $N$ is the least integer such that $16 \ | \ \frac{p^N-1}{p-1}$. If $p = 1+ 2^l (2a+1)$ it means $2^{l+4} \ | \ p^N-1$ so that $N$ is the order of $p \bmod 2^{l+4}$.

If $p \equiv 13 \bmod 64$ or $p \equiv 13+32 \bmod 64$ then $l = 2$ and $ord(13 \bmod 2^{l+4}) = ord(13 +32\bmod 2^{l+4}) = 16$ thus yes $x^{16}-2 \in \mathbb{F}_p[x]$ is irreducible.

  • 1
    $\begingroup$ For $p\equiv1\pmod{4}$, we have $\nu_2(p^N-1)=\nu_2(p-1)+\nu_2(N)$. This derives $16\mid N$ form $2^{l+4}\mid p^N-1$. Besides, we need the fact that $(\frac{2}{p})=-1$, which implies $(\pi_p(\alpha)/\alpha)^8=\pi_p(\alpha^8)/\alpha^8\neq1$. So we may relax the condition to $p\equiv5\pmod{8}$ for the irreducibility of $x^{16}-2$ over $\mathbb{F}_p$. $\endgroup$ – Mercury Aug 31 '17 at 4:46
  • $\begingroup$ The paper, where this prime was suggested, suggested also the extension field mod $x^{16}-2$. I was believing ;) But thank you for filling the belief with scientific background :D $\endgroup$ – Shalec Aug 31 '17 at 9:29
  • 1
    $\begingroup$ The way Shalec phrased this (and an earlier) question made it clear that this particular obstacle had alread been cleared. Still, I admit that this was also the first thing I checked :-) I guess we have seen too many questions here where the asker says: "the polynomial has no zeros, so it is irreducible". $\endgroup$ – Jyrki Lahtonen Aug 31 '17 at 13:01

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.