Patent ID: 7472154
Filing Date: 2008-12-30
Classification: G06F

Abstract:
1. A multiplication remainder calculator which shifts inferior m bits of a provisional remainder u by continuously connecting m stages of processing circuits which execute addition of a modulus N and one-bit shift, and calculates a Montgomery product of a number to be multiplied A and a multiplier factor B by repeating this processing, in a circuit which adds a partial product {Σ(Aj*B)*2^j (j=0, , , m−1)} to the provisional remainder u by using a value of inferior m bits (m is an integer not less than 2) of the number to be multiplied A, and the multiplier factor B, wherein a multiple number of the multiplier factor B is calculated by inhibiting one-bit shift of the processing circuits, the multiplication remainder calculator comprising: a temporary register, connected to the processing circuits, that stores a feedback value output from the processing circuits and that generates a new provisional value; a register that stores the multiplier factor B; an m-bit right shift register that stores the number to be multiplied A; a multiplexer, connected to the register and the m-bit right shift register, that generates a multiplexed signal based on the inferior m bits of the number to be multiplied A, and the multiplier factor B; and an adder, connected to the multiplexer and the temporary register, that adds the new provisional value and the multiplexed signal to generate an addition signal, and that provides the addition signal to the processing circuits for addition to the modulus N.