According to an aspect of the invention, Montgomery arithmetic can be achieved while omitting division in an input stage. That is, the aspect of the invention is configured to obtain a Montgomery transform result m' (=mR mod p) of n-bit from an input m of 2n-bit without using the division, with using Montgomery reduction and Montgomery multiplication instead of conventional mod arithmetic and the Montgomery transform. Accordingly, Montgomery arithmetic can be achieved while omitting the division in the input stage.