| 摘要 |
PURPOSE: A high speed remainder calculation method as to a specific big integer for a public key cryptosystem is provided, which performs a high speed remainder calculation using only addition and subtraction. CONSTITUTION: According to the method, a remainder of a (a) big integer dividend(d) is copied to a big integer register(r)(S701). An amplitude of the above register and an amplitude of a big integer divisor(m) are compared(S702). When the big integer divisor is larger than the register value, a maximum word, which is not zero, is scanned in the register where the big integer dividend is copied(S704). A new corresponding word value and a carry(c) to be propagated to an upper word are calculated by adding the maximum word and the corresponding word value(S705). A new corresponding word value and a carry(c) are calculated by adding the corresponding word value and the above carry to a value obtained by shifting the maximum word value to the left by b(S706). A new corresponding word value and a carry(c) to be added to the upper word are calculated by adding the corresponding word value and the carry to a value obtained by shifting the maximum word to the right by b(S707). Corresponding word values and carries(c) are calculated by adding the calculated carry values to the upper words continuously and then a final big integer register(r) is calculated. When the register value(r) is smaller than the big integer divisor, the register value(r) is output as a remainder as to m value. When the big integer register value(r) is larger than the big integer divisor, the above steps are repeated.
|
