吳金霞, 吳乘先, 韋 康, 劉 博, 李金玲

(1. 遼寧工業(yè)大學(xué) 理學(xué)院, 遼寧 錦州 121001; 2. 遼寧工業(yè)大學(xué) 電子與信息工程學(xué)院, 遼寧 錦州 121001)

0 引 言

模指數(shù)的冪運算是公鑰密碼學(xué)中的核心運算之一,它的運行效率直接影響著公鑰密碼體制的執(zhí)行速度,而加法鏈則可以應(yīng)用到模指數(shù)的冪運算中。同時,加法鏈也被應(yīng)用到橢圓曲線密碼中改進點乘運算的效率。關(guān)于加法鏈問題的歷史和發(fā)展請參考文獻[1-2]。加法鏈相關(guān)問題的研究是密碼學(xué)等相關(guān)研究領(lǐng)域中的熱門問題[3-7],給定一個正整數(shù)n,一個長度為r的可計算n的加法鏈(addition chain),U是一個嚴(yán)格遞增的U=(u0,u1,u2,…,ur),其中u0=1,u1=2,…,ur=n,且對任意的k>1,uk是它前面2個元素(不必不同)的和,即存在i,j

1 貪心算法

貪心算法(又稱貪婪算法)是指,在對問題求解時,總是做出在當(dāng)前看來是最好的選擇。也就是說,不從整體最優(yōu)上加以考慮,他所做出的是在某種意義上的局部最優(yōu)解.為了能盡快得到目標(biāo)正整數(shù)n,我們使用貪心算法思想,每次都以當(dāng)前值的2倍作為下一個值的選擇,當(dāng)超過目標(biāo)正整數(shù)時,便用當(dāng)前最大值加次大值作為下一個值的選擇,具體操作如下:從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時,則進行l(wèi)ist的向前遍歷,使得k+list[index-i]

packagemimashuxue;import

java.math.BigInteger;import

java.util.ArrayList;import

