$\newcommand\F{\mathbb F}$
Example $\F_{p^2}\cong \F_p[x]/(X^2-2)$ for $p\equiv \pm 3\bmod 8$
For any $A\in\F_{p^2}$ we get the $\F_p$ representation as $A=a+bx$ for $a,b\in\F_p$. Computing the p-Frobenius reveals $A^p=(a+bx)^p=a^p+b^p+x^p$, thanks to the freshmen's dream working modulo $p$. The next step is to know the "Fermats little theorem", that says $a^p\equiv a \bmod p$. Therefore, we have $A^p = a+bx^p$. Now we take a closer look onto $x^p$:
$x^p= (x^2)^{\frac{p-1}{2}}x = 2^{\frac{p-1}{2}}x \equiv -x \bmod p$, since 2 is a none-quadratic resudue in our considered case $p\equiv \pm 3\bmod 8$.
All in all the p-Frobenius increases the computation time to be a simple conjugation: $A^p=(a+bx)^p=a-bx$
Question
I derived this technic for the tower field $\mathbb F_{p^{16}}\cong \F_p[x]/(x^{16}-2)$ but I'm not sure if I did any mistakes. Since I am not allowed to publish this, I need to ask something in general about this.
How would you compute the Frobenius? Is there any "state of the art" design? Which tricks would you use to get to the aim?
My Attempt
I started by building up a tower, like in sage:
p=103
R = GF(p)
_.<U> = PolynomialRing(R)
R2.<U> = R.extension(U^2 - 2, 'U')
_.<V> = PolynomialRing(R2)
R4.<V> = R2.extension(V^2 - U, 'V')
_.<W> = PolynomialRing(R4)
R8.<W> = R4.extension(W^2-V, 'W')
_.<X> = PolynomialRing(R8)
R16.<X> = R8.extension(X^2-W, 'X')
But this does not hold for any prime congruent to $\pm 3\bmod 8$. There we have to check on equivalence classes module 32. The class of my interest is $p\equiv 13\bmod 32$.
Question rising from attemption
Sage cannot help me, verify the Frobenius for my prime, since the prim-test fails. I could consider any other prime from the same equivalence class, but how could I be sure that this won information holds? I check via bruteforce for any prime (first 3 found primes from the same equivalence class) modulo 64, and it turned out, that all information from mod 32 is repeated.