Patent ID: 6430588
Filing Date: 2002-08-06
Classification: G06F

Abstract:
An elliptic curve multiplication apparatus for calculating m-multiplication of GF(qk)-rational point P over an elliptic curve E/GF(q) defined over a finite field, said apparatus comprising:input means for inputting thereinto said GF(qk)-rational point P, a Frobenius map &phgr; defined over said elliptic curve E/GF(q), an integer k, and a prime q exceeding 3 or a power of said prime; base-&phgr; expansion means for calculating integers r and ci, where 0&lE;ii&lE;q, which satisfy m=&Sum;i=0r-1&it;â€ƒ&it;ci&it;Ï†i(1a)using said Frobenius map &phgr; dependent on said elliptic curve E/GF(q);Pi generation means supplied with said GF(qk)-rational point P and said integers r and ci, for calculating r points P0 to Prâˆ’1 such that P0=P P1=&phgr;P P2=&phgr;2P : Prâˆ’1=&phgr;râˆ’1P; table reference addition means supplied with said r points P0 to Prâˆ’1, for obtaining mP by mP=&Sum;i=0r-1&it;â€ƒ&it;ci&it;Ï†i&it;P(2a)andoutput means for outputting said mP.