Scalar multiplication operating program and exponentiation of the calculation program of

摘要

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)=A q =A s 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.