To speedily retrieve a stored value required for power residue calculation from exponential coefficients by improving the efficiency of table generation.

In order to input the base value of the power residue calculation, a plurality of the exponential coefficients, a modulo and a table side variable to output modulo by the base and the respective exponential coefficients, a table preparing step prepares a table by inputting a making-up value, the table size variable and the modulo to obtain a maximum exponent by the table size variable, calculating all the power residue with an integer equal to or smaller than the maximum exponent as the exponential coefficient and with the making-up value as the base to store them in a table, outputting the modulo exponentiation with the maximum exponent as the exponential coefficient as the making-up value and inputting the table size variable, the modulo and the making-up value with the initial value of the making-up value as a base value to output the making up value, and a table using step inputs the exponential coefficients, the table size variable, the modulo and the table, equally divides the bit expression of the exponential coefficients into the bit strings of a length fixed by the table size variable, chooses the corresponding stored value from the table by using the respective bit strings, calculates the power residue as the product of the housed values and outputs it.