Remainder calculating method, modular-multiplication method, remainder calculating apparatus, modular-multiplication apparatus and recording medium

摘要

In a remainder calculating method and a modular-multiplication method on the basis of a Montgomery method, a number expressed by N (N=c2^d±1) is used as a divisor N. In order to calculate a remainder in the case of dividing a dividend Y by a divisor N on the basis of a Montgomery method, a number expressed by a condition of N=c2^d−1 is used as the divisor N, and the following steps are repeatedly carried out; the steps includes: a step of adding a product of a least digit value y_o of the dividend Y and c to a lower d-bit position of the dividend Y; and a step of setting a portion excluding the least digit of the additive result as a next dividend.