一種低復(fù)雜度的改進(jìn)wNAF標(biāo)量乘算法

趙石磊，楊曉秋，劉志偉，于 斌，黃 海

（哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱 150080）

1 引言

橢圓曲線密碼體制的核心運(yùn)算主要是橢圓曲線群上的標(biāo)量乘法，它的運(yùn)算速度決定著密碼系統(tǒng)整體執(zhí)行效率［1］. 一般來(lái)說(shuō)，標(biāo)量乘算法可分為兩種：無(wú)預(yù)計(jì)算算法和有預(yù)計(jì)算算法. 無(wú)預(yù)計(jì)算算法包括二進(jìn)制算法（Double and Add，D&A）［2］、非鄰接表示算法（Non-Adjacent Form，NAF）［3］、多基鏈表算法（Double-Base Chain，DBC）［4］和相反形式算法（Mutual Opposite Form，MOF）［5］等，這些算法大都存在著計(jì)算復(fù)雜度過(guò)高的問(wèn)題. 為降低計(jì)算復(fù)雜度，學(xué)者們提出了有預(yù)計(jì)算算法，如滑動(dòng)窗口算法［6］、窗口非相鄰算法（window width-Non-Adjacent Form，wNAF）［7］、加法鏈算法［8］、利用素?cái)?shù)代替奇數(shù)進(jìn)行預(yù)計(jì)算并通過(guò)構(gòu)建多基鏈來(lái)彌補(bǔ)素?cái)?shù)與奇數(shù)之間的差值算法［9］、帶門(mén)限的動(dòng)態(tài)窗口的NAF 標(biāo)量乘法［10］等. 文獻(xiàn)［8］所提加法鏈算法相比較其他加法鏈算法計(jì)算復(fù)雜度降低了4%～18%. 文獻(xiàn)［9］的計(jì)算復(fù)雜度相比于wNAF 優(yōu)化了28.37%. 在文獻(xiàn)［10］中，帶門(mén)限的動(dòng)態(tài)窗口的NAF 標(biāo)量乘法的預(yù)計(jì)算量?jī)H為基于Moller 碎片窗口技術(shù)的標(biāo)量乘法的30%、基于固定窗口改進(jìn)后的NAF 標(biāo)量乘法的25%，其預(yù)計(jì)算利用率比基于Moller 碎片窗口技術(shù)的標(biāo)量乘法提高了15%左右，比基于固定窗口改進(jìn)后的NAF標(biāo)量乘法提高了12%左右. 文獻(xiàn)［11］則提出了Alternate-Zeckendorf 表示算法，可以用加法鏈序列表示任何標(biāo)量k，此算法比其他算法的成本至少降低12.7%. 文獻(xiàn)［12］提出了基于窗口的NAF 算法，當(dāng)n={192，224，256，384}時(shí)，預(yù)計(jì)算效率提高了26.35%，當(dāng)n=521時(shí)，預(yù)計(jì)算效率提高33.59%.

以上算法雖然取得了較好的結(jié)果，能夠有效降低標(biāo)量k的漢明重量，減少點(diǎn)加操作的次數(shù)，降低標(biāo)量乘的計(jì)算復(fù)雜度，但是仍然存在著不適用于窗口寬度較大、使用寄存器較多、預(yù)計(jì)算量過(guò)大等問(wèn)題. 針對(duì)以上問(wèn)題，本文設(shè)計(jì)了一種低復(fù)雜度的改進(jìn)wNAF 算法，首先在預(yù)計(jì)算階段用2nP替換(2h-1)P（wNAF 算法中奇數(shù)與基點(diǎn)P的乘積），再用2nP構(gòu)造加法鏈來(lái)補(bǔ)償2nP與(2h-1)P之間的差值. 然后，為解決隨著窗口寬度的增大，2nP與(2h-1)P之間差值過(guò)大的問(wèn)題，采用有符號(hào)的wNAF 算法將標(biāo)量k的二進(jìn)制鏈轉(zhuǎn)換成有符號(hào)的wNAF 鏈，能將該差值范圍縮小為原來(lái)的50%，極大地減少了點(diǎn)加次數(shù). 最后，實(shí)驗(yàn)結(jié)果證明，所設(shè)計(jì)的算法具有所需寄存器數(shù)量少以及計(jì)算復(fù)雜度低等優(yōu)點(diǎn).

