数理解析研究所講究録
第 1744 巻 2011 年 129-136

129

Dynamic Programming Algorithm for
Optimal Double-Base Chains (Extended Abstract)
Vorapong Suppakitpaisarn

Hiroshi Imai\d ag er

Masato Edahiro \dag er*

February 23, 2011

Abstract

add method. This method depends on the binary
expansion of explained as follows:, andwhere isDefinea member of a finite set $Ds$ . We call $Ds$ as digit set,andas the binary expansionof . The $Hamn\dot{u}ng$ weight $W(R)$ is defined as$W(R)= \sum_{t=0}^{n-1}W(r_{t})$ , where $W(r_{t})=0$ when $r_{t}=$and $W(r_{t})=1$ otherwise. For example, let $Ds=$$\{0,1\}$ , and $r=127=2^{0}+2^{1}+2^{2}+2^{3}+2^{4}+2^{5}+2^{6}$ .
The binary expansion of is $R=\langle 1,1,1,1,1,1,1\rangle$ ,and the Hamming weight $W(R)=7$ .
In the double-and-add scheme, we need two elementary operations, that are point doubles $(S+S$ ,$2S)$ and point additions $(S+Q$ when $S\neq Q)$ . The
number of point doubles is constant for each scalar. However, the number of point additions depends
on the binary expansion. In some $Ds$ , there are
more than one way to expand a positive integer,
and we need select the efficient way. This problem
has been studied extensively in [1, 2].
In [3, 4], Dimitrov et al. proposed to use doublebase chains on the elliptic curve cryptography. Let, such thatbe a memberof digit set $Ds-\{0\}$ and $x_{t}\leq x_{t+1},$ $y_{t}\leq y_{t+1}$$X,$, whenfor all . We define $C[r]$$X=\langle x_{0},$,$Y=\langle y0,$as the double-base chains of. Also, we define the Hamming weight of doublebase chains $W(C[r])=m$ . For examples, one ofthe double-base chains of $127=2^{0}3^{0}+2^{1}3^{2}+2^{2}3^{3}$
when $R=\langle 1,1,1\rangle,$ $X=$
is $C[127]=\langle R,X,$. In this case $W(C[127])=3$ .
In addition to point doubles and point additions needed in the binary expansion, we also needpoint triples(3S). In some elliptic curves where thepoint triple is relatively fast, double-base chains areshown to be faster than the binary expansion.
Similar to the binary expansion, every scalars
have more than one double-base chains, and the efficiency of elliptic curve strongly depends on whichchain we use. The algorithm to select the good
double-base chains is very important. There aremany works have studied the problem [3, 4, 5, 6],$r$

In this work, we propose an algorithm to produce
the double-base chains that optimize the time used
for computing an elliptic curve cryptosystem. The
double-base chains is the representation that combining the binary and ternary representation. By
this method, we can reduce the Hamming weight ofthe expansion, and reduce the time for computing
the scalar point multiplication $(Q=rS)$ , that is thebottleneck operation of the elliptic curve cryptosystem. This representation is very redundant, i.e. we
can present a number by many expansions. Then,
we can select the way that makes the operation
fastest. However, the previous works on doublebases chain have used a greedy algorithm, and theirsolutions are not optimized. We propose the algorithm based on the dynamic programming schemethat outputs the optimized the double-bases chain.
The experiments show that we have reduced thetime for computing the scalar multiplication by
3.88-3.95%.
Keywords: Elliptic Curve Cryptography, Minimal Weight Conversion, Digit Set Expansion,
Double-Base Chains

1

Introduction$r_{1},$$\ldots,$$r_{n-1}\rangle$

$0$

$r$

$r$

$r= \sum_{t=0}^{m-1}r_{t}2^{x_{\ell}}3^{y_{t}}$$r_{t}$$=$$t$$Q=rS$

when $S,$ are points on the elliptic curve and isa positive integer. There are many works proposed
the ways to reduce the computation time of theoperation. Most of them are based on double-and$r$*Graduate School of Information Science and Technol-ogy, the University of Tokyo & ERATO-SORST Quantum

Computation and Information Project, Japan Science andTechnology Agency\dagger System IP Core Research Laboratories, NEC Corporation & Graduate School of Information Science and Technology, the University of Tokyo\d ag er
Same as$*$$R=\langle r_{0},$$r_{t}$$r$$R=\langle r_{0},$ $r_{1},$Scalar multiplication is the bottleneck operation of
the elliptic curve cryptography. It is to compute$Q$$r= \sum_{t=0}^{n-1}r_{t}2^{t}$$n=\lfloor lgr\rfloor$$y_{1},$$\ldots,$$\ldots,$$r_{m-1}\rangle,$$y_{m-1}\rangle$$r$$Y\rangle$$\langle 0,1,2\rangle,$$Y=\langle 0,2,3\rangle$$\langle R,$$x_{1},$$Y\rangle$$\ldots,x_{m-1}\rangle$

