Browsing by Subject "Hardware"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    A General Digit-Serial Architecture for Montgomery Modular Multiplication
    (Institute of Electrical and Electronics Engineers Inc., 2017) Erdem S.S.; Yanik T.; Çelebi A.
    The Montgomery algorithm is a fast modular multiplication method frequently used in cryptographic applications. This paper investigates the digit-serial implementations of the Montgomery algorithm for large integers. A detailed analysis is given and a tight upper bound is presented for the intermediate results obtained during the digit-serial computation. Based on this analysis, an efficient digit-serial Montgomery modular multiplier architecture using carry save adders is proposed and its complexity is presented. In this architecture, pipelined carry select adders are used to perform two final tasks: adding carry save vectors representing the modular product and subtracting the modulus from this addition, if further reduction is needed. The proposed architecture can be designed for any digit size δ and modulus θ. This paper also presents logic formulas for the bits of the precomputation -θ-1 mod 2δ used in the Montgomery algorithm for δ ≤ 8. Finally, evaluation of the proposed architecture on Virtex 7 FPGAs is presented. © 2017 IEEE.