Patent ID: 8856200

Claim:
An exponentiation calculation apparatus comprising: a computer having a dividing unit, a first calculating unit, a second calculating unit, a third calculating unit, and a coupling unit that are processed by the computer so that: the dividing unit divides an input value as an element of a 2rth degree extension field and as an element of a torus T 2 (Fq^r) (where r is an odd prime, q is a power of a prime, Fq is a finite field with q elements, and Fq^r is an rth degree extension field of the finite field Fq) into a first element of the rth degree extension field with r values and a second element of the rth degree extension field with r values; the first calculating unit calculates only some multiplications on a base field based only on the r values of the first element and some multiplications on a base field based only on the r values of the second element, in order to obtain a plurality of multiplication results as bases for a calculation of a third element of the rth degree extension field with r values, wherein the third element is first half portion of the (q+1)th power of the input value, and wherein the plurality of multiplication results consist only of the some multiplications on a base field based only on the r values of the first element and the some multiplications on a base field based only on the r values of the second element; the second calculating unit calculates the third element based only on the plurality of multiplication results; the third calculating unit calculates, in parallel to calculations by the first and second calculating units, a fourth element of the rth degree extension field with r values by an Fq^r multiplication based on the first element and the second element, wherein the fourth element is last half portion of the (q+1)th power of the input value; and the coupling unit couples the third element with the fourth element to obtain the (q+1)th power of the input value.