Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Montgomery Multiplication in GF(2^k)

Cetin K. Koc and Tolga Acar

Abstract

We show that the multiplication operation c = a b r^(-1) in the field GF(2k) 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(2k). 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 typeInproceedings
Published inThird Annual Workshop on Selected Areas in Cryptography
URLhttp://cryptocode.net/docs/c14.pdf
Pages95–106
AddressQueen's University, Ontario, Canada
PublisherSpringer Verlag
> Publications > Montgomery Multiplication in GF(2^k)