4

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.

Community
  • 1
  • 1
torrho
  • 1,823
  • 4
  • 16
  • 21
  • Qiaochu suggested polynomials and reducing after every step; that sounds fair enough to me. Do you have any polynomial multiplication written? How about the reduction? – sarnold Jul 24 '12 at 03:48
  • I don't have anything written at the moment. From previous experience coding Z/nZ modpow's I have a hunch that reduction after every step just seems slow. I figure there has to be some kind of way to avoid the iterative (recursive) method of doing this because it can be done in an equivalent setting using montgomery exponentiation in Z/nZ. – torrho Jul 24 '12 at 03:54

1 Answers1

3

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.

Community
  • 1
  • 1
torrho
  • 1,823
  • 4
  • 16
  • 21