REDC (A*B) is calculated for the values A and B by using a Montgomery's algorithm REDC. The part related to the A*B is performed by the three-input two-output product-sum calculation circuit. One digit ai of the value A, one digit bj of the value B and a carry value c1 are input to the product-sum calculation circuit, and ai*bj+c1 is calculated thereat. The higher-order digit of the r-adic two-digit of the calculation result is used as the carry value c1, and the lower digit is used for a later calculation. Further, one digit ni of a modulo N for the REDC, a predetermined value m and a carry value c2 are input into the product-sum calculation circuit, and n*ni+c2 is calculated thereat. The higher-order digit is used as the carry value c2, and the lower digit is used for a later calculation.