2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ What does depth-free mean? $\endgroup$ – k.stm Dec 12 '17 at 13:19
  • $\begingroup$ 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 $\endgroup$ – Mayank Dec 12 '17 at 13:20
  • $\begingroup$ Okay, … then what are multiplication gates? $\endgroup$ – k.stm Dec 12 '17 at 13:21
  • $\begingroup$ A mult-gate takes in 2 arguments and returns their product as output. $\endgroup$ – Mayank Dec 12 '17 at 13:22
  • 2
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Dec 12 '17 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.