配对运算装置、配对运算方法、以及配对运算程序

摘要

本发明提供能够进行高速配对运算的配对运算装置、配对运算方法、以及配对运算程序。具有以下部件：曲线方程式由y2＝x3+ax+b，a∈Fp，b∈Fp给出，嵌入次数为k，以Fpk为定义域的能够配对的椭圆曲线上的有理点构成的加法群记为E，素数位数r的有理点的集合记为E[r]，以φp为Frobenius自同态，将位数r和Frobenius自同态φp的踪迹t作为整数变量x的函数，计算有理函数fx，Q(S)的运算部件；计算通过规定的有理点的直线的有理点S(xs，ys)上的值的运算部件；利用这些运算部件的运算结果对有理函数f′x，Q(S)进行计算的运算部件；以及利用所述有理函数f′x，Q(S)作为式(1)进行配对运算的运算部件。