java.util. Scanner;publicclasst {

publicstaticvoidmain(String[] args) {

Scanner scan=newScanner(System.in); String

in=scan.nextLine();

BigInteger x=newBigInteger(in); BigInteger

one=newBigInteger("1");

ArrayList〈BigInteger〉 list=newArrayList〈BigInteger〉();

intindex=0; list.add(0,

one);

System.out.println("v0="+list.get(index));

index++;

list.add(index,newBigInteger("2"));

System.out.println("v1="+list.get(index));while

(!list.get (index).equals(x)) {

if((list.get(index).add(list.get(index))).compareTo(x) <= 0)

{list.add(index+1, list.get(index).add(list.get(index)));

index++;

System.out.println("v"+(list.size()-1)+"=("

+list.get(index)+","+index+","+(index-1)

+","+(index-1)+")");

}elseif((list.get(index).add(list.get(index))).compareTo(x)>0) {

inti=index;

while((list.get(index).add(list.get(i-1))).compareTo(x)>0) {i=i-1;

}

list.add(index+1, list.get(index).add(list.get(i-1)));

index++;

System.out.println("v"+(list.size()-1)+"=("

+list.get(index)+","+index+","+(index-1)

+","+(i-1)+")");

2 深度優(yōu)先搜索算法

深度優(yōu)先搜索算法是一個針對圖和樹的遍歷算法,英文縮寫為DFS即Depth First Search。深度優(yōu)先搜索是圖論中的經(jīng)典算法,利用深度優(yōu)先搜索算法可以產(chǎn)生目標(biāo)圖的相應(yīng)拓?fù)渑判虮?利用拓?fù)渑判虮砜梢苑奖愕慕鉀Q很多相關(guān)的圖論問題。其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止,而且每個節(jié)點只能訪問一次。

利用貪心算法得到的初始解的深度作為全局上界GUB,通過深度優(yōu)先搜索算法對這個可行解進行進一步優(yōu)化,當(dāng)搜索深度l超過貪心算法得到的初始解的深度,即l>GUB,則停止進一步搜索,返回到上一個節(jié)點進行搜索或繼續(xù)返回上一個節(jié)點.代碼如下

節(jié)點類:

packagemimashuxue4;import

java.math.BigInteger;import

java.util.ArrayList;publicclass

Node {

publicintdepth;

publicBigInteger CurrentMax;

publicArrayList〈BigInteger〉 array=newArrayList〈BigInteger〉();

}

方法類:

packagemimashuxue4;import

java.math.BigInteger;import

java.util.ArrayList;import

java.util.Iterator;publicclass

method {

publicvoidfunction(Node CurNode,intMaxDepth, BigInteger n) {

if(CurNode.depth >=MaxDepth) {

}elseif(CurNode.CurrentMax.compareTo(n)==0 && CurNode.depth

〈MaxDepth) {

MaxDepth = CurNode.depth;

Iterator iterator=CurNode.array.iterator();

while(iterator.hasNext())

System.out.println(iterator.next()+" ");

System.out.println("加法鏈長度:"+CurNode.depth);

}else {

ArrayList〈BigInteger〉 arrayTemp=newArrayList〈BigInteger〉(); Iterator iterator1=

CurNode.array.iterator();

while(iterator1.hasNext()) {

BigInteger temp=(BigInteger) iterator1.next();

arrayTemp.add(temp.add(CurNode.CurrentMax));

}

Iterator iterator2 = arrayTemp.iterator();

while(iterator2.hasNext()) {

BigInteger object = (BigInteger) iterator2.next(); Node nextNode =newNode();

nextNode.array = (ArrayList〈BigInteger〉)

CurNode.array.clone();

BigInteger("2").pow(MaxDepth-CurNode.depth));

if(object.compareTo(n)<=0&&temp.compareTo(n)>=0)

{nextNode.array.add(object); nextNode.CurrentMax=

object;

nextNode.depth=CurNode.depth+1;

function(nextNode, MaxDepth, n);

}

}

}

}

}

結(jié)果類:

packagemimashuxue4;import

java.math.BigInteger;publicclass

test {

publicstaticvoidmain(String[] args) { Node

currentNode=newNode(); currentNode.depth=39;

currentNode.array.add(newBigInteger("1"));for(int

i=0;i<39;i++) {

currentNode.array.add(currentNode.array.get(i).multiply(newBigInteger("2")));

currentNode.CurrentMax=currentNode.array.get(i+1);

}

method tt=newmethod();

tt.function(currentNode,49,newBigInteger("10445360463908"));

}

}

3 剪枝函數(shù)與優(yōu)化

當(dāng)前節(jié)點值為t,當(dāng)前層次為l,通過貪心算法得到的層次為L,目標(biāo)正整數(shù)為n,通過數(shù)學(xué)歸納法得:t×2L-l

當(dāng)長度n過大時,不能在理想時間內(nèi)得到一個最優(yōu)解,結(jié)合已經(jīng)實現(xiàn)的貪心算法,對深度優(yōu)先搜索算法的前部分的路徑進行確定,在此基礎(chǔ)上進行深度優(yōu)先搜索,這樣能夠保證算法在理想時間內(nèi)得到一個比貪心算法要好的解。

4 結(jié)果分析

為了驗證本文所提出的算法的有效性,我們在Eclipse平臺編寫算法對7類長度的參數(shù)進行了測試,這7類參數(shù)依次為

第1類參數(shù):n=10445360463911,

第2類參數(shù):n=211108170305887,

第3類參數(shù):n=13835058061724614657,

第4類參數(shù):n=255211775190703851000955237173238443091,

第5類參數(shù):

n=57896044618658097711785492504343953926634992332820282019728792003956564819949

第6類參數(shù):

n=670390396497129854978701249910292306373968291029619668886178072186088201503677348

8400937149083451713845015929093243025426876941405973284973216824503042031

第7類參數(shù):

n=184769970321174147430683562020016440301854933866341017147178577491065169671116124

9859337684305435744585616061544571794052229717732524660960646946071249623720442022269756

7566873784275623895087646784409332851574965788434150884755282981867264513398633649319080

8467199043187438128336350279547028265329780293491615581188104984490831954500984839377522

7257052578591944993870073695755688436933812779613089230392569695253261620823676490316036

551371447913932347169566988069

第1類問題:具有最短加法鏈長度的數(shù)有(n,n+1,n-3,n-5),其長度都為46;第2類問題:具有最短加法鏈長度的數(shù)有(n+1),其長度為58;第3類問題:具有最短加法鏈長度的數(shù)有(n-1),其長度為66;第4類問題:具有最短加法鏈長度的數(shù)有(n-3),其長度為138;第5類問題:具有最短加法鏈長度的數(shù)有(n-4),其長度為349;第6類問題:具有最短加法鏈長度的數(shù)有(n-1),其長度為765;第7類問題:具有最短加法鏈長度的數(shù)有(n+1,n-4),其長度都為2 294。

5 結(jié) 論

本文針對7類不同長度的n,研究了最短加法鏈求解算法,將貪心算法、深度優(yōu)先搜索算法和隨機冪樹法有機地結(jié)合在一起,并利用一些剪枝函數(shù)進行剪枝操作,以減少時間復(fù)雜度和空間復(fù)雜度。在Eclipse平臺下編寫程序驗證了所用方法的有效性。