2 橢圓曲線標(biāo)量乘算法分析

2.1 窗口非相鄰（wNAF）標(biāo)量乘

橢圓曲線標(biāo)量乘法是橢圓曲線密碼系統(tǒng)中最關(guān)鍵（也是消耗資源和能量最多）的步驟，是橢圓曲線上一個(gè)點(diǎn)P與一個(gè)隨機(jī)的整數(shù)k的乘積，即Q=kP=P+P+…+P. 由于在雅可比坐標(biāo)下，倍點(diǎn)的運(yùn)算消耗小于點(diǎn)加，因此通常做法是將k進(jìn)行轉(zhuǎn)換以減少其中點(diǎn)加次數(shù)，如wNAF 標(biāo)量乘算法［13］. wNAF 標(biāo)量乘算法通過(guò)將二進(jìn)制形式的標(biāo)量k轉(zhuǎn)化為wNAF 形式，構(gòu)建一條wNAF 鏈，即其中ki∈{±1，±3，…，±(2w-1)}，m表示wNAF 鏈中的非零數(shù)字個(gè)數(shù)，λi是wNAF 鏈中每個(gè)非零數(shù)ki所在的位置. 實(shí)現(xiàn)標(biāo)量乘時(shí)，通過(guò)調(diào)用已預(yù)計(jì)算并存儲(chǔ)的點(diǎn){±P，±3P，…，±(2w-1)P}，其中w是窗口寬度，可極大地減少運(yùn)算時(shí)的計(jì)算量.wNAF 的具體實(shí)現(xiàn)如算法1所示.

該算法整個(gè)過(guò)程分成3 個(gè)階段：wNAF 序列生成階段（步驟1 到步驟12）、預(yù)計(jì)算階段（步驟13）和算數(shù)運(yùn)算階段（算數(shù)運(yùn)算包括點(diǎn)加運(yùn)算和倍點(diǎn)運(yùn)算，步驟14到步驟20）.wNAF 是通過(guò)降低標(biāo)量k的漢明權(quán)重、減少點(diǎn)加運(yùn)算來(lái)降低算法的復(fù)雜度. 假設(shè)在wNAF 鏈{ki}中有非零數(shù)字m個(gè)，第i個(gè)非零數(shù)字是ki，λi是wNAF 鏈中每個(gè)ki所在的位置，則有λi-λi-1≥w+1，顯然，wNAF 的非零概率為1( )w+1，預(yù)計(jì)算階段和算數(shù)運(yùn)算階段的成本分別為2w-1A+D 和，所以標(biāo)量乘計(jì)算量為，其中A 是點(diǎn)加運(yùn)算，D 是倍點(diǎn)運(yùn)算，且有1A=12M+4S，1D=4M+6S［14］以及0.8M=1S［15］（M 是模乘運(yùn)算，S 是模平方運(yùn)算）. 然而，wNAF 標(biāo)量乘算法也存在一定的問(wèn)題：當(dāng)窗口寬度增大的時(shí)候，預(yù)計(jì)算點(diǎn)的個(gè)數(shù)呈指數(shù)增長(zhǎng)，大大增加了預(yù)計(jì)算量和所需的寄存器數(shù)量.

