Then, values of hN mod N2, (hN mod N2)2j, . . . , and (hN mod N2)2j[(i/j)?1] can be pre-calculated, and then after actually selected random number r is divided, further calculation is performed with reference to the pre-calculated values. Alternatively, the value of each of numerical segments r_0, r_1, . . . , and r_[(i/j)?1] obtained after random number r is divided belongs to [0, 2j?1], and therefore values of (hN mod N2)0 to (hN mod N2)2j?1, [(hN mod N2)2j]0 to [(hN mod N2)2j]2j?1, . . . , and [(hN mod N2)2j[(i/j)?1]]0 to [(hN mod N2)2j[(i/j)?1]]2j?1 can be pre-calculated. In this case, after actually selected random number r is divided, for example, when i/j numerical segments ru are obtained through division and u∈[0, (i/j)?1], corresponding pre-calculated values can be selected based on values of the numerical segments, and then without involving modular exponentiation, these values are multiplied to calculate (hN mod N2)r or to further process (hN mod N2)r into [(hN mod N2)r mod N2], thereby improving calculation efficiency.
