Scalar point multiplication using redundant recoding in elliptic curve cryptosystems

Scalar multiplication is the backbone operation in elliptic curve cryptosystems, and its implementation algorithms are expected to exhibit high performance. We introduce a point quadruple scalar operation in an elliptic curve cryptosystem to be used in a novel scalar point multiplication algorithm, named quad-and-add. Expressions derived by the algorithm were applied to a real prototype cryptosystem and evaluated at both C language and HDL level. Point quadruple operation with the proposed quad-and-add algorithm were twice as fast as the traditional double-and-add algorithm when we fixed the radix number at four.