PAIRING ARITHMETIC UNIT, PAIRING ARITHMETIC METHOD AND PAIRING ARITHMETIC PROGRAM

摘要

PROBLEM TO BE SOLVED: To solve the problem, wherein a pairing arithmetic speed is slow, since the amount of operation required for pairing arithmetic is much larger than that of a regular ellipse arithmetic operation. SOLUTION: In the invention, high speed is achieved by using a characteristic of a finite field. Assuming r as an element on the finite field GF(pk/2) and f as an element on the finite field GF(pk) which is calculated by Miller algorithm, calculation is performed using the algorithm in which a calculating amount is less than Miller algorithm for imaging to an element f' on the finite field GF(pk) which satisfies f'=rf. Instead of calculating an inverse element, p to the k-th power of a multiplying element is calculated as a quasi inverse element. The polynomial expansion of multiplications of elements of GF(pk) in which the calculation amount is large, is performed by using the quasi inverse elements. High speed is achieved by calculating terms beforehand, in which calculation amount is large, as a common term of a repeated calculation, by performing the polynomial expansion. COPYRIGHT: (C)2007,JPO&INPIT