METHOD AND APPARATUS FOR MODULO N CALCULATION

摘要

An apparatus and a method for modulo N operation are provided to perform efficiently a modulo 3 for an arbitrary integer N by adding a logical circuit in accordance with twice AND operations for outputting a modulo operation result more rapidly. A method for modulo N operation includes the following several steps. An apparatus for modulo N operation checks whether a specifically inputted integer value N is for an M1 bit operation and performs an AND operation for lower M1 bits and a binary number of 0101(S200,S202). The apparatus determines an AND operation result and changes output register values according to the result(S204). If the result is a binary number of 0101, the apparatus adds 2 to an output register(S206), if 0, adds 0 to the output register(S216) and if neither 0101 nor 0, adds 1 to the output register(S218). Then, the apparatus performs an AND operation for the lower 4 bits and a binary number of 1010(S208), determines an AND operation result(S210), and changes the output register values according to the result. If the result is a binary number of 1010, the apparatus adds 4 to the output register(S212), if 0, adds 0 to the output register, and if neither 1010 nor 0, adds 2 to the output register(S222). Then, the apparatus performs a 4 bit shift right for the inputted integer N(S214). Then, the apparatus abandons corresponding bits, and repeats the steps of S202 to S222. In case of a 4*M bit operation, the apparatus performs the shift right M times(S226), and checks whether the result value is lower and equal to 3(S228). The apparatus repeats the steps of S228 to S248 until the result value is 3.