130
and proposed greedy algorithms that cannot guarantee the best chain. On the other hand, we
adapted our previous works [7, 8, 9], where we propose the dynamic programming algorithm to findthe minimal weight expansion of various representation. Then, we can find the algorithm that always
outputs the best chain, where the computation timeof all elementary operations (point additions, point
doubles, point triples) have been considered. By
the experiment, we have shown that the optimal
double-base chains are better than the best greedy
algorithm proposed on double base chain [6] by
3.9% when $Ds=\{0, \pm 1\}$ .
Recently, there is the independent work [10] proposed the algorithm which can output the chainswith least Hamming weight when $Ds=\{0,1\}$ . We
consider their work as the specific case of our works
as we are working on any finite digit sets. Also, ouralgorithm can output the least Hamming weight byadjusting the computation time for point doubles
and point additions to zero. When the point addition is the only elementary operation concerned,
minimizing the computation time of the scalar multiplication means optimizing the Hamming weight.
There is also the work utilizing Yao’s algorithmwith double base number system [11, 12], which isthe double-base without the restriction such thatand $y_{t}\leq y_{t+1}[13]$ . Their results of
the algorithm is comparable to our results evenwhen we select the $Ds$ that gives the best result.
However, our algorithm works better on the elliptic
curve that the point triple is fast comparing to thepoint double. These include inverted coordinates
on edwards curves which has the fastest point doubles [14] up to this states.
This paper is organized as follows: we show the
double-and-add scheme, and how we utilize thedouble-base chain to elliptic curve cryptography
in Section 2. In Section 3, we show our algorithm which outputs the optimal double-base chain.
Next, we show the experimental results comparing
to the existing works in Section 4. Last, we conclude the paper in Section 5.
$x_{t}\leq x_{t+1}$

is inidoubles, and point additions. However,tialized to , and we need not the point addition on
the first iteration. Also, $r_{t}S=0$ if $r_{t}=0$ , and weneed not the point addition in this case. Hence, thenumber of the point additions is $W(R)-1$ , where$W(R)$ the Hamming weight of the expansion defined in Section 1. The Hamming weight tends tobe less if the digit set $Ds$ is larger. However, as wefor all $r_{t}\in Ds$ , using big
need to precompute$Ds$ makes cost for the precomputation higher.
$Q$

$n$

$O$

$r_{t}S$$\frac{A1gorithm1Doub1e-and-addmethod}{Require:Apointone11ipticcurveS,thepos-}$

itive integer$\langle r_{0},$$r_{1},$$\ldots,$$r$$r_{n-1}\rangle$.

with the binary expansion

Ensure: $Q=rS$
1: $Qarrow O$
2: for $tarrow n-1$ downto$Qarrow Q+r_{t}S$3:4:
if $t\neq 0$ then
$Qarrow 2Q$
5:
6:
end if
7: end for

$0$

do

In Algorithm 2, we show how to apply the
double-base chain$C[r]=\langle R,$ $X,$

$Y\rangle$,

when$R=\langle r_{0},$ $r_{1},$$\ldots,$$r_{m-1}\rangle$,$X=\langle x_{0},x_{1},$ $\ldots,x_{m-1}\rangle$$Y=\langle y_{0},$ $y_{1},$$\ldots,$,$y_{m-1}\rangle$

