Montgomery multiplication in GF(2^k)

Cetin K. Koc and Tolga Acar

April 1998

## Abstract

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.

## Details

Publication type | Article |

Published in | Designs, Codes and Cryptography |

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

Pages | 57–69 |

Volume | 14 |

Publisher | Kluwer Academic All copyrights reserved by Kluwer Academic 2007. |

## Publication files

## By the same authors

## People also read

##
Related people