Fast software multiplication in F2[x] for embedded processors

Abstract

We present a novel method for fast multiplication of polynomials over F-2 which can be implemented efficiently in embedded software. Fast polynomial multiplication methods are needed for the efficient implementation of some cryptographic and coding applications. The proposed method follows a strategy to reduce the memory accesses for input data and intermediate values during computation. This strategy speeds up the binary polynomial multiplication significantly on typical embedded processors with limited memory bandwidth. These multiplications are usually performed by the comb method or the Karatsuba-based methods in embedded software. The proposed method has speed and memory advantages over these methods on embedded platforms for the polynomial degrees usually encountered in practical cryptosystems. We perform a detailed complexity analysis of the proposed method and complexity comparisons with the other methods. Finally, we present the running limes of the proposed method and its alternatives on ARM7TDMI processor.