Patent ID: 9164732
Filing Date: 2015-10-20
Classification: G06F,H04L

Abstract:
1. A modular multiplier comprising at least one central processing unit configured to execute instructions to implement: a partial multiplication unit configured to multiply a multiplier and a multiplicand bit; a modulus multiplication unit configured to multiply a modulus and a transformed quotient bit; an accumulator configured to receive a previous accumulated value and output values of the partial multiplication unit and the modulus multiplication unit, and calculate an accumulated value according to a Montgomery algorithm; a register configured to store the accumulated value calculated by the accumulator; a first recoding unit configured to transform the previous accumulated value by adding a recoding constant to the redundant-form previous accumulated value, and recode the transformed previous accumulated value; a quotient generator configured to generate a redundant-form quotient using the previous accumulated value; and a second recoding unit configured to transform the redundant-form quotient by adding a recoding constant thereto, and recode the transformed quotient, wherein the transformed quotient bit has a value of the output of the second recoding unit.