Fast Exponentiation for galois fields

问题:

I want to be able to compute

g^x = g * g * g * ... * g     (x times)

where g is in a finite field GF(2^m). Here m is rather large, m = 256, 384, 512, etc. so lookup tables are not the solution. I know that there are really fast algorithms for a similar idea, modpow for Z/nZ (see page 619-620 of HAC).

1. What is a fast, non-table based way to compute cycles (i.e. g^x)?
2. This is definitely a wishful question but here it comes: Can the idea of montgomery multiplication/exponentiation be 'recycled' to Galois fields? I would like to think so because of the isomorphic properties but I really don't know.

Remark: this is from my post on math.stackoverflow.com I suppose this is the best community to ask this question.

回答1:

From the math stackexchange community, I had two people suggest Binary Exponentiaion. Wikipedia states a recursive it as a recursive algorithm. It can be changed to an iterative algorithm as shown in the Wiki's psuedocode.

I frowned at the idea at first but I looked into it more and I found two papers (1, 2) that can help implement binary exponentiation in Galois Fields that uses Montgomery Multiplication.

Furthermore, Jyrki Lahtonen suggested using normal bases (or when m =/= 256,384, 512, etc. optimal normal bases) to speed up the multiplication. Algorithms for this method of multiplication can be found in this paper.

Thanks to sarnold for his/her input.