FINAL EXPONENTIATION CALCULATION DEVICE, PAIRING CALCULATION DEVICE, CODE PROCESSING UNIT, FINAL EXPONENTIATION CALCULATION METHOD, AND FINAL EXPONENTIATION CALCULATION PROGRAM

摘要

According to the present invention, a decomposition unit (211) decomposes, with respect to a final exponentiation calculation part of a pairing calculation in an elliptic curve expressed with a polynomial r(x), a polynomial p(x), a polynomial t(x), an embedded degree k, and an integer u, exponent parts of the polynomials into easy parts and hard parts. A factoring unit (212) factors the hard parts by using a homogeneous cyclotomic polynomial Ψn(x, p) An exponentiation calculation unit (22) calculates final exponentiation by using the easy parts and the factored hard parts.