FINITE FIELD CALCULATION APPARATUS, FINITE FILED CALCULATION METHOD, PROGRAM, AND RECORDING MEDIUM

摘要

A calculation   i=0 N-1 e(R(i, 0), ..., R(i, K-1)) where a calculation of K elements R(i, k) ˆˆ GF(p m ) of a finite field GF(p m ) over a finite field is expressed as e(R(i, 0), ..., R(i, K-1)) is efficiently performed. Polynomials poly(R(i, 0), ..., R(i, K-1)) that express a d-th-order extension field of the finite field GF(p m ), which are obtained by the calculations e(R(i, 0), ..., R(i, K-1)) for different values of i, are multiplied by each other, and a cumulative multiplication of the products is performed, for example. The polynomial poly(R(i, 0), ..., R(i, K-1)) is a mapping from the input elements of the finite field GF(p m ), and the coefficients of at least some of the terms thereof are 0. The same process is performed for different sets of values of i, and the calculation   i=0 N-1 e(R(i, 0), ..., R(i, K-1)) is performed using the result.