A Complexity-Effective Version of Montgomery's Algorihm

Abstract

A new version of Montgomery’s algorithm for modular multiplication of large integers and its implementation in hardware is presented. It has been designed to meet the predominant requirements of most modern devices: small chip area and low power consumption. The algorithm is superior to the original method by a factor of 2, with respect to both area and latency. The new method has a simple structure. It requires a small amount of precomputation and storage in order to reduce the number of neccessary additions by a factor of 2.