SCALAR MULTIPLICATION METHOD, RAISING METHOD, RECORDING MEDIUM WHERE SCALAR MULTIPLICATION PROGRAM IS RECORDED, AND RECORDING MEDIUM WHERE RAISING METHOD PROGRAM IS RECORDED

摘要

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.