Patent ID: 8458242

Claim:
A modular multiplier apparatus for obtaining a quotient q i = - 1 M × S ⁢ i - 1 ⁢ ⁢ mod ⁢ ⁢ 2 k and a result S i = S ⁢ i - 1 + B i ⁢ A + q i - 1 ⁢ M 2 k of an arithmetic operation of modular multiplication by using a modulus satisfying a condition −M<A, B<M where B = ∑ i = 0 n - 1 ⁢ ⁢ B i ⁢ 2 ki ⁢ ⁢ and ⁢ ⁢ ⁢ B i ⁢ ∈ { 0 , 1 , ⋯ ⁢ , ( 2 k - 1 ) } and two arbitrary constants A, B, the modular multiplier apparatus comprising: a reduction unit for obtaining a short path carry (SPC) included when a result S i , of a modular arithmetic operation is obtained at an ith loop, by using a medium calculation result SPP at an (i−1)th loop; a carry predictor for predicting a long path carry (LPC) included when the result of the modular arithmetic operation is obtained at the ith loop, by using the medium calculation result SPP at the (i−1)th loop; and an accumulator for accumulating the result S i , of the modular arithmetic operation obtained at the ith loop to a result S i-1 of the modular arithmetic operation obtained at the (i−1)th loop by using the SPC and the LPC, wherein the medium calculation result SPP is obtained by adding the result S i-1 of the modular arithmetic operation obtained at the (i−1)th loop and a partial product B i A of the two constants obtained at the ith loop, and the SPC is obtained by the sum of a carry C k-1 , a sum (S k-1 ), and a medium calculation result SPP k-1 with respect to a lower k-1 bit on which the reduction is performed.