# Cycling through powers of a generator of finite field. Something similar to modpow for Z/nZ

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?
-

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.

-
The algorithms I have looked at to use square and multiply, square and multiply using montgomery multiplication[1 , 2 ], and the normal bases multiplication. hopefully, I will implement these and release my code to the public later on this year or next year. – torrho Jul 24 '12 at 16:08
Thank you for your help and input on the subject matter. – torrho Jul 24 '12 at 16:10
@torrho: Do you public your implementation. I am working in GF2 and I would like to use your method – mjohn1282 Jan 12 '15 at 9:26
@mjohn1282 review the handbook of applied cryptography's Chapter 14 for pseudocode. cacr.uwaterloo.ca/hac/about/chap14.pdf – torrho Feb 3 '15 at 19:36

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.

-
is there a nice way to make that binary exponentiation into an iterative method? – torrho Jul 24 '12 at 0:46
I don't know. I'm not the right person to ask this kind of question, really. – Qiaochu Yuan Jul 24 '12 at 0:55
@torrho: Isn't square and multiply an iterative method? – Jyrki Lahtonen Jul 24 '12 at 9:54
the way wikipedia defined squaring and multiplying was recursive. However any recursive method can be made iterative. so I suppose the answer is yes. On second look of the definition, it shouldn't be too hard to turn the wiki definition to a recursive one. – torrho Jul 24 '12 at 15:30
@Qiaochu Yuan♦ thank you for your help and input on the subject matter – torrho Jul 24 '12 at 16:11