Cryptology ePrint Archive: Report 2007/179

New Fast Algorithms for Arithmetic on Elliptic Curves over Fields of Characteristic Three

Kwang Ho Kim and So In Kim and Ju Song Choe

Abstract: In previous works on ECC(Elliptic Curve Cryptography), the case of characteristic three has been considered relatively less than cases of fields of even characteristic and large prime fields. To the best of our knowledge, for point multiplication on ordinary elliptic curves over fields of characteristic three the most efficient way is known as one shown by N.P. Smart et al.(cf. [2]). In first portion of this paper we propose new fast algorithms for arithmetic on Hessian elliptic curves over finite field of characteristic three, which reduce costs of a doubling and a mixed point addition from 3M+3C and 10M (cf. [2]) to 3M+2C and 9M+1C, respectively. These algorithms can realize fast point multiplication nearly comparable with the case of even characteristic, on ordinary elliptic curves over finite field of characteristic three. In next portion we propose a kind of projective coordinates we call ML coordinates and new algorithms for arithmetic on Weierstrass elliptic curve in it, which reduce costs of a tripling and a mixed point addition from 7M+4C and 10M+2C (cf. [2]) to 6M+6C and 8M+2C, respectively. In conclusion, we can say that ternary elliptic curves are another alternative to existing technology for elliptic curve cryptosystems.

Category / Keywords: implementation / characteristic three elliptic curves, ordinary elliptic curve, point addition, point doubling, point tripling, Hessian form, Weierstrass form

Date: received 12 May 2007, last revised 12 May 2007

Contact author: kimkhhj1980 at yahoo com cn

Available format(s): PDF | BibTeX Citation

Note: Names of Coauthors was added.

Version: 20070520:130030 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]