算法1 帶符號(hào)的wNAF標(biāo)量乘算法輸入:標(biāo)量k,基點(diǎn)P,窗口寬度w輸出:標(biāo)量乘結(jié)果Q 1)i=0 2) While k ＞0 do 3) If k mod 2=1 then ei=k mod 2w+1;4) If ei ≥2w then ei ?ei-2w+1;5) End if 6) k ?k-ei;7) Else 8) ei=0;9) End if 10) k ?k/2; i ?i+1;11)End while 12)return{ki-1，ki-2，…，k1，k0}13)預(yù)計(jì)算:Pi=iP，i ∈{1，3，5，…，2w-1}14)for i from b-1 to 0 do 15) Q ?2Q;16) If ki ≠0 then 17) If ki ＞0 then Q ?Q+Pki;18) If ki ＜0 then Q ?Q-Pki;19) End 20)End

2.2 加法鏈標(biāo)量乘算法

文獻(xiàn)［16］進(jìn)行加法鏈標(biāo)量乘運(yùn)算時(shí)，首先構(gòu)造一條加法鏈，定義為一個(gè)序列v=(v1，v2，…，vl)，其中，v1=1，v2=2，vi=vi-1+vi-2(3 ≤i≤l)，l是加法鏈的長(zhǎng)度，標(biāo)量k由加法鏈序列中若干個(gè)vi組成，表示成其次，將vi與基點(diǎn)P相乘并存儲(chǔ)；最后，只需點(diǎn)加操作即可得到標(biāo)量乘的最終結(jié)果. 加法鏈標(biāo)量乘算法如算法2所示.

算法2 加法鏈標(biāo)量乘算法輸入:標(biāo)量k,基點(diǎn)P輸出:標(biāo)量乘結(jié)果Q 1)通過(guò)貪心算法得到k的加法鏈(v1，v2，…，vl)2)Q ?0;3)for i from 1 to l do 4) Q ?Q+vi;5)end 6)return Q

如算法2所示，步驟1是得到k的加法鏈的過(guò)程，貪心算法用于每次在加法鏈中尋找最接近ki的元素vi，然后再利用ki和vi的差值在加法鏈中找到最接近該差值的vi，進(jìn)而可以得到標(biāo)量k的加法鏈；步驟2～6是計(jì)算標(biāo)量乘的過(guò)程，這部分只需要進(jìn)行點(diǎn)加操作而不需要進(jìn)行倍點(diǎn)操作即可得到標(biāo)量乘的結(jié)果. 此外，由于生成k的加法鏈需要用到貪心算法，隨著k位數(shù)的增加，創(chuàng)建加法鏈所用的時(shí)間也會(huì)越長(zhǎng).

3 低計(jì)算復(fù)雜度的wNAF算法設(shè)計(jì)

3.1 基于2n p預(yù)計(jì)算

眾所周知，wNAF 算法在預(yù)計(jì)算階段將{±P，±3P，…， ±(2w- 1)P}存儲(chǔ)起來(lái)用于加速標(biāo)量乘的計(jì)算，但隨著窗口寬度w的增大，預(yù)計(jì)算點(diǎn)的個(gè)數(shù)呈指數(shù)增長(zhǎng)，使得該算法不適用于窗口寬度較大的情況. 本部分針對(duì)該問(wèn)題，對(duì)wNAF 算法進(jìn)行改進(jìn)，減少預(yù)計(jì)算點(diǎn)以降低wNAF算法的標(biāo)量乘計(jì)算復(fù)雜度.

