DEVICE AND METHOD FOR ARITHMETIC OPERATION ON ELLIPTIC CURVE AND RECORDING MEDIUM WHICH RECORDS THE ARITHMETIC OPERATION PROGRAM

摘要

PROBLEM TO BE SOLVED: To provide an arithmetic operation method on an elliptic curve in which elliptic k multiplying operations that integer-multiple a first point being affine coordinate-displayed on an elliptic curve of an element body to a second point being affine coordinate-displayed on the same curve is processed at a high speed without degrading precision. SOLUTION: The elliptic adding operations conducted in elliptic k multiplying operations are computed in a form in which an affine coordinate system and a Jacobian coordinate system are mixed in a Montgomery operational region. Thus, the number of executions of multiplication remainder operation is reduced and the processing of elliptic k multiplying operations is speeded up.