Montgomery multiplication in GF(2^k)

Cetin K. Koc and Tolga Acar

April 1998

We showthat the multiplication operation $c = a · b · r^{−1}$ in the field $GF(2^k)$ can be implemented significantly faster in software than the standard multiplication, where r is a special fixed element of the field. This operation is the finite field analogue of the Montgomery multiplication for modular multiplication of integers. We give the bit-level and word-level algorithms for computing the product, perform a thorough performance analysis, and compare the algorithm to the standard multiplication algorithm in $GF(2^k)$. The Montgomery multiplication can be used to obtain fast software implementations of the discrete exponentiation operation, and is particularly suitable for cryptographic applications where k is large.

PDF file |

In Designs, Codes and Cryptography

Publisher Kluwer Academic

All copyrights reserved by Kluwer Academic 2007.

Type | Article |

URL | http://cryptocode.net/docs/j47.pdf |

Pages | 57–69 |

Volume | 14 |

> Publications > Montgomery multiplication in GF(2^k)