| 摘要 |
PURPOSE:To execute multiplication remainder calculation useful in a cipher, etc., at high speed through the use of small-scale hardware and a small number of execution steps. CONSTITUTION:A multiplier is stored in registers 101, 102, and a multiplicand is stored in the registers 106, 107, and a value obtained by subtracting a divisor from the n-th power of '2' is stored in the register 105, and '0' is stored in the registers 106, 107. A bit extracting means 108 extracts the bits of the registers 101, 102 from an (n-1)-th bit up to a 0-th bit at every first to n-th step, and outputs the sum of two bits. Multiplying means 113, 114 output the value obtained by multiplying the sum of two bits by the registers 103, 104 respectively, and delay adders 109, 110 output parts 121, 122 higher than the (n-3)-th bit to an approximate division circuit 116 and the delay adder 111. A correction circuit 112 corrects input from the delay adder 111, and writes it in the registers 106, 107. The operation is repeated (n+5)-times from the first step up to the (n+5)-th step. |
