| 摘要 |
PROBLEM TO BE SOLVED: To provide a device for power residue calculation which can execute calculation more efficiently. SOLUTION: With respect to a cipher text C, residue system expressions based on the first and second bases (all integers included in both bases are relatively prime and B>p, q, A*B>C is true where A is the product of all integers of the first base and B is that of the second base) are used to obtain a plain text m=Cd mod p*q. With respect to p, a residue system expression of (Cpdp)*B mod p or a value obtained by adding p to it is obtained on the basis of a residue system expression of C mod p and d mod (p-1); and with respect to q, the same operation is performed (123 and 124). A residue system expression of m' which is the element of the modulus p*q and is congruent with Cd is obtained on the basis of both obtained residue system expressions (123 to 126). The residue system expression of m' is converted to a binary expression (128). The obtained value smaller than p*q or the value smaller than p*q, which is obtained by subtracting p*q from m' larger than p*q a prescribed number of times is outputted as the plain text m (130).
|
