# 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$.

$\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.

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
• I just use $\$\ldots\$$and \\\ldots\\$$ as usual. Do you have problem with that? – Mercury Aug 31 '17 at 11:03