橢圓曲線密碼體制中標量乘法的快速算法
2009-01-01 00:00:00劉連浩申勇
計算機應用研究 2009年3期
(中南大學 信息科學與工程學院， 長沙 410083)
摘 要：求逆是標量乘法中最耗時的運算，求逆運算次數的多少直接決定標量乘法的性能。轉換求逆為乘法運算能夠降低求逆次數。根據這種思想，提出了素域Fp上用仿射坐標直接計算3P+Q的算法，其運算量為1I+3S+16M，比Ciet等人提出的方法節省了一次求逆運算。同時還給出直接計算3kP的算法，該算法比重復計算k次3P更有效。最后結合3NAFw的編碼方法，把兩個新算法應用到標量乘法中。結果表明，運用3P+Q、3kP的標量乘法比傳統的NAF、NAF4等方法更有效，相交處I/M的值可降為5.4。
關鍵詞：橢圓曲線密碼體制； 標量乘法； 仿射坐標； 求逆； NAF
中圖分類號：TP309 文獻標志碼：A
文章編號：10013695(2009)03110405
Fast algorithm for scalar multiplication in elliptic curves cryptography
LIU Lianhao， SHEN Yong
（School of Information Science Engineering， Central South University， Changsha 410083， China）
Abstract:A field inversion is the most expensive operation on scalar multiplication， and the number of inversion determines the performance of scalar multiplication. Trading inversions for multiplications can decrease the number of inversion. Based on the idea，this paper proposed an efficient algorithm to compute 3P+Q directlyover Fp in terms of affine coordinates， its computational complexity was 1I+3S+16M， saving one field inversion compared to Ciet’s method. Moreover， also gave an improvement to compute 3kP directly， which was more efficient than k repeated 3P. Finally， applied the two algorithms to scalar multiplication combined with the representation of 3NAFw.The result suggests that the scalar multiplication using 3P+Q and 3kP is faster than traditional methods， such as NAF， NAF4 and so on， and the ration I/M of breakeven point can be reduced to 5.4.
Key words：elliptic curves cryptography(ECC); scalar multiplication; affine coordinates; field inversion; nonadjacent form
0 引言
1985年，Koblitz[1]和Miller[2]分別提出了一種能在低要求的計算環境中達到高強度加密的一種新的公鑰算法——橢圓曲線密碼體制(ECC)，并逐步成為國內外學者研究的熱點。這種密碼體制受歡迎之處在于在安全性相當的前提下可用較短的密鑰。就安全性而言，一般認為ECC160位的密鑰與RSA1 024位密鑰是相當的，為保證長期的安全性，RSA至少需要2 048位，而橢圓曲線密碼體系只需要210位。有數據表明當位長加倍時，公鑰操作時間(加密或簽名驗證)增加為原來的4倍，私鑰操作時間(解密或簽名)增加為原來的8倍[3]。密鑰短意味著存儲空間占用少、帶寬要求低等。ECC的這些特點使得業內人士普遍認為它在某些計算能力和存儲空間受限的領域如PDA、手機、智能卡等方面的應用將取代RSA， 并成為下一代最通用的公鑰加密算法標準。
利用ECC算法加密、解密、簽名、驗證，最主要和最耗時的運算是標量乘法。所謂標量乘法就是給定一個整數m（標量）和橢圓曲線上的一個點P（基點），求另外一個點mP的運算。現階段，計算mP也有一些較好的辦法[4~6]，可歸納為：a）對基點P進行坐標變換（仿射坐標、投影坐標、Jacobian坐標等）；b）對標量m進行重新編碼（二進制、三進制、NAF、wNAF等）；c）在曲線上進行有效的群運算(2P、2P+Q、3P、3P+Q等）；d）利用comb、加減法鏈等有效算法。本文首先采用方法c)對3P+Q進行群運算，然后采用方法b)對m進行重新編碼，最后計算mP。
標量乘法中的求逆運算極為耗時，為提高標量乘法的運算效率，很多學者[7~11]把求逆運算轉換為乘法運算。Guajardo等人[10]利用轉換求逆為乘法的思想，提出了仿射坐標下直接計算4P、8P和16P的算法，提高了標量乘法的效率。Sakai等人[9]則拓展了文獻[10]，提出仿射坐標下直接計算2kP的算法。對于給定的P和Q，Ciet等人[7]根據同樣的思想，提出了仿射坐標下直接計算3P+Q的算法，把其運算量降為2I+4S+9M，比計算(3P)+Q節省了一次求逆運算。其中用I、S、M分別表示求逆、平方、乘法運算。此外，文獻[7]還提出了直接計算3P的算法，其運算量為1I+4S+7M，比計算(2P)+P節省了0.6M。
利用轉換求逆為乘法運算的思想，本文提出另一種用仿射坐標直接計算3P+Q的算法，其運算量為1I+3S+16M，比文獻[7]節省了一次求逆運算，相交處(運算量相等時)I/M的值為6.2。另外，本文還提出了用仿射坐標直接計算3kP的算法，其運算量為1I+(7k-1)S+(8k+2)M，比重復計算k次3P節省了k-1次求逆，相交處I/M的值為3.4+(4.6/(k-1))。
1 ECC的基本知識
本章簡單介紹有關ECC的基本知識，詳細內容可參考文獻[1， 2]。
定義 用E表示橢圓曲線，K表示域。而E就是定義在K上的Weierstrass等式
y2+a1xy+a3y=x3+a2x2+a4x+a6(1)
其中：系數a1，a2，a3，a4，a6∈K，且Δ≠0，Δ為E的判別式。但在實際應用中，式(1)往往在素域Fp（p>3）和二進制域F2m下簡化。
本文將討論素域Fp的曲線E：設K定義在素域Fp上，即K=Fp，特征p>3，式(1)可被簡化為
y2=x3+ax2+b (2)
其中：系數a，b∈K且Δ=4a3+27b3 mod p≠0。
E(K)表示定義在域K上的橢圓曲線E的所有點的集合，它是一個Abel群。橢圓曲線E的群運算是按照橢圓曲線群運算法則完成的，其中所涉及的運算有加、減、乘、求逆和平方五種基本運算，用M、S和I分別表示域Fp上的乘法、平方和求逆運算，I/M表示求逆和乘法運算的復雜度比。五種基本運算中，加法和減法相對其他運算來說，所用時間可以忽略不計。求逆運算則是最耗時的，在域Fp上，一般認為I/M >30[11]，且I/M隨著p的增大而增大；而對于平方和乘法，可設定1S=0.8M[12]。
設P=(x1，y1)和Q=(x2，y2)是E(Fp)上的任意兩個非零點，且P≠-Q，R=(x3，y3)=P+Q。下面將給出加點運算和倍點運算的公式。
1.1 加點運算
當P≠Q時，R=P+Q稱為加點運算（簡記為A），在仿射坐標下，R=(x3，y3)可通過式(3)得到：
λ=(y2-y1)/(x2-x1)
x3=λ2-x1-x2， y3=λ(x1-x3)-y1 (3)
由式(3)可知，素域Fp上完成加點運算R=P+Q需要1I+1S+ 2M。
1.2 倍點運算
當P=Q，且P≠O (O表示曲線E的無窮遠點)時，R=2P稱為倍點運算（簡記為D），在仿射坐標下，R=x3，y3可通過式(4)得到：
λ=(3x12+a)/(2y1)
x3=λ2-x1-x2， y3=λ(x1-x3)-y1(4)
由式(4)可知，素域Fp上完成倍點運算R=2P需要1I+2S+2M。
2 Ciet等人計算3P+Q的算法
求逆耗時較多，而標量乘法往往涉及很多求逆運算，所以減少求逆運算，降低ECC的運行時間也成為學者們的研究熱點。
2003年，Eisentrager等人[8]提出一種仿射坐標下直接計算2P+Q的快速算法，通過中間步驟的代換節省了一次平方和一次乘法運算。在此基礎上，Ciet等人[7]利用轉換求逆為乘法運算的思想，把2P+Q的運算量從2I+3S+4M降為1I+2S+9M，使運算效率大大提高。通過上述原理，Ciet等人還對3P、3P+Q、4P和4P+Q等曲線操作進行了研究。表1為文獻[7，8]的不同算結果。
從表1不難看出，在域Fp上，對給定的點P和Q，2P+Q的運算量為1I+2S+9M，并不是(2P)+Q的運算量之和2I+3S+4M(一次倍點和一次加點)，而是通過轉換求逆為乘法，使求逆次數減少了一次，大大提高效率。當然在求逆次數降低的同時，也增加了五次乘法運算，具體細節可參見文獻[7]。
根據同樣的原理，文獻[7]還對3P+Q作了詳細研究。設(x3，y3)=2P，(x4，y4)= P +Q，(x5，y5)= 3P +Q，其步驟如下：
a)通過式(4)計算(x3，y3)=2P
λ1=(3x12+a)/(2y1)
x3=λ12-x1x2， y3=λ1(x1-x3)-y1 (5)
b)通過式(3)計算(x4，y4)= P +Q
λ2=(y2-y1)/(x2-x1)
x4=λ22-x1-x2， y4=λ2(x1-x4)-y1 (6)
c)通過式(3)計算(x5，y5)= 3P +Q
λ3=(y4-y3)/(x4-x3)
x5=λ32-x3-x4， y5=λ3(x3-x5)-y3 (7)
d)把求逆運算轉換為乘法運算。引入公因子λc，λc為λ1和λ2分母的最小公倍數，即λc=(2y1(x1-x2))-1。λ1和λ2可通過λc和幾次額外的乘法求取，(x3，y3)和(x4，y4)可由式(5)和(6)求得，最后再通過式(5)(一次加點運算)得到(x5，y5)。具體如算法1所示。其運算量如表2所示。
算法1: Ciet’s computation of 3P+Q
Input: P=(x1，y1) ≠O and Q=(x2，y2) ≠O
Output: S=3P+Q=(x5，y5)
if(y1=0) then return P+Q
if(x1=x2) then
if(y1=y2) then return 4P
else return 2P
Step1: compute λc， λ1， λ2
λc←((2y1)(x1-x2))-1
λ1←(x1-x2)(3x12+a)λc
λ2←2y1(y1-y2)λc
Step2:compute (x3，y3) and (x4，y4)
x3←λ12-2x1
y3←λ1(x1-x3)-y1
x4←λ22-x1-x2
y4←λ2(x1-x4)-y1
if(x3=x4) then return O
Step3: compute (x5，y5)
λ3←(y1-y4)/(x1-x4)
x5←λ32-x3-x4
y5←λ3(x3-x5)-y3
return (x5，y5)
3 計算3P+Q的新方法
算法1通過引入λc，把求逆運算轉換為乘法運算，即用λc代替2P的λ1和P+Q的λ2，減少一次求逆運算。然而可以再進一步，用λc代替λ1、λ2和λ3，從而將求逆次數從三次降為一次。根據上述思想，本文將提出一種計算3P+Q的新算法。
與算法1一樣，引入公因子λc，λc為λ1、λ2和λ3的分母的最小公倍數，且都為已知項的最簡式。為便于計算，設A1、A2、A3分別表示λ1、λ2、λ3的分母，B1、B2、B3分別表示λ1、λ2、λ3的分子，即A1=2y1，A2=x2-x1，A3=x4-x3，B1=3x12+a，B2=y2-y1，B3=y4-y3，λ1=B1/A1，λ2= B2/A2，λ3=B3/A3。很明顯A1、A2、B1、B2、λ1和λ2已知，A3、B3和λ3未知。
新算法的步驟如下：
a)化簡A3和λ3為最簡式。λ1和λ2已知，故x3、x4可通過式(5)和(6)求得，所以A3=(x4-x3)是關于A1、A2、B1和B2的表達式，通過計算求得：
A3=D/(A1A2)2(8)
其中D=(A1B2+A2B1)(A2B1-A1B2)-A2(A1A2)2。將式(8)代入λ3 = B3 /A3，化簡λ3：
λ3=B3(A1A2)2/D(9)
b)把求逆運算轉換為乘法運算，即求取λc、λ1、λ2和λ3。由于λ1、λ2和λ3都已化簡，且分母都為已知項的最簡式， 可求得λc、λ1、λ2和λ3：
λc=(DA1A2)-1，λ1=DλcA2B1
λ2=DλcA1B2， λ3=B3(A1A2)3λc (10)
c)通過式(5)~(7)計算(x5，y5)。
從上述步驟可知，求逆項只有λc，求逆次數從算法1的2次(λc和λ3)降為一次(λc)。
式(10)中的λ3雖已化簡，但還含有未知項B3，給求取(x5，y5)帶來額外的開銷。下面對其進行優化。
由于x5=(λ32-x3-x4)和y5=(λ3(x3-x5)-y3)中并不含有y4，可再對B3和λ3進行變換：
B3=y4-y3
=λ2(x1-x4)-λ1(x1-x3)
=(x1-x3)(λ1-λ2)-λ2(x4-x3)
把B3代入λ3=B3/A3=(y4-y3)/(x4-x3)：
λ3=((x1-x3)(λ1λ-2))/(x4-x3)-λ2=
(A1A2)3λc(x1-x3)(λ1-λ2)-λ (11)
式(11)中的λ3雖然比式(10)中的λ3增加了一次乘法運算，但前者不再含有x4和y4項。如果再對橫坐標x5=λ32-x3-x4進行變換，消除x4項，這樣就可以在計算3P+Q的過程中省去對(x4，y4)的計算。為此，將x4=λ22-x1-x2代入x5：
x5= (λ3+λ2)(λ3-λ2)+x1+x2-x3
經過變換后，原來計算x5需要的二次平方運算（x4中的λ22和x5中的λ32）變為一次乘法運算，節省了0.6M。算法2如下所示，其運算量如表3所示。
算法2: Our improved computation of 3P+Q
Input: P=(x1，y1)≠O and Q=(x2，y2)≠O
Output: S=3P+Q=(x5，y5)
if(y1=0) then return P+Q
if(x1=x2) then
if(y1=y2) then return 4P
else return 2P
compute λc，λ1，λ2，λ3
A1←2y1
B1←3x12+a
A2←x2-x1
B2←y2-y1
D←(A1B2+A2B1)(A2B1-A1B2)-A2(A1A2)2
λc←(DA1A2)-1
λ1←DλcA2B1
λ2←DλcA1B2
λ3←(A1A2)3λc(x1-x3)(λ1-λ2)-λ2
compute (x3，y3)
x3←λ12-2x1
y3←λ1(x1-x3)-y1
Step3: compute (x5，y5)
x5←(λ3+λ2)(λ3-λ2)+ x1+x2-x3
y5←λ3(x3-x5)-y3
return (x5，y5)
通過計算λc、λ1、λ2、λ3和(x3，y3)，算法2 可得到(x5，y5)= 3P+Q，省去了(x4，y4)=P+Q的計算。經分析，其總運算量為1I+3S+16M，比算法1的2I+4S+9M節省了一次求逆運算。當I/M≥6.2時，算法2比算法1有效。
4 直接計算3kP的新方法
如果標量m表示為3k的形式，那么直接計算3kP將會使效率大大提高，因為它只需要一次求逆。本章給出一種用仿射坐標直接計算3kP的新算法。
2005年，Dimitrov等人 [13]提出了用Jacobian坐標直接計算3kP的方法，但沒有給出計算3kP的方法。Ciet等人[7]給出在仿射坐標下3P的運算量為1I+4S+7M，但也沒對3kP進行深入的研究。以下為文獻[7]計算3P的公式：
X←(2y1)2，Z←3x12+a，Y←Z2
d←X(3x1)-Y， D←d(2y1)，I←D-1
λ1←DIZ， λ2←X2I-λ1
x4←λ22-x1-x2
y4←λ2(x1-x4)-y1(12)
式(12)的運算量為1I+4S+7M，若計算3kP，運算量則為k(1I+4S+7M)。
在Dimitrov等人研究的基礎上，本文提出直接計算3kP的算法，如算法3所示，其運算量如表4所示。
算法3: Direct computation of 3kP in terms of affine coordinates
Input: P=(x1，y1)≠O
Output: S=3kP=(x3k， y3k)
set A0，B0，C0
A0←x1
B0←y1
C0←1
for i from 1 to k compute
Ti， Ni， Di， Ai， Bi，Ci
Ti←8B i-14
Ni←3Bi-14+aCi-14
Di←12Ai-1Bi-12-Ni4
Ai←8Bi-12(Ti-NiDi)+Ai-1Di2
Bi←Bi-1(4(NiDi-Ti)(2Ti-NiDi)-Di3)
Ci←DiCi-1
compute x3k， y3k
x3k←Ak/Ck2
y3k←Bk/Ck3
return (x3k， y3k)
經分析，算法3的運算量為1I+(7k-1)S+(8k+2)M。證明略。
顯然，當計算3P（k=1）時，算法3的運算量為1I+6S +10M，而式(12)則為1I+4S+7M，算法3的效率略低于式(12)。但當計算9P（k=2）時，算法3的運算量為1I+13S+18M，而式(12)為2(1I+4S+7M)，當I/M≥7.2時，算法3效率高于式(12)。若計算3kP，算法3與式(12)重復k次計算3P相比，節省了k-1次求逆運算，相交處I/M=3.4+ (4.6/(k-1))。顯然，隨著k的增大，I/M的值逐漸減小，效率也不斷提升，當k足夠大時，I/M值可降為3.4。
5 標量乘法
前面提出直接計算3P+Q的算法2比文獻[7]節省了1次求逆，而算法3比重復計算k次3P更有成效。本章將把它們運用到橢圓曲線的標量乘法mP中(m為給定的正整數，P是橢圓曲線的點)。
5.1 lNAFw算法
最近，Takagi等人[14]提出了正整數m的lNAFw的編碼方式，即m為l進制和窗口寬度為w的NAF。這種算法和普通的NAFw算法有相似性質，其表達形式為m=ti=0eili。其中t為ei的長度。本文把m的lNAFw表達形式簡記為m=(et…e0)lNAFw，其有關性質可參考文獻[15]。為把本文之前提出的3P+Q和3kP的算法運用到標量mP中，設定l=3，即m=ti=0ei3i=(et…e0)3NAFw，m的3NAFw計算方法如下。
算法4:3NAFw representation
Input: a positive integer m， w>1
Output: m=(et…e0)3NAFw
i←0
while m>0 do
ei←m mod 3w
if ei>3w/2 then ei←ei-3w
m←m-ei
else ei←0
m←m/3 and i←i+1
return((et…e0)3NAFw)
文獻[15]證明了3NAF3的漢明密度(非零個數比)為2/7，長度t=「log3m」。由于ei∈{0，±1…±13}\\{3，6，9，12}，正在3NAF3的標量乘法中，需要預計算2P、4P、5P、7P、8P、10P、11P和13P。
5.2 性能比較與分析
為方便性能分析，對于給定的點P和Q，本文記P+Q運算為A、2P為D、2P+Q為DA、3P為T、3P+Q為TA、3kP為Tk。下面分別以NAF、NAF3、NAF4、Ternary /Binary[7]、3NAF和3NAF3六種方法計算mP，其中m的長度分別為160、192、224和256位。對于給定的m，其3進制的長度t3=「log3m」，2進制的長度t2=「log2m」，故t3=t2/ log23，即160位的2進制和101位的3進制相當，192、224、256位的2進制分別與122、142、162位3進制相當。NAF、NAF3、NAF4、3NAF 和3NAF3的漢明密度分別為1/3、1/4、1/5、2/5和2/7。對于不同長度值的t3和t2，NAF、NAF3、NAF4、3NAF和3NAF3的運算量分別為t2(DA+2D)/3、t2(DA +3D)/4、t2(DA+4D)/5、t3(2TA+3T)/5、(t3/3-1)(T3+A)。至于Ternary/Binary，則參考文獻[16]提供的數據。表3為不同長度的m用不同方法計算mP的運算量，其中設定1S=0.8M，A、DA和T的運算量用表1文獻[7]的數據，TA、Tk的運算量用算法2和3的數據。各運算量結果如表5、6所示。
從表6中不難看出，相同長度下求逆運算次數最少的是3NAF3，最多的則是傳統的NAF。為更詳細地比較它們各自的性能，表7中給出了3NAF3和3NAF與其他方法相交處I/M的值。
從表7中可以看出，當I/M≥5.4時，160位的3NAF3比160位的NAF有效，當I/M≥6.3時，160位的3NAF3比160位的NAF3有效；當I/M≥6.2時，160位的3NAF3比160位的Ternary/Binary有效；同樣，當I/M≥7.0時，160位3NAF比160位的NAF有效。依此類推，當I/M≥10.9時，256位的3NAF比256位的Ternary/Binary有效。故表4中的I/M值也會隨之下降。從表7中還可以看出各列的I/M值變化不大，也就是說I/M的值并不隨長度的變化而變化。
表6中用3NAF計算mP時，用到的群運算只是TA和T，并沒用到Tk，而3NAF3的窗口為3，即也只用到了T3。在實際應用中，(et…e0)3NAF和(et…e0)3NAF3往往會出現連續k個ei為零的情況，這時3NAF可結合直接計算3kP的算法，效率會比連續計算k次3P更有效，而3NAF3的窗口值也可能會增大，I/M的值也會隨之下降。例如，(314 159)3NAFP =(202001000404)P，結合Tk的運算量為4TA+T2+T3+2T，即8I+53S+112M；而只用TA和T的運算量為4TA+7T，即11I+40S+113M。很明顯，前者的效率比后者高。
6 結束語
本文根據轉換求逆運算為乘法運算的思想，研究橢圓曲線(基于域Fp)用仿射坐標直接計算3P+Q的新算法結果表明：3P+Q的運算量為1I+3S+16M，比文獻[7]節省了一次求逆運算，當I/M≥6.2時，新算法更有效。利用相同的原理，還提出了直接計算3kP(k≥2)的算法，其運算量為1I+(7k-1)S+(8k+2)M，比連續計算k次3P節省了k-1次求逆運算，其I/M的值為3.4+(4.6/(k-1))，當k的值足夠大時，I/M的值可為3.4。最后結合3NAFw，把新算法應用到標量乘法，與NAF、NAF3、NAF4和Ternary/Binary相比，3NAF和3NAF3的優勢較為明顯，與傳統的NAF相比，相交處的I/M值甚至降為5.4。在實際應用中，因為分解序列會涉及更多連續的零，所以I/M值還會更小。還可得知I/M的值與所使用的方法有關，而與m的長度無關。
另外，本文中的3P+Q和3kP的算法也可在域F2m上進行改進。當DBNS(double base number system)[16]結合本文的新算法時，其效率也會大大提高。
參考文獻：
［1］KOBLITZ N. Elliptic curve cryptosystems[J]. Mathematics of Computation， 1987， 48(177): 203209.
[2]MILLER V. Uses of elliptic curves in cryptography[C]//Advances in’ Cryptology CRYPTO’85.[S.l.]: SpringerVerlag， 1986:417426.
[3]RSA Laboratories. Highspeed RSA implementation， Teachnical Report TR201[R].[S.l.]: RSA Data Security， 1994.
[4]AVANZI R M， COHEN H， DOCHE C，et al. Handbook of elliptichyperelliptic curve cryptography[M].[S.l.]:CRC Press， 2005.
[5]BLAKE I F，SEROUSSI G， SMART N P. Elliptic curves in cryptography[M].New York: Cambridge University Press， 1999.
[6]HANKERSON D， MENEZES A， VANSTONE S. Guide to elliptic curve cryptography[M]. [S.l.]:SpringerVerlag， 2004.
[7]CIET M， JOYE M， LAUTER K，et al. Trading inversions for multiplications in elliptic curve cryptography[J].Designs， Codes and Cryptography， 2006，39(2):189206.
[8]EISENTRAGER K， LAUTER K， MONTGOMERY P L. Fast elliptic curve arithmetic and improved Weil pairing evaluation[C]// JOYE M. Proc ofCTRSA’03. [S.l.]: SpringerVerlag，2003:343354.
[9]SAKAI Y， SAKURAI K. Efficientscalar multiplications on elliptic curves with direct computerations of several doublings[J]. IEICE Trans on Fundamentals， 2001:120129.
[10]GUAJARDO J， PAAR C. Efficent algorithms for elliptic curve cryptosystems[C]//Proc of the 17th Annual International Cryptology Conference on Advances in Cryptology.London:SpringerVerlag，1997: 328340.
[11]FONG K， HANKERSON D， LOPEZ J，et al. Field inversion and point halving revisited[J]. IEEE Trans on Computers， 2004， 53(8): 10471059.
[12]HANKERSON D， HERNANDEZ J L， MENEZES A. Software implementation of elliptic curve cryptography over binary [C]//Proc of the 2nd International Workshop on Cryptographic Hardware and Embedded Systems .London: SpringerVerlag，1999: 124.
[13]DIMITROV V S， IMBERT L， MISHRA P K. Efficient and secure elliptic curve point multiplication using doublebase chains[C]//Proc ofASIACRYPT 2005.Berlin:SpringerVerlag，2005: 5978.
[14]TAKAGI T， YEN S M， WU B C. Radixr nonadjacent form[C]// Information Security ConferenceISC 2004.Berlin:SpringerVerlag，2004:99110.
[15]DOCHE C， ICART T， KOHEL D R. Efficient scalar multiplication by isogeny decompositions[C]//Proc of Public Key Cryptography， PKC’06.[S.l.]:SpringerVerlag，2006:191206.
[16]DIMITROV V S， IMBERT L， MISHRA P K. Fast elliptic curve point multiplication using doublebase chains， Report 2005/069[R].2005.
