2
$\begingroup$

I am not sure if I am talking to the correct community (perhaps stack overflow is best). I want to be able to compute $g^x = \underbrace{g \cdot g \cdot \dots \cdot g}_\text{x amount of times}$ really fast, where $g \in GF\left(2^m \right)$.

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 $\mathbb{Z}/n\mathbb{Z}$ (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/exponention be 'recycled' to galois fields?

2 Answers 2

2

Binary exponentiation, aka square and multiply is the way to go. A possibility that comes to mind is to use a suitable normal basis to represent the elements of $GF(2^n)$. The reason is that then squaring becomes a very cheap operation. It is equivalent to cyclically shifting the coordinate bits.

To optimize the multiplication you want to use such a normal basis that the products of the basis elements can be written as sums of as few basis elements as possible. Your set of values for $m$ is probably not too nice in the sense that so called optimal normal bases probably won't exist for any of thos. Anyway, IIRC the Handbook of Cryptography has an algorithm for finding a reasonably good normal basis.

If your application insists on using a monomial basis for the field in question, then you need to write a routine for changing from one basis to another.

  • 0
    @mjohn1282 review the handbook of applied cryptography's Chapter 14 for pseudocode. http://cacr.uwaterloo.ca/hac/about/chap14.pdf2015-02-03
2

Pick a primitive polynomial and use binary exponentiation together with repeated use of the Euclidean algorithm to reduce modulo your primitive polynomial.

Montgomery multiplication should generalize just fine.

  • 0
    @Qiaochu Yuan♦ thank you for your help and input on the subject matter2012-07-24