To provide an exponentiation remainder computing element which has a small circuit scale and enables high-speed processing.

The exponentiation remainder computing element includes an internal bus 115 for data exchange between an e-register 102 which holds a key-e and a Y register 103 which holds a multiplier Y of Montgomery transform, an N register 104 which holds a key N, a B2N register 105 which holds a value of 2B+N calculated in operation of Montgomery transform, an X register 106 which holds a plain text X, an internal bus 116 for data exchange between an operation circuit 107 which performs operation for encrypting and decrypting and a P register 108 which holds an operation result P, an exponentiation remainder control circuit 109 functions as a state machine for execution of exponentiation remainder operation, and a Montgomery multiplication remainder and remainder control circuit 110 which functions as a state machine for execution of Montgomery multiplication remainder operation and remainder operation.