由于倍點(diǎn)運(yùn)算相較于點(diǎn)加運(yùn)算、3 倍點(diǎn)運(yùn)算和5 倍點(diǎn)運(yùn)算需要較少的模乘次數(shù)，同時(shí)由于2n構(gòu)成的集合中元素比3n，5n構(gòu)成的集合中元素更加密集，2n與奇數(shù)之間的差值更小，有利于構(gòu)造差值的加法鏈. 此外，考慮到在進(jìn)行算數(shù)運(yùn)算時(shí)也需要進(jìn)行倍點(diǎn)運(yùn)算，倍點(diǎn)運(yùn)算結(jié)構(gòu)可以通過(guò)控制器控制，反復(fù)利用，節(jié)省資源. 本文的思路是：在預(yù)計(jì)算階段用2n代替生成的wNAF鏈中的奇數(shù)，只預(yù)計(jì)算并存儲(chǔ)2nP. 這種替換的優(yōu)勢(shì)在于能夠大大減少預(yù)計(jì)算點(diǎn)的個(gè)數(shù)且預(yù)計(jì)算點(diǎn)只需要通過(guò)倍點(diǎn)運(yùn)算即可得到. 例如：當(dāng)窗口為5時(shí)，wNAF 算法需要存儲(chǔ){P，3P，…，31P}，共計(jì)16 個(gè)點(diǎn)；而本文算法只需要存儲(chǔ){20P，21P，…，25P}，共計(jì)6個(gè)點(diǎn). 表1列出了在不同窗口寬度下所需預(yù)計(jì)算的點(diǎn)及個(gè)數(shù).

表1 預(yù)計(jì)算點(diǎn)及個(gè)數(shù)

3.2 基于2n p的加法鏈的差值補(bǔ)償

由3.1 節(jié) 中 可 知，用{20P，21P，…，2nP} 代 替{P，3P，…，(2w-1)P}會(huì)產(chǎn)生差值. 例如當(dāng)窗口寬度為w=5 時(shí)，本文預(yù)計(jì)算點(diǎn)為{20P，21P，…，25P}，wNAF 算法預(yù)計(jì)算點(diǎn)為{P，3P，…，31P}，若wNAF 鏈中存在非零數(shù)17時(shí)，24P與17P最接近，但存在差值P；當(dāng)wNAF鏈中存在非零數(shù)21 時(shí)，24P與21P最接近，存在差值5P；當(dāng)wNAF鏈中存在非零數(shù)23時(shí)，24P與23P最接近，存在差值7P.不同窗口寬度下的預(yù)計(jì)算點(diǎn)與wNAF 預(yù)計(jì)算點(diǎn)之間可能存在的差值如表2所示.

由表2 可知，本文預(yù)計(jì)算與wNAF 預(yù)計(jì)算之間的差值為奇數(shù)，且隨著窗口寬度的增加，該差值的最大值也不斷增加，當(dāng)窗口寬度在5～11范圍內(nèi)時(shí)，差值的最大值為511P.

表2 本文預(yù)計(jì)算點(diǎn)與wNAF預(yù)計(jì)算點(diǎn)之間的差值

由于任意一個(gè)標(biāo)量k都可以用二進(jìn)制表示并且在預(yù)計(jì)算階段已經(jīng)完成了對(duì)2nP的計(jì)算和存儲(chǔ)，因此2nP與(2h-1)P之間的差值Δ可以通過(guò)構(gòu)造2nP加法鏈來(lái)補(bǔ)償. 由第2.2 節(jié)可知，加法鏈?zhǔn)菍⒁粋€(gè)大數(shù)拆分成若干個(gè)小數(shù)，在計(jì)算時(shí)，通過(guò)若干個(gè)小數(shù)相加減得到結(jié)果.因此，差值Δ 可以基于加法鏈的思想由多個(gè)2nP相加減得到，即Δ=∑2nP. 例如：在窗口寬度為w=5 時(shí)，已知wNAF 鏈中存在非零數(shù)13，且已有預(yù)計(jì)算點(diǎn){20P，21P，22P，23P，24P，25P}找到與13P最接近的24P，24P與13P之間的差值為3P，3P則可以表示為22P-20P，最終13P=24P-22P+20P. 此外，根據(jù)表2，當(dāng)窗口寬度為11 時(shí)，構(gòu)造的加法鏈最長(zhǎng)，需要4 次點(diǎn)加運(yùn)算，例如：差值為299P時(shí)，299P的加法鏈可以構(gòu)造為299P=28P+25P+23P+21P+20P.

3.3 改進(jìn)的wNAF標(biāo)量乘算法

