Patent ID: 6910058

Claim:
An elliptic curve arithmetic operation device for performing one of an addition and a doubling on an elliptic curve E: y{2=f(x) on a residue class ring of polynomials in two variables α and β, moduli of the residue class ring being polynomials β{2−f(α) and h(α), where f(α)=α{3+aα+b, a and b are constants, and h(α) is a polynomial in the variable α, the elliptic curve arithmetic operation device comprising: acquiring means for acquiring affine coordinates of at least one point on the elliptic curve E and operation information indicating one of the addition and the doubling, from an external source; transforming means for performing a coordinate transformation on the acquired affine coordinates to generate Jacobian coordinates, the coordinate transformation being transforming affine coordinates (φ(α), β×φ,(α)) of a given point on the elliptic curve E using polynomials X (α)= f (α)×φ(α) Y (α)= f (α){2×φ(α) Z (α)=1 into Jacobian coordinates (X(α):Y(α):β×Z(α)), φ(α) and φ(α) being polynomials; and operating means for performing one of the addition and the doubling indicated by the acquired operation information, on the generated Jacobian coordinates to obtain Jacobian coordinates of a point on the elliptic curve E.