国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

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

2022-05-17 04:19:32趙石磊楊曉秋劉志偉
電子學(xué)報(bào) 2022年4期
關(guān)鍵詞:算數(shù)標(biāo)量差值

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

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

1 引言

橢圓曲線(xiàn)密碼體制的核心運(yùn)算主要是橢圓曲線(xià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 橢圓曲線(xiàn)標(biāo)量乘算法分析

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

橢圓曲線(xiàn)標(biāo)量乘法是橢圓曲線(xiàn)密碼系統(tǒng)中最關(guān)鍵(也是消耗資源和能量最多)的步驟,是橢圓曲線(xià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)的本文算法在不同窗口寬度、不同曲線(xiàn)下的計(jì)算復(fù)雜度曲線(xiàn). 計(jì)算復(fù)雜度包括預(yù)計(jì)算計(jì)算復(fù)雜度、算數(shù)運(yùn)算計(jì)算復(fù)雜度和標(biāo)量乘計(jì)算復(fù)雜度;曲線(xiàn)包括P256,P384和P521,窗口寬度范圍為2~12. 由圖1可以看出,對(duì)于所有曲線(xiàn),窗口寬度為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%.

猜你喜歡
算數(shù)標(biāo)量差值
差值法巧求剛體轉(zhuǎn)動(dòng)慣量
一種高效的橢圓曲線(xiàn)密碼標(biāo)量乘算法及其實(shí)現(xiàn)
一屋三室
放學(xué)后(2019年4期)2019-09-10 07:22:44
說(shuō)話(huà)要算數(shù)
秋天不會(huì)算數(shù)
一種靈活的橢圓曲線(xiàn)密碼并行化方法
人生沒(méi)有白走的路,每一步都算數(shù)
海峽姐妹(2017年8期)2017-09-08 12:16:45
枳殼及其炮制品色差值與化學(xué)成分的相關(guān)性
中成藥(2017年6期)2017-06-13 07:30:35
基于區(qū)域最大值與平均值差值的動(dòng)態(tài)背光調(diào)整
單調(diào)Minkowski泛函與Henig真有效性的標(biāo)量化
404 Not Found

404 Not Found


nginx
增城市| 喀什市| 泌阳县| 青州市| 宝山区| 澄城县| 杭锦后旗| 牙克石市| 尖扎县| 屯昌县| 四川省| 荔波县| 蒲江县| 馆陶县| 上蔡县| 唐山市| 云安县| 神池县| 义马市| 揭东县| 宁蒗| 淳安县| 来凤县| 水富县| 克拉玛依市| 道孚县| 永年县| 霞浦县| 土默特右旗| 宁安市| 两当县| 精河县| 个旧市| 桂阳县| 元氏县| 邵阳市| 双城市| 揭东县| 类乌齐县| 长泰县| 罗山县|