to compute scalar multiplication. For example, oneof the double-base chain of $127=2^{0}3^{0}+2^{1}3^{2}+2^{2}3^{3}$
is $C[12\eta=\langle R,X,Y\rangle$ , where $R=\langle 1,1,1\rangle,$ $X=$
. Hence, we can compute $Q=$
$127S$ as follows:$\langle 0,1,2\rangle,$$Y=\langle 0,1,3\rangle$.

$Q=2^{1}3^{2}(2^{1}3^{1}S+S)+S$

2Preliminaries

Using the binary expansion$R=\langle r_{0},$ $r_{1},$$\ldots,$$r_{n-1}\rangle$

,

$we$

$Cancomphesca1armu1tip1icationQ=rSbywherer=\sum_{utet^{t=0}}^{n-1}r_{t}2^{t}exp1ainedinSection1,$

In this case, we need two point additions, two point
doubles, and three point triples. In general, thenumber of point additions is $W(C)-1=m-1$
defined in Section 1. On the other hand, the number of point doubles and point triples are $x_{m-1}$ anddouble-and-add scheme as shown in Algorithm 1. $y_{m-1}$ respectively.
For example, we compute $Q=127S$ when the biIn the double.and-add method, the number ofnary expansion of 127 is $R=\langle 1,1,1,1,1,1,1\rangle$ as point doubles required is proved to be constantly
follows:
equal to $n-1=\lfloor lgr\rfloor-1$ . Then, the efficiencyof the binary expansion strongly depends on the$Q=2(2(2(2(2(2S+S)+S)+S)+S)+S)+S$. number of point additions or the Hamning weight.
However, the number of point doubles and point
We need six point doubles and six point additions triples are not constant, as discussed in the previous
in this example. Generally, we need $n-1$ point paragraph that they are equal to $x_{m-1}$ and $y_{m-1}$

131
Algorithm 2 double-bUhdbl
Using thebase chain to compute scalar multiplication$R$ quire: Apoint
on elliptic curve $S,$ thhe positive integer
with the double-base chains$C[r]=\langle R,$ $X,$
, where
,

$i11$
$r$

$R=\langle r_{0},$$Y\rangle$$X=\langle x_{0},$ $\ldots,x_{m-1}\rangle,$$\ldots,$$Y=\langle y_{0},.\cdots,y_{m-1}\rangle$

Ensure: $Q=rS$$r_{m-1}\rangle$.

1: $Qarrow O$
2: for $tarrow m-1$ downto do$Qarrow Q+r_{t}S$3:4:
if $t\neq 0$ then
$Qarrow 2^{(x_{t-1}-x_{t})}3^{(y_{t-1}-y_{t})}Q$
5:
6:
else
$0$

7:

Figure 1: We can compute $C[7]$ by two ways. The
first way is to compute $C[3]$ , and perform a point$Qarrow 2^{x_{O}}3^{yo}Q$

end if8:$\underline{9:endfor}$respectively. Hence, we need to optimize the value$x_{m-1}\cdot P_{dou}+y_{m-1}\cdot P_{tri}+(W(C[r])-1)\cdot P_{add}$,$doub1eandapointaddition.ThecostinthiswayisP(C[3])+P_{dou}+P_{add}.Thesecondwayisto$

compute $C[2]$ , and perform a point triple and apoint addition, where the cost is $P(C[2]+P_{tri}+$. The cost of the first way is smaller than thesecond way, and we select the first way to compute$P_{add})$

when
are the cost for point double, $C[7]$ .
point triple, and point addition respectively. Thisis different ffom the literature [1, 2, 7, 8, 9, 10]
where only the Hamming weight is considered.
1 $=2^{0}3^{0}$ . Hence, $x_{0}=0$ and $y_{0}=0$ . Then,. By this equation, there are
only two ways to compute the scalar multiplication
3 Algorithm$Q=7S$ with Algorithm 2. The first way is to com$3S$ , do point double to $6S$ and point additionpute
3.1 Algorithm for single integer with
to $7S$ . As we know the the optimal chain for 3,$Ds=\{0,1\}$
the cost using this way is $P(C[3])+P_{dou}+P_{add}$ .
Define the cost to compute using the chain $C[r]=$ The$6S$other way is to compute$7S$$2S$ , do point triple
toand point addition to. In this case, theascost is $P(C[2])+P_{tri}+P_{add}$ . The optimal way is$P(C[r])=x_{m-1}\cdot P_{dou}+y_{m-1}\cdot P_{tri}+(W(C[r])-1)\cdot P_{add}$to select one of these two ways. We will show laterthat $P(C[3])=2$ and $P(C[2])=1$ . Then,, and $P(C[r])=0$ otherwise.
when$P(C[3])+P_{dou}+P_{add}=2+1+1=4$ ,Our algorithm is to find the double-base chain of$C[r]=\langle R,X,$
such that for all double-base$P(C[2])+P_{tri}+P_{add}=1+20+1=22$ .
chain of $Ce[r]=\langle Re,$ $Xe,$,
We select the first choice, and the optimal cost is$P(Ce[r])\geq P(C[r])$ .
$P(C[7])=4$ . The optimal $c[\eta=\langle R,$ $X,$
when
$R=\langle 1,$$x_{0}=0$,.
where
To explain the algorithm, we start with a small
and $x_{t}=x[3]_{t-1}+1$ for 1 $\leq t\leq m-$ 1. Y
example explained in Example 1 and Figure 1.
, where $y_{0}=0$ and $y_{t}=y[3]_{t-1}$ for$1\leq t\leq m-1$ .
Example 1 Find the optimal chain $C[7]$Next, we find $C[3]$ that is the optimal doublegiven $Ds=\{0,1\},$ $P_{tri}=20,$ $P_{dou}=1$ ,. Similar to $7S$ , we can combase chain of
and $P_{add}=1$ .
Assume that we are given the optimal chain pute $3S$ by two ways. The first way is to triple thewe $needonepointtriple$ ,$C[3]=\langle R[3],X[3],$$double-basechaininpointSUsingthisway,$$whichcostsP_{tri}=20.$ The. The other way is that
this case will be$m-1$
as $7= \sum_{t=0}r_{t}2^{x_{t}}3$”, when $r_{t}\in Ds-\{0\}=\{1\}$ . we double point to $2S$ , then add $2S$ with to get
As 2 {7 and 3 {7, the smallest term much be $3S$ . The cost is $P_{dou}+P_{add}=1+1=2$ . In this case,$P_{dou},$ $P_{tri},$ $P_{add}$$7= \sum_{t=1}^{m-1}2^{x_{t}}3^{y_{t}}+1$$r$$\langle R,X,$ $Y\rangle$$C[r]\neq\langle\langle\rangle,$$r,$$\langle\rangle,$$\langle\rangle\rangle$$Y\rangle$$r,$$Ye\rangle$$Y\rangle$$R[3]\rangle$$X=\langle x_{0},$ $\ldots,x_{m-1}\rangle$$f$$\langle y_{0},$$\ldots,$$=$$y_{m-1}\rangle$$=$$\langle R,X,$$Y\rangle$$L\frac{7}{2}\rfloor=3$$Y[3]\rangle of.3=\lfloor\frac{7}{2}\rfloor andC[2]=\langle R[2],X[2],Y[2]\rangle of2=\lfloor\frac{7}{3}\rfloor Wewanttorewrite7$$\langle\langle 1\rangle,$$S$$\langle 0\rangle,$$\langle 1\rangle\rangle$

$S$

132
Next, we will step to the algorithm. In Example 1, we consider the computation as a topdown algorithm. However, bottom-up algorithm isbetter way to implement the idea. We begin thealgorithm by computing the double-base chain ofsuch that $x+y=q$ where
for all $x,$$2^{q}\leq r<2^{q+1}$ . Then, we move to compute thefor all $x,$
suchdouble-base chain ofthat $x+y=q-1$ by referring to the double-basewhen $x+y=q$ . We decrease thechain of$x+y$
numberuntil $x+y=0$ , and we get the chain.
of
We illustrate this idea in Figure 2.

$\frac{r}{2^{q}3^{0}}$$y\in \mathbb{Z}^{+}$$\lfloor\frac{r}{2^{x}3u}\rfloor$

$–$

$r$

$y\in \mathbb{Z}^{+}$$L\frac{r}{2^{x}3^{y}}\rfloor$$\frac{r}{\underline{2^{q-1}3}^{1}}$$\lfloor\frac{r}{2^{x}3^{y}}\rfloor$$r=\lfloor_{F^{r_{3}}}\tau\rfloor$

3.2

Generalized Algorithm for Any

Digit Sets

In this section, we expand our results applying ourformer works [7, 8, 9] to our previous subsection.
As a result, the proposed double-base chains canbe used on the digit set other than $\{0,1\}$ .
When $Ds=\{0,1\}$ , we usually have two choices
compute $C[v]$ . One is to perform a point double,
toFigure 2: Bottom-up algorithm to find the optimal. Another isand use the subsolution
double-base chain of
to perform a point triple, and use the subsolution. However, we have more choices. We se- when we deploy larger digit set. For example, when
the double-base chain is 1,lect the better double-base chain that is $C[3]=$ $Ds=\{0, \pm 1\}$–$\frac{r}{2^{0}3^{q},mw-}d$$C[v_{2}]=C[ \lfloor\frac{v}{2}\rfloor]$$r$$C[v_{3}]=C[ \lfloor\frac{v}{3}\rfloor]$$\langle\langle$$1\rangle,$$\langle 0,1\rangle,$$\langle 0,0\rangle\rangle$.
$5=2\cross 2+1=3\cross 2-1=2\cross 3-1$ ,Last, we find $C[2]$ , the optimal double-base chain. The interesting point to note is that the number of cases increase bom one in the preof
subsection to three. Also, we naed more opthere are only one choice to consider in this case. vious
in this caee. Even for point doutimal
subsolution
This is because the fact that we cannot rewrite 2$r\equiv
2mod
3$
.
ble,
we
and
naed
.
by $3A+B$ whenand $B\in Ds$ if
Then, the only choice left is to double the point , We callas standard, and the addiwhich costs 1, and the double-base chain is $C[2]=$ tional term $g[v](g[2]=1$ in $C[3]$ and $g[2]=0$.
in $C[2])$ as carry. By this definition, we get the
To conclude, the optimal double-base chain for 7 relation $(vmod 2)+g[v]=u+g[v_{2}]$ , when $u\in$. We $Ds$ . This is the case when we choose to performin this case isnote that $C$ is not the double-base with the least point double. Let $C[v_{2}+g[v_{2}]]=\langle R’,$ $X’,$
Hamming weight as
be the optimal solution of $r=v_{2}+g[v_{2}]$ . Dehas lower Hamning weight.
, $x_{m-1}’’)$ where $x_{i}’’=x_{i}’+1$ ,fine $X”=\langle x_{0}’’,$$Y”=Y’,$ $R”=R’$ . The edited solution of $C[v+$Define $C[r],$be the optimal double- $g[v]]=\langle R,$ $X,$,
when $X=\langle 0,X’’\rangle,$
respectively.From Exam- $R=\langle u,$base chain of. If we perform point triple, the reple 1, $P(C^{f})= \min(P(C[\lfloor\frac{f}{2}\rfloor])+P_{dou},$lation is $(vmod 3)+g[v]=u+g[v_{3}]$ . Again, we$0mod 6$ .
, when
It is equal to define $C[v_{3}+g[v_{3}]]=\langle R’,$ $X’,$
be the opti$\min(P(C[\lfloor\frac{r}{2}\rfloor])+P_{dou}, P(C[\lfloor\frac{f}{3}\rfloor])+P_{tri})+P_{add}$ ,mal solution of $r=v_{3}+g[v_{3}]$ , and $X”=X’$ ,where $y_{i}’’=y_{i}’+1,$ $R”=R’$ .
,when
lmod6. It is equal to
Similar to the case when we perform point double,
when $r\equiv 2mod 6$ . It is equal towhen
the edited solution of $C[v+g[v]]=(R,$ $X,$
$P_{dou}+P_{add},$, when $r\equiv 3mod 6$ . $X=\langle 0,$$R=\langle u,$$Y=\langle 0,$. We illusIt is equal to $\min(P(C[\lfloor\frac{r}{2}\rfloor])+P_{dou},$
trate the idea in Figure 3 and Example 2.
$P_{tri}+P_{add})$ , when $r\equiv 4mod 6$ .
It is equal to$P(C[ \lfloor\frac{f}{2}\rfloor])+P_{dou}+P_{add}$ when $r\equiv 5mod 6$ .
Example 2 Compute the optimal double-base$\langle\langle 1,1\rangle,$$\langle 0,1\rangle,$$\langle 0,0\rangle\rangle$$L\frac{7}{3}\rfloor=2$$C[2]=C[ \lfloor\frac{5}{2}\rfloor]$$A\in \mathbb{Z}$$S$$\langle\langle 1\rangle,$$\langle 1\rangle,$$C[3]=C[ \lfloor\frac{5}{2}\rfloor+1]$$v= \lfloor\frac{5}{2}\rfloor=2$$\langle 0\rangle\rangle$$c[\eta=\langle\langle 1,1,1\rangle,$$\langle 0,1,2\rangle,$$\langle 0,0,0\rangle\rangle$$Y’\rangle$$Ce[\eta=(\langle 1,1\rangle, \langle 0,1\rangle, \langle 0,1\rangle)$$\ldots$$C[ \lfloor\frac{r}{2}\rfloor],$$C[ \lfloor\frac{r}{3}\rfloor]$$Y=\langle 0,Y’’\rangle$$Y\rangle$$r,$$L\frac{r}{2}\rfloor,$$r$$\equiv$$L\frac{r}{3}\rfloor$$R”\rangle$$P(C[ \lfloor\frac{r}{3}\rfloor])+$$P_{tri})$$Y’\rangle$$P(C[ \lfloor\frac{r}{2}\rfloor])+P_{dou}$$r\equiv$$Y”=\langle y_{0}’’,$$\ldots,$$y_{m-1}’’\rangle$$\min(P(C[\lfloor\frac{r}{2}\rfloor])+$$Y\rangle$$P(C[ \lfloor\frac{f}{3}\rfloor])+P_{tri})$$X”\rangle,$$P(C[ \lfloor\frac{r}{3}\rfloor])+$$Y”\rangle,$$R”\rangle$

133
Algorithm 3 thThlihfidhe
The algorithm finding
optimal$\frac{doub1e-basechainforsing1eintegerforanyDs}{Require:thepositiveintegerr,thefinitedigitset}$$Ds$ , and the carry set
Ensure: the optimal double-base chain of
$G$

$r$

,

$C[r]=\langle R[r],$ $X[r],$ $Y[r]\rangle$

1:
2: while $q\geq 0$ do
for all $x,$3:
4:
$qarrow\lfloor lgr\rfloor$$y\in \mathbb{Z}^{+}$

such that $x+y=q$ do$v arrow\lfloor\frac{r}{2^{x}3v}\rfloor$

5:

Figure 3: Given $Ds=\{0, \pm 1\}$ , we can compute$C[5]$ by three ways. The first way is to compute$C[2]$ , and perform a point double and a point addition. The second is to compute $C[3]$ , perform
a point double, and a point substitution (add thepoint $with-S$ ). The third is to compute $C[2]$ , perform a point triple, and a point substitution. All
methods consume the same cost.

chain of 5 when $P_{add}=P_{dou}=P_{tri}=1$ and$Ds=\{0, \pm 1\}$.

When $Ds=\{0, \pm 1\}$ , we can compute the carry

set $G=\{0,1\}$ .
We want to compute $C[5]=\langle R,$ $X,$

for all $g[v]\in G$ do$vaarrow v+g[v]$6:7:
if $va=0$ then$C[va]arrow(\langle\rangle,$
8:
else if $va\in Ds$ then
9:
10:
11:
else
12:
13:
$C[va]arrow FO(va, C[v_{2}+G], C[v_{3}+G])$
14:$15$ :
end if16:
end for17:
end for$qarrow q-1$
18:
19: end while$(\rangle,$$C[va]arrow\langle\langle va\rangle,$$\langle\rangle\rangle$$\langle 0\rangle,$$\langle 0\rangle)$$v_{2} arrow\lfloor\frac{r}{2^{x+1}3^{y}}\rfloor$$v_{3} arrow\lfloor\frac{r}{2^{x}3y+1}\rfloor$

such that$x_{i}\leq x_{i+1},$ $y_{i}\leq y_{i+1}.5$ canandbe rewritten as follows:
such as the scalar multiplication defined on the binary field
and the scalar multiplication de$5=2\cross 2+1=(2+1)\cross 2-1=(1+1)\cross 3-1$ .
fined on the prime field. To compute point
We need $C[2](v_{2}=2, g[v_{2}]=0),$ $C[3](v_{2}=2$ , addition, point double, and point triple definedin Section 1, we need to compute field inversion,$g[v_{2}]=1)$ , and $C[2](v_{3}=1, g[v_{3}]=1)$ .
It is easy to see that the optimal chain $C[2]=$ field squaring, and field multiplication. We desquarand. $P(C[2])=$ fine the$[s]$cost for field inversion as , field$[m]$ .
,
ing
multiplication
and
as
field
as
Basi$P(C[3])=1$ .
cally, $P_{dou}=P_{add}=[i]+[s]+2[m]$ . However,
2 $Wechoosethe+l,5=3\cross 2-l,5=bestchoiceamon\S 5\cross=23-1\cross$. there are many researches working on optimizing
more complicated operation such as point triple,
By the first choice, we get the chain $C’[5]$point
quadruple [3, 4, 15, 16]. Moreover, when
. The second choice and thepoint
addition
is chosen to perform just after thethird choice is $C”[5]=\langle\langle-1,1\rangle,$. We
get $P(C’[5])=P(C”[5])=3$ , and both of them point double, we can use some intermediate resultsof point double to reduce the computation time of
can be the optimal chain $(C[5]=C’[5]=C”[5])$ .
point addition. Then, it is more convenient to consider point double and point addition together as
Using the idea explained above, we propose Al- the basic operation. We call the operation as point
gorithm 3,4.
double-and-add. The computation cost of point
double-and-add is $P_{dou+add}$ . The similar thing also
happen when we perform point addition after point
4 Results
triple, and we also define point triple-and-add asanother basic operation. Also, we define the comTo evaluate our algorithm, we show some exper- putation cost of point triple-and-add as $P_{tri+add}$ .
imental results in this section. We perform the It is obvious that we can treat these improvements
experiment on each implementation environment by a little modification in Algorithm 3,4.
$r_{i}\in Ds$$Y\rangle$$x_{i},$ $y_{i}\in \mathbb{Z},$$(F_{2q})$$(F_{p})$$\langle\langle 1\rangle,$$\langle 1\rangle,$$\langle 0\rangle\rangle$$C[3]=\langle\langle 1\rangle,$$[i]$$\langle 0\rangle,$$\langle 1\rangle\rangle$$=$$\langle\langle 1,1\rangle,$$\langle 0,0\rangle,$$\langle 0,2\rangle\rangle$$\langle 0,1\rangle,$$\langle 0,1\rangle\rangle$

134$\underline{Algorithm4FO(va,C[v_{2}+G],C[v_{3}+G])}$
Require: the positive integer va,
for allthe optimal double base chain of
for all
and the optimal double base chain of
Ensure: the optimal double base chain of va, $C[va]$$g[ \lfloor\frac{va}{2}\rfloor]\in G,$$\lfloor\frac{va}{2}\rfloor+g[\lfloor\frac{va}{2}\rfloor]$$\lfloor \mathscr{F}\rfloor+g[\lfloor\frac{va}{3}\rfloor]$$C[va_{2}+G]$ ,$g[ \lfloor\frac{va}{3}\rfloor]\in G,$$C[va_{3}+G]$

1: $c_{2,u}arrow\infty,$ $c_{3,u}arrow\infty$
2: for all $u\in Ds$ such that $va- u\equiv 0mod 2$ do$c_{2,u} arrow P(C[\frac{va-u}{2}])+P_{dou}$3:$c_{2,u}arrow c_{2,u}+P_{add}$ if $u\neq 0$
4:
5: end for
6: $c_{2} arrow\min_{u\in D\epsilon}c_{2,u},$ $u_{2} arrow\min\arg_{u\in Ds}c_{2,u},$ $vc_{2}arrowarrow^{va-u2}$
7: for all $u\in Ds$ such that $va– u\equiv 0mod 3$ do$c_{3,u} arrow P(C[\frac{va-u}{3}])+P_{tri}$8:$c_{3,u}arrow c_{3,u}+P_{add}$ if $u\neq 0$
9:10: end for
11: $c_{3} arrow\min_{u\in D\epsilon}c_{3,u},$ $u_{3} arrow\min\arg_{u\in D\epsilon}c_{3,u},$ $vc_{3}arrowarrow^{va-u3}$

12: ifand $u_{2}=0$ then$R[v]arrow R[vc_{2}],$ $X[v]arrow\langle x[v]_{0},$ $\ldots,x[v]_{m-1}\rangle$ where $x[v]_{t}arrow x[vc_{2}]_{t}+1,$ $Y[v]arrow Y[vc_{2}]$13:
14: else ifthen$c_{2}\leq c_{3}$$c_{2}\leq c_{3}$15:$R[v]arrow\langle u_{2},$ $R[vc_{2}]\rangle,$ $X[v]arrow\langle 0,x[v]_{1},$ $\ldots,x[v]_{m-1}\rangle$: else if $u_{3}=0$ then$R[v]arrow R[vc_{3}],$ $X[v]arrow X[vc_{3}],$ $Y[v]arrow\langle y[v]_{0},$17:where $x[v]_{t}arrow x[vc_{2}]_{t-1}+1,$$Y[v]arrow\langle 0,$ $Y[vc_{2}]\rangle$$16$$\ldots,$$y[v]_{m-1}\rangle$

where $y[v]_{t}arrow y[vc_{3}]_{t}+1$

ls: else$R[v]arrow\langle u_{3},$19:$20$ : end if
21: $C[v]arrow\langle R[v],X[v],$$R[vc_{3}]\rangle,$

4.1$X[v]arrow\langle 0,$ $X[vc_{3}]\rangle,$ $Y[v]arrow\langle 0,y[v]_{1},$$\ldots,$$y[v]_{m-1}\rangle$

where $y[v]_{t}arrow y[vc_{3}]_{t-1}+1$$Y[v]\rangle$

Scalar Multiplication on the Bi- In both experiments, we set $Ds=\{0, \pm 1\}$ , andwe randomly select 10000 positive integers whichnary Field
are less thanIn the binary field, the field squaring is very fast,i.e. $[s]\approx 0$ . Normally, $3\leq[i]/[m]\leq 10$. There-add,
are two methods to compute point
point triple, and point triple-and-add proposed by[15, 16]. We use the same parameter as [3] does, andperform two experiments. First, We set $[i]/[m]=4$
and use the method $hom[16]$ . In this case,$doubl\triangleright and$

$P_{dou}=P_{add}=[i]+[s]+2[m]=6[m]$ ,, and find the average computation cost comparing between the optimal chain proposed in this paper and the greedy algorithm presented in [3, 4]. The results are shown in Table 1.
Our result is 4.06% better than [3] when $[i]/[m]=$4, and 4.77% better than [3] when $[i]/[m]=8$ .
$2^{163}$

Table 1: Comparing the computation cost for scalarpoint multiplication using double-base chains when$P_{dou+add}=P_{tri}=2[i]+2[s]+3[m]=11[m]$ ,$P_{tri+add}=3[i]+3[s]+4[m]=16[m]$ .

In another experiment, we set $[i]/[m]=8$ and use
the method from [15]. In this case,$P_{dou}=P_{add}=[i]+[s]+2[m]=10[m]$ ,$P_{dou+add}=1[i]+2[s]+9[m]=17[m]$ ,$P_{tri}=1[i]+4[s]+7[m]=15[m]$ ,$P_{tri+add}=2[i]+3[s]+9[m]=25[m]$ .

$\frac\frac{thee\overline{Method[i]/[m]=4[i]/[m]=8}m_{P}ticcurveisimplementedinthebinaryfie1d}{Binary1627[m]2441[m]}$NAF [1]Ternary/Binary [12]DBC (Greedy) [3]Optimized DBC(Our Result)$1465[m|$$2225[m]$1463 $[m]$1427 $[m]$2168 $[m]$2139 $[m]$$1369[m]$$2037[m]$

135
4.2

Scalar Multiplication on the improve the result ffom [13] in many cases. These
cases are the case when point triple is costly opPrime Field

When we compute the scalar multiplication on theprime field, field inversion is very expensive task
as $[i]/[m]$ is usually more than 30. To cope with
that, we compute in the coordinate in which weneed to perform field inversion as least as possible
such as inverted Edward coordinate with a curvein Edwards form [17]. Up to this state, it is thefastest way to implement scalar multiplication. In
this case, the number of field inversion required ineach scalar multiplication is constant, and $P_{add}=$$9[m]+1[s],$ $P_{dou}=3[m]+4[s]$ , and $P_{tri}=9[m]+4[s]$[18]. To compare our results with the existing
work, we set the parameter similar to what [6] does.
$[s]=0.8[m]$ , and $Ds=\{0, \pm 1\}$ . We perform fiveexperiments, for the positive integer less than,
$2^{320},2^{384},2^{448}$ , and. In each experiment, we
randomly select 10000 integer, and find the average computation cost in term of $[m]$ . We show theresults in Table 2. Our results improve the treebased approach proposed by Doche and Habsieger
by 3.95%, 3.88%, 3.90%, 3.90%, 3.90% when the bit
number is 192 bits, 256 bits, 320 bits, 384 bits, 512
bits respectively.
We also compare our results with the other digit
sets. In this case, we compare our results withthe works by Bernstein et al. [5]. In the paper,
they use the different way to measure the computation cost of the scalar multiplication. In addition to the cost of computing $rS$ , they also consider the cost for the precomputation. For exam$17S$ whenple, we need to precompute $3S,$ $5S,$$Ds=\{0, \pm 1, \pm 3, \ldots, \pm 17\}$ . We perform the experiment on eight different curves and coordinates. In
each curve, the computation cost for point double,
point addition, and point triple are different, andwe use the same parameter as defined in [5]. We
use $Ds=\{0, \pm 1, \pm 3, \ldots, \pm(2h+1)\}$ , and we check
all $0\leq h\leq 20$ to find the digit set that give us theminimal average computation cost. Although, thecomputation cost of the scalar multiplication tends
to be lower if we use larger digit set, the higher
precomputation cost makes optimal lied between
6 to 8 in most of cases.
Recently, there is a research by Meloni and Hasan[13]. Instead of using double-base chain, they use
double-base number system defined in Section 1.
To cope with the difficulties computing the number system, they introduce Yao’s algorithm. Theirresult significantly improves the result using the
double-base chain using greedy algorithm, especially the curve where point triple is expensive.
In Table 3, we compare the results in [5], [13]with our algorithm. We randomly choose 10000
positive integers less than. As the improvement ffom [5], our algorithm significantly improves
the efficiency. On the other hand, our results do not$2^{256}$$2^{512}$$\ldots,$$h$$2^{160}$

eration, and we need only few point triples in the
optimal chain. In this case, Yao’s algorithm works
efficiently. However, our algorithm works betterin the inverted Edward coordinate, which is commonly used as the benchmark to compare the algorithm.

5

Conclusion

In this work, we use the dynamic programming algorithm to present the optimal double-base chain.
The chain guarantees the optimal computation coston the scalar multiplication. The time complexityof the algorithm is $O(lg^{2}r)$ , similar to the greedy
algorithm. Also, our algorithms consume the sameamount of memory as the tree-based approach,$O(lg^{2}r)$ . The experiment result shows that the optimal chain significantly improve the efficiency of
scalar multiplication from the greedy algorithm.

References[1] Egecioglu, O., Koc, C.K.: Exponentiation using canonical recoding. Theoretical Computer
Science 8(1) (1994) 19-38[2] Muir, J.A., Stinson, D.R.:
New minimal
weight representation for leffi-to-right window

methods. Department of Combinatorics andoptimization, School of Computer Science,
University of Waterloo (2004)[3] Dimitrov, V., Imbert, L., Mishra, P.K.: Efficient and secure elliptic curve point multiplication using double-base chains. In: Proc. of
ASIACRYPT 2005. (2005) 59-78[4] Dimitrov, V., Imbert, L., Mishra, P.K.: The
double-base number system and its application
to elliptic curve cryptography. Mathematics ofComputation 77 (2008) 1075-1104[5] Bernstein, D.J., Birkner, P., Lange, T., Peters, C.: optimizing double-base elliptic-curve
single-scalar multiplication. In: In Progressin Cryptology-INDOCRYPT 2007. Volume4859 of Lecture Notes in Computer Science.,
Springer (2007) 167-182[6] Doche, C., Habsieger, L.: A tree-based approach for computing double-base chains. In:

ACISP 2008. (2008) 433-446[7] Suppakitpaisarn, V.: Optimal average jointhamming weight and digit set expansion on
integer pairs. Master’s thesis, The Universityof Tokyo (2009)

136
Table 2: Comparing the computation cost for scalar point multiplication using double-base chains whenthe elliptic curve is implemented in the prime field

bits256bits320bits384bits512bits$\overline{\overline{Methodl92}}$

4241.1 [m]$\overline{NAF[1]1817.6[m]2423.5[m]3029.3[m]3635.2[m]}$Ternary/Binary [12]DB-Chain (Greedy) [4]Tree-Based Approach [6]
Our Result

1761.2[m]1725.5[m]2353.6[m]2302.0[m]2944.9[m]2879. 1 [m]3537.2[m]3455.2 [m]4129.6[m]4032.4[m]$1691.3[m]$$2255.8[m]$$2821.0[m]$$3386.0[m]$$1624.5[m]$$2168.2[m]$$2710.9[m]$$3254.1[m]$$3950.3[m]$$3796.3[m]$Table 3: Comparing the computation cost for scalar point multiplication using double-base chains inlarger digit set when the elliptic curve is implemented in the prime field, and the bit number is 160
ExtJQuartic
Edwards
Hessian$1311.0[m]$$1565.0[m]$$1502.4[m]$$1322.9[m]$
DBC Greedy Alg. [5]$1477.3[m]$$1283.3[m]$$1226.0[m]$$1501.8[m]$DBNS Yao’s Alg. [13]$1438.7[m]$$1276.5[m]$$1514.4[m]$$1284.3[m]$Our Algorithm$\overline{\overline{Method3DIK}}$
$+$

$+$

InvEdwards JacIntersect
Jacobian
Jacobian-3$\overline{\overline{Method}}$

DBC Greedy Alg. [5]DBNS Yao’s Alg. [13]Our Algorithm
$+$

$+$

$1290.3[m]$$1438.8[m]$$1558.4[m]$$1504.3[m]$$1258.6[m]$$1257.5[m]$$1301.2[m]$$1534.9[m]$$1514.5[m]$$1475.3[m]$$1458.0[m]$[8] Suppakitpaisarn, V., Edahiro, M.: Fast scalarpoint multiplication using enlarged digit set on
integer pairs. Proc. of SCIS 2009 (2009) 14[9] Suppakitpaisarn, V., Edahiro, M., Imai, H.:
Optimal average joint hamming weight andminimal weight conversion of integers. Cryptology ePrint Archive 2010/300 (2010)$d$[10] Imbert, L., Philippe, F.: How to computeshortest double-base chains? In: ANTS IX.
(July 2010)[11] Dimitrov, V., Cooklev, T.V.: Two algorithms
for modular exponentiation based on nonstandard arithmetics. IEICE Tkans. FUndamentals
E78-A(1) (January 1995) 82-87 special issue
on cryptography and information security.
[12] Dimitrov, V.S., Jullien, G.A., Miller, W.C.:
An algorithm for modular exponentiations. Information Processing Letters 66 (1998) 155-

159

[13] Meloni, N., Hasan, M.A.: Elliptic curve scalarmultiplication combining yao’s algorithm anddouble bases. In: CHES 2009. (2009) 304-316$1376.0[m]$[14] Doche, C., Kohel, D.R., Sica, F.: Doublebase number system for multi-scalar multiplications. In: EUROCRYPT 2009. (2009) 502-

517
[15] Ciet, M., Joye, M., Lauter, K., Montgomery,
P.L.: hading inversions for multiplications
in elliptic curve cryptography. Daeigns, Codae
and Cryptography 39(6) (2006) 189-206[16] Eisentrager, K., Lauter, K., Montgomery,
P.L.: Fast elliptic curve arithmetic and improved Weil pairing evaluation. In: Topics in
Cryptology-CT-RSA 2003. Volume 2612 of
Lecture Notes in Computer Science., Springer(2003) 343-354[17] Bernstein, D.J., Lange, T.: Inverted edwards
coordinates. In Boztas, S., H.-F.Lu, eds.:
AAECC 2007. Volume 4851 of Lecture Notein Computer Science., Heidelberg, Springer(2007) 20-27[18] Bernstein, D., Lange, T.:

database

Explicit-formulas