METHOD AND DEVICE FOR CALCULATION ON ELLIPTIC CURVE, AND RECORDING MEDIUM WITH CALCULATION PROGRAM RECORDED THEREON

摘要

PROBLEM TO BE SOLVED: To provide an arithmetic calculation method on an elliptic curve by which an elliptic k-multiple calculation for calculating an integral multiple of a first point expressed in the affine coordinates on an elliptic curve of a prime field to a second point expressed in the affine coordinates is speedily processed without causing decrease in accuracy. SOLUTION: According to this invention, an elliptic summing calculation performed during the elliptic k-multiple calculation is carried out in a form of letting the affine coordinate system and a homogenous coordinate system exist together in a Montgomery arithmetic domain. In such a manner, the number of executing a multiplication residue calculation is reduced, and the elliptic k-multiple calculation is processed speedier.