根據(jù)第3.1 節(jié)和第3.2 節(jié)，可以總結(jié)出本文的算法：通過(guò)算法1生成wNAF鏈，用2n代替wNAF鏈中的奇數(shù)，在預(yù)計(jì)算階段，將2nP預(yù)計(jì)算出來(lái)，在算數(shù)運(yùn)算階段，通過(guò)搜索k鏈中的非零數(shù)值ki，2nP與kiP之間的差值通過(guò)構(gòu)建微小的2nP加法鏈來(lái)實(shí)現(xiàn)，最后再通過(guò)一系列的點(diǎn)加運(yùn)算和倍點(diǎn)運(yùn)算，得到標(biāo)量乘的最終結(jié)果. 改進(jìn)的wNAF標(biāo)量乘算法如算法3所示.

算法3 中，步驟1～2 是預(yù)計(jì)算部分，根據(jù)窗口的大小預(yù)計(jì)算2nP；步驟3～37 是算數(shù)運(yùn)算階段. 步驟8～10用于尋找與wNAF 鏈中非零數(shù)值最接近的2nP，此時(shí)，在查找k鏈時(shí)會(huì)分成兩種情況，一種是k鏈中的非零數(shù)值小于0 的情況，執(zhí)行步驟11～22；另一種是k鏈中的非零數(shù)值大于0 的情況，執(zhí)行步驟23～34. 此外，步驟11～12 以及步驟23～24 用于得到2nP和(2h-1)P之間的差值Δ；步驟14～19 以及步驟26～31 是構(gòu)造差值Δ 的加法鏈的過(guò)程，先找到與Δ 接近的2nP，計(jì)算它們的差值，再找到與該差值接近的2nP，以此類(lèi)推，迭代找到構(gòu)成Δ的2nP加法鏈add1，最終得到標(biāo)量乘結(jié)果.

算法3 改進(jìn)的wNAF的標(biāo)量乘算法輸入:標(biāo)量k,基點(diǎn)P,窗口寬度w輸出:標(biāo)量乘結(jié)果Q 1)預(yù)計(jì)算:2) Pi=2iP，i ∈{0，1，2，…，w}3)標(biāo)量乘計(jì)算:4) Q ?0;add1 ?0;5) for i from b-1 to 0 do 6) Q ?2Q;7) add1 ?0;8) If ki ≠0 then 9) s ?Findnearst(|kiP|) //找到最接近|kiP|的2nP;10) add ?Findnearst(|kiP|);11) If ki ＜0 12) a ?kiP+s;13) j ?0;14) While(a ≠0)15) tj ?Findnearst(|a|);16) a ?|a|-tj 17) j ?j+1;18) End 19) add1 ?∑tj;20) If a ≥0 then add ?add1-add;21) Else add ?-add-add1;22) End 23) If ki ＞0 24) a ?kiP-s;25) j ?0;26) While(a ≠0)27) tj ?Findnearst(|a|);28) a ?|a|-tj 29) j ?j+1;30) End 31) add1 ?∑tj;32) If a ≥0 then add ?add-add1;33) Else add ?-add-add1 34) End 35) Q ?Q+add;36) End 37) End

3.4 算法計(jì)算復(fù)雜度分析

結(jié)合第3.1 節(jié)、第3.2 節(jié)、第3.3 節(jié)得到的本文算法，下面對(duì)算法的復(fù)雜度進(jìn)行分析.

預(yù)計(jì)算部分：計(jì)算2nP時(shí)，窗口寬度為w，則需要進(jìn)行w次倍點(diǎn)，例如，當(dāng)w=5時(shí)，預(yù)計(jì)算點(diǎn)為{20P，21P，…，25P}，需要進(jìn)行5次倍點(diǎn)，所以預(yù)計(jì)算的成本為

