最短加法鏈的一種快速算法

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

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

0 引 言

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

1 貪心算法

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

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

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

節(jié)點(diǎn)類:

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("加法鏈長(zhǎng)度:"+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é)點(diǎn)值為t,當(dāng)前層次為l,通過貪心算法得到的層次為L(zhǎng),目標(biāo)正整數(shù)為n,通過數(shù)學(xué)歸納法得:t×2L-l

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

4 結(jié)果分析

為了驗(yàn)證本文所提出的算法的有效性,我們?cè)贓clipse平臺(tái)編寫算法對(duì)7類長(zhǎng)度的參數(shù)進(jìn)行了測(cè)試,這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類問題:具有最短加法鏈長(zhǎng)度的數(shù)有(n,n+1,n-3,n-5),其長(zhǎng)度都為46;第2類問題:具有最短加法鏈長(zhǎng)度的數(shù)有(n+1),其長(zhǎng)度為58;第3類問題:具有最短加法鏈長(zhǎng)度的數(shù)有(n-1),其長(zhǎng)度為66;第4類問題:具有最短加法鏈長(zhǎng)度的數(shù)有(n-3),其長(zhǎng)度為138;第5類問題:具有最短加法鏈長(zhǎng)度的數(shù)有(n-4),其長(zhǎng)度為349;第6類問題:具有最短加法鏈長(zhǎng)度的數(shù)有(n-1),其長(zhǎng)度為765;第7類問題:具有最短加法鏈長(zhǎng)度的數(shù)有(n+1,n-4),其長(zhǎng)度都為2 294。

5 結(jié) 論

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