最短加法鏈的算法研究

張仕昌，陳 陽

（1.遼寧工業(yè)大學(xué) 電氣工程學(xué)院，遼寧 錦州 121001；2.遼寧工業(yè)大學(xué) 理學(xué)院，遼寧 錦州 121001）

模指數(shù)的冪運(yùn)算是公鑰密碼學(xué)中的核心運(yùn)算之一，運(yùn)行效率直接影響著公鑰密碼體制的執(zhí)行速度，加法鏈則能應(yīng)用到模指數(shù)的冪運(yùn)算中[1]。同時(shí)，加法鏈也被應(yīng)用到橢圓曲線密碼中改進(jìn)點(diǎn)乘運(yùn)算的效率[2-4]。加法鏈相關(guān)問題的研究是密碼學(xué)等相關(guān)研究領(lǐng)域中的熱門問題[5-6]，下面討論了計(jì)算加法鏈的2 種算法：二叉樹加法鏈和基于貪心算法的逐步回溯法，并用2 種算法求解了競賽中提出的第一類和第二類挑戰(zhàn)參數(shù)的最短加法鏈。

一個(gè)長為7的可計(jì)算34 的加法鏈為1-2-4-8-16-32-34?？捎?jì)算254 的加法鏈有1-2-4-8-16-32-64-80-84-168-252-254，1-2-4-8-16-32-64-80-84-168-254，1-2-4-8-16-32-48-50-54-100-200-254 等。對(duì)于給定的一個(gè)數(shù)n，可以有幾條加法鏈，找到的可計(jì)算n的加法鏈越短越好。

1 加法鏈問題

定義1(加法鏈)正整數(shù)n的長度為s的加法鏈(addition chain)U是一個(gè)嚴(yán)格遞增的正整數(shù)序列滿足：

其中：

2 二叉樹加法鏈

定義2星型加法鏈?zhǔn)且粋€(gè)加法鏈，且滿足。

定義3二叉樹加法鏈，滿足：

對(duì)于任意正整數(shù)n，二叉樹加法鏈算法如下：

例如正整數(shù)34 的二叉樹加法鏈(0,2,1,2,1,2)，對(duì)應(yīng)為：

即加法鏈為1-2-3-4-7-9-16-18-34。

求解密碼數(shù)學(xué)競賽中第二類挑戰(zhàn)問題參數(shù)：n=211108170305887，得到加法鏈長度為59，最短加法鏈為 1-2-3-4-8-16-32-64-128-256-512-1024-2048-4096-8192-16384-32768-65536-131072-262144-524288-1048576-2097152-4194304-8388608-16777 216-33554432-67108864-134217728-268435456-536 870912-1073741824-2147483648-4294967296-85899 34592-17179869184-34359738368-68719476736-137 438953472-274877906944-549755813888-10995116 27776-2199023255552-4398046511104-87960930222 08-17592186044416-35184372088832-70368744177 664-140737488355328-211106232532992-211107306 274816-211107843145728-211108111581184-211108 145135616-211108161912832-211108170301440-211 108170305536-211108170305792-211108170305856-211108170305888。

3 基于貪心算法的逐步回溯法

貪心算法(greedy algorithm)是一種算法技術(shù)，總是做出在當(dāng)前來說是最好的選擇，而并不從整體上加以考慮，所做出的每步選擇只是當(dāng)前步驟的局部最優(yōu)選擇。

對(duì)于最短加法鏈問題，目標(biāo)是盡快找到正整數(shù)n，利用貪心算法，每一次都把當(dāng)前值的2 倍作為下一個(gè)值，如果超過目標(biāo)正整數(shù)n，則使用當(dāng)前的最大值與次大值之和作為下一個(gè)值，具體操作如下。

從1 開始出發(fā)，將1 加入數(shù)組list中，當(dāng)前下標(biāo)為index、值為list[index]=k，每次生成新的值下標(biāo)為index+1，值為k+k,即list[index+1]=k+k,當(dāng)k+k＞目標(biāo)正整數(shù)n時(shí)，則進(jìn)行l(wèi)ist的向前遍歷，使得k+list[index-i]＜n(i=0,…,index)，并將新值添加到list中，直至得到目標(biāo)正整數(shù)n。這樣得到一個(gè)加法鏈的初始解。

深度優(yōu)先搜索算法(DFS)是樹的先根遍歷的推廣，每個(gè)節(jié)點(diǎn)僅訪問1 次且對(duì)每一個(gè)可能的分支路徑深入到不能再深入為止。把貪心算法得到加法鏈的初始解的深度設(shè)為全局上界GUB，利用深度優(yōu)先搜索算法進(jìn)一步優(yōu)化這個(gè)可行解，若搜索深度1 超過貪心算法得到的深度，即1＞GUB，停止搜索，然后返回到上一個(gè)節(jié)點(diǎn)或繼續(xù)返回上一個(gè)節(jié)點(diǎn)進(jìn)行搜索。當(dāng)前節(jié)點(diǎn)值為t，當(dāng)前層次為l，通過貪心算法得到的層次為L，目標(biāo)正整數(shù)為n，通過數(shù)學(xué)歸納法得＜n或L＜log2n/t+l，就對(duì)其進(jìn)行剪枝[7]，使其減少空間和運(yùn)行時(shí)間，能更快得到較好的解。

對(duì)于第二類挑戰(zhàn)問題參數(shù)n=10445360463911，通過貪心算法得到一個(gè)可行解，得到加法鏈的長度為49，對(duì)其數(shù)據(jù)進(jìn)行分析，再使用深度優(yōu)先搜索算法時(shí)，對(duì)前40 層的節(jié)點(diǎn)值進(jìn)行確定，并使用剪枝函數(shù)，得到加法鏈長度為46。