MONTGOMERY MULTIPLICATION METHOD FOR PERFORMING FINAL MODULAR REDUCTION WITHOUT COMPARISON OPERATION AND MONTGOMERY MULTIPLIER

摘要

A Montgomery multiplier includes a partial product computing unit for multiplying a multiplicand and a multiplier; a modulus reduction computing unit for performing a multiplication of a modulus and a quotient that reflects a quotient sign; an accumulation unit for accumulating in a intermediate value an output value of the partial product computing unit and an output value of the modulus reduction computing unit from a previous cycle; a quotient computing unit for receiving an accumulation value of the accumulation unit during a current cycle and calculating a quotient sign to be used during a next cycle; and a quotient sign determination unit for determining a quotient sign to be used during a next cycle from the multiplicand, the multiplier and the quotient.

主权项

1. A Montgomery multiplier apparatus, comprising:
a partial product computing unit configured to multiply a multiplicand and a multiplier; a modulus reduction computing unit configured to multiply a modulus and a quotient with a quotient sign; an accumulation unit configured to accumulate in a intermediate value an output value of the partial product computing unit and an output value of the modulus reduction computing unit from a previous cycle; a quotient computing unit configured to receive an accumulation value of the accumulation unit during a current cycle and to calculate a quotient sign to be used during a next cycle; and a quotient sign determination unit configured to determine the quotient sign to be used during the next cycle from the multiplicand, the multiplier and the quotient.