Cetin K. Koc and Tolga Acar
15 August 1996
We show that 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.
In Third Annual Workshop on Selected Areas in Cryptography
Publisher Springer Verlag
All copyrights reserved by Springer 2007.
|Address||Queen's University, Ontario, Canada|