| 摘要 |
The modular multiplication apparatus includes a residue calculating unit, a multiplier division unit, a partial product calculation unit, an accumulation unit, a correction unit, and a control unit. The residue calculating unit recurrently calculates intermediate values in sequence. The residue calculating unit obtains the multiplicand as the intermediate value first time, and at the second time and after, calculates residues or congruent values of the modulo P multiplication of the intermediate values being preceding intermediate values left-shifted s bits. The multiplier division unit divides the multiplier into a plurality of s-bit partial multipliers in order from lower bits. The partial product calculation unit calculates partial products of intermediate values and partial multipliers in sequence. The accumulation unit and the correction unit accumulate the partial products while correcting them under the control of the control unit. The residue calculating unit includes a table unit. The table unit prestores residues of modulo p multiplications of (m-bit value) *2k, where the m-bit values respectively correspond to values from decimal values 0 to 2m-1. The residue calculating unit refers to the table unit to read out a residue corresponding to higher m bits adjacent to the lower k bits of the left-shifted intermediate value. The residue calculating unit calculates a residue or a congruent value of modulo p multiplications of the left-shifted intermediate value by adding up the read-out residue and the lower k bits.
|
