Patent ID: 7925893

Claim:
A modular exponentiation operation apparatus comprising: a storing unit storing therein an operand S, which is a natural number; a reading unit that reads the operand S from the storing unit; a selecting unit that selects prime numbers expressed by ∑ m = 1 a - 1 ⁢ C m - 1 a - 1 where a is a natural number being 2 or larger and m is a variable natural number being any number from 1 through a−1, from among 2 a −2 prime numbers that are mutually different; and a calculating unit that performs a modular exponentiation operation over a finite field, the modular exponentiation operation seeking a value expressed by S′=S 1/P mod N where N is a product of a prime number p and a prime number q, the prime numbers p and q are larger than a predetermined value, and P is a product of all of the prime numbers selected by the selecting unit, wherein the selecting unit includes: a prime number storing subunit storing therein the 2 a −2 prime numbers that are in one-to-one correspondence with all possible combinations in which a number of branches equal to all of the numbers from 1 through (a−1) are selected from among a branches each connecting to one of nodes in an a-ary tree; and a branch obtaining subunit that obtains branch information specifying one branch out of the a branches; and a prime number selecting subunit that selects all prime numbers being in correspondence with combinations that each include the branch specified in the branch information, from among the 2 a −2 prime numbers stored in the prime number storing subunit, and wherein the modular exponentiation operation apparatus further comprises: a writing unit that overwrites the operand S stored in the storing unit with the calculated value S′ such that the calculated value S′ is stored as the operand S; and a repetition control unit that controls the branch obtaining subunit, the prime number selecting subunit, the calculating unit, and the writing unit so that, on each of branches positioned on a path from a root to a leaf in the a-ary tree, starting from the root and ending with the leaf, the obtainment of branch information specifying the branch, the selection of all prime numbers being in correspondence with combinations that each include the specified branch, the modular exponentiation operation based on S′=S 1/P mod N, and the writing of the calculated value S′ into the storing unit are repeatedly performed.