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.
$\begingroup$
$\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
Add a comment
|
$\begingroup$
$\endgroup$
1
One common trick, which requires $O(\log_2 m)$ multiplications, is to use the following algorithm:
- If $m$ is even, calculate $b=a^{m/2}$ and then use one additional multiplication to find $a^m = b^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.
-
$\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
$\begingroup$
$\endgroup$
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$.
-
$\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
