3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ So what if, for example, $a \in F_8$ and I want to compute $a^9$?? $\endgroup$ – Boby Aug 1 '14 at 19:06
  • $\begingroup$ Remember that the field $\Bbb F_{p^n}$ has characteristic $p$. $\endgroup$ – Ben Grossmann Aug 1 '14 at 19:10
  • $\begingroup$ But how would you use Fermat's Little Theorem to do that? $\endgroup$ – Boby Aug 1 '14 at 19:14
  • 1
    $\begingroup$ Depends on your hardware and the size of the field. If the field is small (say $q=p^n<50000$), then in programs I use discrete logarithm tables. See my Q&A pair for examples of discrete log tables, when $q\in\{4,8,16\}$. For large fields (when generation and/or storing of the said log tables is not feasible) people use the trick described by MJD. If you use a normal basis for presenting elements, then there is the short cut that raising to power $p$ is free of charge in the sense that it amounts to cyclically shifting the sequence of coordinates. $\endgroup$ – Jyrki Lahtonen Aug 1 '14 at 19:25
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ A close examination of the process shows that the precise sequence of operations is determined by the binary expansion of $m$. $\endgroup$ – Lubin Aug 1 '14 at 19:37
2
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ could you elaborate on the "Frobenius automorphism very easy" sentence? $\endgroup$ – Jason S Jul 8 '18 at 23:43
  • 1
    $\begingroup$ @JasonS: I gave one example: coordinates relative to a normal basis. $\endgroup$ – user14972 Jul 9 '18 at 0:00

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.