REMAINDER CALCULATION METHOD, MULTIPLICATION REMAINDER CALCULATION METHOD, REMAINDER CALCULATOR, MULTIPLICATION REMAINDER CALCULATOR AND RECORDING MEDIUM

摘要

PROBLEM TO BE SOLVED: To simplify a remainder operation and a multiplication remainder calculation based on a Montgomery method and to reduce calculation quantity much more than heretofore. ;SOLUTION: In this remainder calculation method and this multiplication remainder calculation method based on a Montgomery method, a number expressed by N=c2d±1 as a divisor N is used, and a step for adding the product of the value y0 of the lowest digit of a remainder number Y and (c) to a lower d-th bit in the remainder number Y and a step setting a part other than the lowest digit of the addition result to be the next remainder number are repeated.;COPYRIGHT: (C)2000,JPO