PURPOSE: To secure high safety and shorten the time required for arithmetic by making a value that an auxiliary device calculates not depend upon secret information that a main device holds.
CONSTITUTION: The request calculating device performs power remainder calculation Mdmodn. the main device 1 has a power exponent (d) as the characteristic secret information and holds all coefficients di obtained by expanding the power exponent by (b)-array notation d=Σdibi based upon a positive integer b larger than 2 as a cardinal number, and the auxiliary device 2 calculates plural values by raising M as a specific base to β th power repeatedly and obtaining a remainder with (n) as a specific divisor as conversion which depends upon a specific integer β exactly dividing the cardinal number and also depends on neither (d) nor the coefficients di. Then the calculation results are sent to the main device 1, which obtains a power residue calculation result by conversion which depends upon the coefficients di and (n) held in its device 1 by using the calculation values. The secrecy regarding the (d) never slips out of the main device 1.
SHINPO ATSUSHI