To fast calculate a remainder of n of the C-th power of B.
This circuit has a 1st circuit 100, which calculates a remainder to module n of B, holds a result B1, shifts a holding value, calculates a value to be congru to modulus n and repeats processing to hold a result, a 2nd circuit 110 which accumulates calculation results of the 1st circuit when a prescribed bit of a 1st register 120 that makes an initial value B1 is one and a 3rd circuit 150 which accumulates results of the 1st circuit when the output volue of a C output circuit 140 is one and the prescribed bit of a 2nd register 160 whose initial value is one is one. The prescribed bits of the 1st and 2nd registers are shifted in the direction from the LSB of a stored value to MSB, a value to be congruous to modulus n of the accumulated result of the 2nd circuit a method and is congruous is made the holding value of the 1st circuit and stored in the 1st register when the processing of the MSB of a value that is stored by the 1st register is finished, the output of a C output circuit is changed to a value that is shifted in the direction from the LSB of C to MSB, and a value to be congruous to modulus n of the accumulated results of the 3rd circuit is stored in the 2nd register when the output value of the C output circuit is one.
SATO AKASHI
NIIJIMA HIDETO
Next Patent: LAUDABLE HARDWARE SUPPORTING METHOD