MODULO OPERATION METHOD AND APPARATUS FOR SAME

摘要

The present invention provides a modulo operation method. The modulo operation method, in a case where the square of a divisor N is greater than or equal to a dividend C, includes: determining the number of computation stages n satisfying 2 n < N ‰¤ 2 n+1 ; performing an initialization operation by initializing a constant a to the smallest integer greater than or equal to half of N; performing a first operation by subtracting, when C is greater than or equal to N·a (product of N and a ) , the value of C by the value of N·a; and performing a second operation by assigning the smallest integer greater than or equal to half of a to the value of a, wherein the value of C is output as the result of modulo operation after the first operation and the second operation are repeated n times. In the first operation, when C is less than N·a, the value of C is unchanged. In the modulo operation method and apparatus of the present invention, the amount of computation in a modulo operation or division operation does not increase in linear proportion to the magnitude of the divisor N but increases in proportion to log N. As a result, the total amount of computation decreases and computation speed increases.