Raising to the power over finite fields ??

Question

Are there any tricks with raising an element from a finite field to power. For example let $ a \in GF(p^n)$ and I want to compute $a^m$ for some $m \in \mathbb{Z}$. Is there a nice trick to do this fast?

Many thanks.

Answer 1

One common trick, which requires $O(\log_2 m)$ multiplications, is to use the following algorithm:

1. If $m$ is even, calculate $b=a^{m/2}$ and then use one additional multiplication to find $a^m = b^2$.
2. If $m$ is odd, calculate $b=a^{(m-1)/2}$ and then use two additional multiplications to find $a^m = ab^2$.

For example, to calculate $a^{1000}$, you calculate the following, using one multiplication each: $a^2, a^3, a^6, a^7, a^{14}, a^{15}, a^{30}, a^{31}, a^{62}, a^{124}, a^{125}, a^{250}, a^{500}, a^{1000}$, for a total of 14 multiplications. To calculate $a^{1000000}$ would require only about twice as many multiplications.

This is not optimal, but it is fast enough that people often don't bother with anything faster.

Answer 2

In some representations of the field $\mathbb{F}_{p^n}$, computing $\alpha^p$ -- called the Frobenius automorphism -- is very easy. For example, if you write elements via their coordinates with respect to a normal basis over $\mathbb{F}_p$ (i.e. a basis of the form $\{ \beta, \beta^p, \beta^{p^2}, \ldots, \beta^{p^{n-1}}\}$), then the Frobenius automorphism is just cyclically permuting the coordinates.

If it's not, it's still a $\mathbb{F}_p$-linear transformation, and so in many other representations, you can simply compute the matrix representing this linear transformation, and so you can raise to the $p$-th power simply by multiplying by this matrix. (or maybe your representation gives a faster way to do this) And by taking powers of this matrix, you can thus compute $\alpha^{p^k}$ efficiently.

If you're trying to compute $\alpha^b$ and $b \geq p$, the above gives you a short cut, similar to the usual "square and multiply" algorithms.

In some other representations, your problem is trivial: e.g. if you store a finite field element as its discrete logarithm, all you have to do to compute $\alpha^k$ is to compute a multiplication by $k$, modulo $p^n - 1$.