If we're in any finite field and we want to compute something like $x^{p^k-1}$ we can use cyclotomic polynomials to factorize. But we allways will have to compute $x^{p-1}=x^p x^{-1}$.
Therefore, we have to invert. But is there any trick, that I could be in the position to compute that value, without inverting so? I'm thinking about homomorphisms/isomorphisms, to switch that problem to something like $x^{f(p-1)}$.
In all those steps, p is a prime. I would recommend, if there is no "do it, I know how." just do a brainstorming with suggestions.
Special Case
In my special case I consider any $A\in\mathbb F_{p^{16}}$ and trying to compute $A^{p^8-1}\in\mathbb F_{p^{16}}$. I would like to find a way without splitting up like this: $A^{p^8}A^{-1}$, where $p\equiv 5\bmod 8$. The way I'm looking for does not require to compute any inverse.
Possible way with inversion
I know that there are different kinds of "Square-and-Multiply" algorithm, like Montgomery, Sliding Window, ... Since the $A$ is random, I cannot precompute (or I do not see any sence in doing this, because the random entropy for $\mathbb F_{p^{16}}$ is just huge ..)
The only terms, I could precompute (which would be senseful) are the powers of $x$.
If I consider the representation $$A=\sum\limits_{k=0}^{n-1} a_k x^k$$ with $a_k\in\mathbb F_p$ and the tower $\mathbb F_{p^{16}} = \mathbb F_p[x]/(x^{16}-1)$ (is this really an equal sign, and no isomorphism sign?) I could transform that polynomial into a companion matrix, invert that matrix, and map the result back. The last part "mapt the result back" could probably be a difficult part.