PURPOSE: To speed up calculation of the residue of a power of a number which is used to decide and generate prime numbers and calculate an open key cipher.

CONSTITUTION: Registers 201, 202, and 203 store respective data on the exponent (e), the operand (m), and the modulus (n). A subtraction part 204 finds n-m and outputs its subtraction result m'. A power residue arithmetic part 205 performs the power residue operation of (m')e mod n based upon the exponent (e) and the modulus (n) and outputs the result c' of the operation. A subtraction part 206 finds n-c' and outputs its subtraction result (c). A parity decision part 207 decides whether the exponent (e) is even or odd. An arithmetic result selection part 208 selects the output c' of the power residue arithmetic part 205 when (e) is even or the output (c) of the subtraction part 206 when it is odd, and outputs the selected output to an output line 209.