算數(shù)運(yùn)算部分：設(shè)wNAF 鏈長(zhǎng)為n，則需要進(jìn)行n次倍點(diǎn)操作，由文獻(xiàn)［12］可知wNAF 的漢明重量為則k鏈中一共有個(gè)非零數(shù)字，需要進(jìn)行次點(diǎn)加，當(dāng)窗口寬度w=5 時(shí)，在構(gòu)建2nP與(2h-1)P差值的加法鏈時(shí)，需要額外進(jìn)行一次點(diǎn)加運(yùn)算的點(diǎn)的個(gè)數(shù)占k鏈中非零數(shù)字的1/4，需要額外進(jìn)行兩次點(diǎn)加運(yùn)算的點(diǎn)的個(gè)數(shù)占k鏈中非零數(shù)字的3/4，因此需要額外進(jìn)行次點(diǎn)加運(yùn)算，一共需要進(jìn)行次點(diǎn)加運(yùn)算，并且窗口寬度每增加1，點(diǎn)加次數(shù)多增加，算數(shù)運(yùn)算階段一共所需的成本為

標(biāo)量乘部分：標(biāo)量乘成本=預(yù)計(jì)算成本+算數(shù)運(yùn)算成本，即

通過(guò)將1A=12M+4S，1D=4M+6S［14］以及0.8M=1S［15］代入到式（1）、式（2）和式（3）可以得到以模乘次數(shù)為標(biāo)準(zhǔn)的預(yù)計(jì)算計(jì)算復(fù)雜度、算數(shù)運(yùn)算計(jì)算復(fù)雜度和標(biāo)量乘計(jì)算復(fù)雜度，結(jié)果如圖1所示.

圖1 表示了以模乘次數(shù)為標(biāo)準(zhǔn)的本文算法在不同窗口寬度、不同曲線下的計(jì)算復(fù)雜度曲線. 計(jì)算復(fù)雜度包括預(yù)計(jì)算計(jì)算復(fù)雜度、算數(shù)運(yùn)算計(jì)算復(fù)雜度和標(biāo)量乘計(jì)算復(fù)雜度；曲線包括P256，P384和P521，窗口寬度范圍為2～12. 由圖1可以看出，對(duì)于所有曲線，窗口寬度為11時(shí)，標(biāo)量乘計(jì)算復(fù)雜度最??；窗口寬度小于5時(shí)，標(biāo)量乘計(jì)算復(fù)雜度要高于窗口寬度為5時(shí). 而當(dāng)窗口寬度大于11時(shí)，由于2nP與(2h-1)P之間的差值過(guò)大，不利于構(gòu)建基于2nP的加法鏈. 根據(jù)以上結(jié)果，本文后面對(duì)算法的比較與分析都將窗口寬度限制在5～11的范圍內(nèi).

圖1 低復(fù)雜度的改進(jìn)wNAF標(biāo)量乘算法在不同窗口下的計(jì)算復(fù)雜度分析

4 算法計(jì)算復(fù)雜度比較

4.1 預(yù)計(jì)算計(jì)算復(fù)雜度比較

為了更直觀、更清晰地觀察本文算法在預(yù)計(jì)算方面有優(yōu)勢(shì)，將提出的算法與目前研究比較多的wNAF 算法［17］、滑動(dòng)窗口非相鄰形式算法（swNAF算法）［18］和基于素?cái)?shù)預(yù)計(jì)算的算法［9］進(jìn)行了比較，比較結(jié)果如表3所示.

由表3 可以看出，相較于wNAF 算法、swNAF 算法和基于素?cái)?shù)預(yù)計(jì)算的算法，本文算法在窗口寬度為5～11 時(shí)預(yù)計(jì)算點(diǎn)的個(gè)數(shù)減少，而在窗口寬度為11 時(shí)預(yù)計(jì)算點(diǎn)個(gè)數(shù)減少最多，分別減少了1 013 個(gè)、330 個(gè)和204個(gè)，減少的百分比分別為98.83%，96.49%和94.42%. 此外，當(dāng)窗口寬度增加時(shí)，本文算法的預(yù)計(jì)算點(diǎn)的數(shù)量減少的百分比也隨之增加，說(shuō)明本算法比其他算法更適用于窗口寬度較大的情況.

