METHOD FOR SCALAR MULTIPLICATION, METHOD FOR EXPONENTIATION, RECORDING MEDIUM RECORDING SCALAR MULTIPLICATION PROGRAM, RECORDING MEDIUM RECORDING EXPONENTIATION PROGRAM

摘要

There are provided a computation method for scalar multiplication or exponentiation and a scalar multiplication program or an exponentiation program which can compute at high speed. In the computation method for scalar multiplication and the scalar multiplication program for computing scalar multiplication by n of a rational point Q in G with respect to a non-negative integer n using an electronic computer, sinceφq(Q)=[q]Q=[t−1]Q holds true with respect to the rational point Q in G, (t−1)-adic expansion of a scalar n is performed and a Frobenius endomorphismφq with respect to a rational point is used in place of t−1. Further, in the computation method for exponentiation and the exponentiation program for computing exponentiation of an element A in H to the power of n with respect to a non-negative integer n using an electronic computer, letting a difference of q and r be s=q−r, sinceφq(A)=Aq=As holds true with respect to the non-zero element A in H, s-adic expansion of an exponent n is performed and a Frobenius endomorphismφq with respect to an element is used in place of s.