The value of α is used as private key sk, and therefore it needs to ensure that the value of α cannot be obtained or is difficult to obtain, to ensure security of α. As described above, number N included in the public key is the product of prime numbers P and Q, and the values of prime numbers P and Q are difficult to obtain. Therefore, a can be calculated based on the values of prime numbers P and Q. For example, intermediate parameters p and q can be used. Intermediate parameters p and q are prime numbers, p|P?1, and q|Q?1 (in other words, p is divisible by P?1, and q is divisible by Q?1). In this case, α=pq can be set. In addition, β=(P?1)(Q?1)/(4pq) can be set, and gcd(α, β)=1 is satisfied. In this case, α·β=(P?1)(Q?1)/4=|QRN| can be determined. It can be seen that |QRNα|=β with reference to |QRNα||QRNβ|=|QRN| and |QRNβ|=α.