表3 預(yù)計(jì)算點(diǎn)比較

表4 顯示了當(dāng)窗口寬度為5～11 時(shí)預(yù)計(jì)算點(diǎn)所需的模乘次數(shù)的比較，其中，倍點(diǎn)運(yùn)算（用D 表示）根據(jù)1D=4M+6S 以及0.8M=1S 進(jìn)行轉(zhuǎn)換. 從表4 可以看出，相較于wNAF 算法、swNAF 算法和基于素?cái)?shù)預(yù)計(jì)算的算法，在窗口寬度為5 時(shí)，本文算法在預(yù)計(jì)算的模乘次數(shù)分別減少了81.95%，70.19%和74.19%，在窗口寬度為11 時(shí)，預(yù)計(jì)算的模乘次數(shù)分別減少了99.38%，99.07%和97.83%. 由此可知，在窗口寬度5～11 時(shí)，本文算法的預(yù)計(jì)算復(fù)雜度最低. 此外，隨著窗口寬度的增加，本文算法預(yù)計(jì)算所需模乘次數(shù)減少的百分比也隨之增加，也說(shuō)明了本文算法更適用于較大窗口.

表4 預(yù)計(jì)算點(diǎn)所需的模乘次數(shù)比較

4.2 標(biāo)量乘計(jì)算復(fù)雜度比較

標(biāo)量乘計(jì)算復(fù)雜度包括了預(yù)計(jì)算計(jì)算復(fù)雜度以及算數(shù)運(yùn)算計(jì)算復(fù)雜度兩部分，在第4.1節(jié)已經(jīng)對(duì)預(yù)計(jì)算計(jì)算復(fù)雜度進(jìn)行了對(duì)比，表5 顯示了當(dāng)n為256，384，521 時(shí)，4 種算法的算數(shù)運(yùn)算計(jì)算復(fù)雜度和標(biāo)量乘計(jì)算復(fù)雜度對(duì)比. 由表5 可以看出，本文算法在算數(shù)運(yùn)算部分的計(jì)算復(fù)雜度與其他3種算法相當(dāng)，但窗口寬度增加時(shí)，本文算法的預(yù)計(jì)算優(yōu)勢(shì)越明顯. 并且隨著窗口寬度增大，在相同位數(shù)下，有符號(hào)wNAF 鏈中非零個(gè)數(shù)相比無(wú)符號(hào)wNAF 鏈中更少，這也進(jìn)一步減少點(diǎn)加次數(shù)，從而降低標(biāo)量乘的計(jì)算復(fù)雜度. 此外，在窗口寬度較大時(shí)w=11 時(shí)，本文算法的標(biāo)量乘計(jì)算復(fù)雜度相較于wNAF算法、swNAF 算法和基于素?cái)?shù)預(yù)計(jì)算算法降低了最多，分別為78.23%，68.94%和43.63%.

表5 4種算法總體計(jì)算復(fù)雜度對(duì)比

5 結(jié)論

本文提出了在有符號(hào)wNAF算法的基礎(chǔ)上，在預(yù)計(jì)算階段采用2nP替換(2h-1)P，替換后的差值采用2nP構(gòu)造的加法鏈進(jìn)行補(bǔ)償，該方法有效降低了預(yù)計(jì)算復(fù)雜度，并且只需要少量的寄存器即可完成預(yù)計(jì)算點(diǎn)的存儲(chǔ)，進(jìn)而解決了有預(yù)計(jì)算算法不適用于窗口很大的問(wèn)題. 與現(xiàn)有的算法相比，預(yù)計(jì)算所需模乘數(shù)相較于wNAF 算法、swNAF 算法和基于素?cái)?shù)預(yù)計(jì)算算法最多減少了99.38%，99.07%和97.83%，標(biāo)量乘的計(jì)算復(fù)雜度分別降低了78.23%，68.94%和43.63%.