In scalar multiplication method using a Montgomery-type elliptic curve, a high-speed elliptic curve calculation device effectively uses a table that stores coordinates of certain scalar multiple points like points multiplied by exponentiation of two to a certain point G and so forth. The elliptic curve calculation device receives an arbitrary integer k of n bits and outputs scalar-multiplied points against a point G on a Montgomery-type elliptic curve E on a finite field F that is given in advance. The elliptic curve calculation device includes a calculation procedure generation unit that generates a calculation procedure that addition on the elliptic curve E with either of G, 2 *G, 22*G., . . . , 2n−1*G as the first addition element is repeated and a scalar multiplication unit that calculates the scalar-multiplied points k*G by repeating addition on the elliptic curve E, referring to a table memorizing unit that stores values (coordinates) of exponentiation of two against the point G and complying with the generated calculation procedure.