Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?
share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.