Montgomery multiplication in \(\text{GF}(2^ k)\) (Q1379662)

The authors generalize the method of Montgomery multiplication to finite fields of even characteristic. They give bit level and word level descriptions for the methods of multiplication and squaring. Examples of the method are given plus an analysis of the methods. All the methods are given when the elements are represented by a polynomial basis. The analysis makes use of a word-level GF(2) polynomial multiplication instruction. The authors point out this can be implemented in one of two ways. Firstly by using Shift and XOR operations and secondly by table look up. They point out that both of these are unsatisfactory as the required instruction is simpler than the integer multiply instruction which is available on most processors. It is simpler due to the absence of carry propogation.