08-09-2017, 11:28 AM
Modular exponentiation in large numbers is computationally intensive. One effective way to perform this operation is to use Montgomery's exponentiation in the Waste Number System (RNS). This paper presents an algorithmic and architectural study of this exponentiation approach. From the algorithmic point of view, the new and avant-garde opportunities that come from the reorganization of operations and precomputations are considered. From the architectural point of view, the design opportunities offered by well-known computer arithmetic techniques are studied, with the aim of developing an efficient arithmetic cell architecture. In addition, since the use of efficient RNS bases with a low Hamming weight is being considered with increasing interest, four additional cell architectures adapted specifically to these bases are developed and the balance between benefits and drawbacks carefully studied. A comprehensive comparison is presented between all algorithmic approaches and cell architectures considered, with the aim of providing the reader with a broad view of the Montgomery exponential opportunities in RNS.