Patent Document ID: 20110261955
Application ID: 13129953
Patent Status: 0

Claim One:
1. A scalar multiplier that computes a scalar multiplication [s]P of a rational point P of an additive group E(F p ) including rational points on an elliptic curve where a characteristic p, an order r, and a trace t of a Frobenius endomorphism at an embedding degree k=12 using an integer variable χ are given by: 
 p (χ)=36χ 4 −36χ 3 +24χ 2 −6χ+1, 
 r (χ)=36χ 4 −36χ 3 +18χ 2 −6χ+1 =p (χ)+1− t (χ), 
 t (χ)=6χ 2 +1, the scalar multiplier comprising, to compute the scalar multiplication [s]P as: 
 [ s]P =([ s 4 +s 5 ]φ′ 2 +[s 2 −s 5 ]) P, using a Frobenius map φ′ 2 given by: 
 [ p 2 ]P=φ′ 2 ( P ) assuming that a twist degree d is 6 and a positive integer e is 2 where k=d×e to give: 
 [6χ 2 −4χ+1 ]P =[(−2χ+1) p 2 ]P=[− 2 χ+ 1 ]φ′ 2 ( P ), computing ν-adic expansion of the scalar s using 6χ 2 −4χ+1=ν to give: 
 s=s 1 ν+s 2 , s 2 <ν, and 
 s ≡(−2χ+1) s 1 p 2 +s 2 mod r, computing ν-adic expansion of the (−2χ+1)s 1 part to give: 
 s ≡( s 3 νs 4 ) p 2 +s 2 ≡s 4 p 2 +s 2 mod r where p 4 ≡p 2 −1 mod r, and using 
 s ≡( s 4 +s 5 ) p 2 +( s 2 −s 5 ) mod r : storage means for storing the value of the scalar s; and first to fifth auxiliary storage means for storing the coefficients S 1 , s 2 , s 3 , s 4 , and s 5 , respectively, wherein a value obtained by computing ν-adic expansion of the scalar s is stored in the first auxiliary storage means and the second auxiliary storage means, a value obtained by computing ν-adic expansion of (−2χ+1)s 1 is stored in the third auxiliary storage means and the fourth auxiliary storage means, and the value of (−2χ+1)s 3 is stored in the fifth auxiliary storage means.