# Depth-free Frobenius map computation in $\mathbb{F}_{p^l}$

I read it somewhere that evaluation of Frobenius maps on elements of $\mathbb{F}_{p^l}$ is multiplicative depth-free. This boils down to the claim that computation of $a^p$ is depth-free inside $\mathbb{F}_{p^l}$.
This is what I understood,
Since elements of $\mathbb{F}_{p^l}$ are polynomials of the form $a_0 + a_1*x + ... + a_{l-1}*x^{l-1}$, let us consider an element $a$.
Now when we compute $a^p$, all the coefficients remain same by Fermat's little theorem, but the positions of these coefficients get shuffled. For e.g. $a_2*x^2 \to a_2*x^{2*p \mod l }$. This means that the exponentiation with $p$ has been reduced to some shifting operations inside the polynomial.
But, how can we say that this exponentiation is depth-free meaning that we can do this with a constant number of mult-gates? Any help is appreciated. Thanks!

• What does depth-free mean? – k.stm Dec 12 '17 at 13:19
• Here, it means we can do $a^p$ with a constant number of multiplication gates whereas if we were to do $a^p$ using regular exponentiation methods, we would require $\log p$ mult-gates – Mayank Dec 12 '17 at 13:20
• Okay, … then what are multiplication gates? – k.stm Dec 12 '17 at 13:21
• A mult-gate takes in 2 arguments and returns their product as output. – Mayank Dec 12 '17 at 13:22
• Computing the Frobenius is, indeed, easy (it's a linear mapping). But I somehow guess that what you read about had to with normal bases. If, instead of a monomial basis, like $1,x,x^2,\ldots, x^{\ell-1}$ modulo some chosen primitive polynomial, you present the elements of the field using a basis of the form $\gamma, \gamma^p,\gamma^{p^2},\ldots,\gamma^{p^{\ell-1}}$, then the calculation of Frobenius becomes a cyclic shift of the sequence of coordinates. – Jyrki Lahtonen Dec 12 '17 at 14:54