MODULO OPERATION METHOD AND APPARATUS FOR SAME

摘要

The present invention provides a modulo operation method, for the event the square of a divisor is larger than or equal to a dividend, wherein said method comprises: a step of determining the number of arithmetic operation stages; an initializing step of setting the initial value of a constant to the smallest integer from among the values equal to or larger than half the value of the divisor; a first arithmetic operation step of updating the dividend with the value obtained by subtracting the value obtained by multiplying the divisor and the constant from the dividend, when the dividend is larger than or equal to the value obtained by multiplying the divisor and the constant; and a second arithmetic operation step of updating the constant with the smallest integer from among the values equal to or larger than half the value of the constant. The first arithmetic operation step and the second arithmetic operation step are repeated by the number of the arithmetic operation stages, in order to output the dividend as the result of the modulo operation. The modulo operation method and an apparatus for same according to the present invention enable the computational complexity of the modulo operation or dividing operation to increase in proportion to the logarithm of the divisor instead of being linearly increased in proportion to the size of the divisor, thus resulting in the overall reduction in the computational complexity and an increase in computational speed.