Arithmetic in finite fields with different bases

Question

For what kind of operations are the normal bases better in cryptography? And for which operations are the polynomial bases better?

Answer 1

If you are using a normal basis for $\mathbb{F}_{q^{n}}$, $1, \alpha, \alpha^{q}, \ldots, \alpha^{q^{n-1}}$, then you can represent any element as a vector as follows: $$x = a_{0} + a_{1}\alpha + \cdots + a_{i}\alpha^{q^{i}} + \cdots + a_{n-1}\alpha^{q^{n-1}} = (a_{0}, a_{1}, \ldots, a_{n-1}).$$ Now if you raise everything to the $q$ power, you obtain $$x^{q} = a_{n-1} + a_{0}\alpha + a_{1}\alpha^{2} + \cdots + a_{i-1}\alpha^{q^{i}} + \cdots + a_{n-2}\alpha^{q^{n-1}} = (a_{n-1}, a_{0}, a_{1}, \ldots, a_{n-2}).$$

Now, most commonly (in computer science applications) you are going to be working in a field with $q=2$. Also, there are many computational algorithms that make use of repeated squaring. So you can square a field element using this representation by simply performing a cyclic shift of the vector coefficients.

(Note that none of this is specific to cryptography, just for general computation with finite fields.)