# Basics

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...}

# Question

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.

# Attemption

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})$

#p=615623382030675150502066218751443438064107566348210118507940234835256709422634902533028653925239565581

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


calling

(x^15)^p


output

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.

• 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.$$ – Mercury Aug 31 '17 at 1:00
• 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. – Shalec Aug 31 '17 at 9:47
• I just use $\$\ldots\$$and \\\ldots\\$$ as usual. Do you have problem with that? – Mercury Aug 31 '17 at 11:03
• Ah, I didn't know the dbl-$sign. Thank you :) – Shalec Aug 31 '17 at 12:17 ## 1 Answer 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. • 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$. – Mercury Aug 31 '17 at 4:46 • 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 – Shalec Aug 31 '17 at 9:29
• 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". – Jyrki Lahtonen Aug 31 '17 at 13:01