INVERSE ELEMENT CALCULATION DEVICE, INVERSE ELEMENT CALCULATION METHOD, AND INVERSE ELEMENT CALCULATION PROGRAM

摘要

PROBLEM TO BE SOLVED: To provide a method for calculating, at high speed, an inverse element of a field which is the base of elliptic cipher, code or the like.;SOLUTION: In the inverse element calculation method, when there are an arbitrary base field and its extended field M in an arbitrary order, a field L which is extended by a q-th order cyclotomic polynomial (q is a prime number obtained by adding 1 to an integral multiple of the above order) is considered, and the field M is considered as a medium field of the extended field L. In the above manner, Frobenius mapping in M is obtained naturally from Frobenius mapping in L. The quantity of calculation required for the Frobenius mapping in L is very small. Also, when obtaining the inverse element, frequency of using multiplication in M is reduced by repeating calculation of products and norms of all the conjugate elements in relation to a medium field which is on a certain medium field and has less members. By this operation, an extended field in an arbitrary order can be obtained and, as a result, the inverse element can be obtained at high speed.;COPYRIGHT: (C)2004,JPO&NCIPI