胡建軍,王 偉,李恒杰

(蘭州文理學(xué)院 數(shù)字媒體學(xué)院, 甘肅 蘭州 730010)

盡管如此，學(xué)者很少關(guān)注Pollardρ和Pohlig-Hellman兩個算法的有效融合．針對這一問題，結(jié)合Pohlig-Hellman和Pollardρ兩個算法各自的長處，利用文獻[2]的迭代函數(shù)，作者提出一種基于Pohlig-Hellman的Pollardρ混合迭代求解離散對數(shù)的方法．方法的思想是:當階的素因子小于等于光滑界時，使用Pohlig-Hellman算法迭代求解；當階的素因子大于光滑界時，使用Pollardρ算法迭代求解．同時，分析了混合算法的效率.最后通過實例驗證了結(jié)論的正確性和有效性．

1 相關(guān)知識

1.1 Pohlig-Hellman算法概述

由Fermat定理，有

gN≡1modp，

所以，有

從0到qi-1嘗試使等式成立的z0的值，并保存z0．另外，由于

1.2 Pollard ρ算法概述

(1)

且ai和bi的序列分別如式(2)和(3)所示, 初始a0=b0=0．從而, 序列中的每個元素具有ri=yaigbi的形式，序列ri=yaigbi可看成是一個隨機游走．

(2)

(3)

執(zhí)行一個6元組(ri,ai,bi,r2i,a2i,b2i)的序列, 直到找到ri=r2i,即yaigbi=ya2igb2i．

令

m≡ai-a2i(modN),

n≡b2i-bi(modN),

則

利用擴展的歐幾里得算法尋找一個滿足d=gcd(m,N)=λm+μN的λ和μ．從而λm≡d(modN),因此yd=gλn, 且λn一定在形式kd中(由于左邊是第d個冪)．利用第d個根, 得到

其中：k=((λn(modN))/m)(modN)．

loggy=(k+(N/d)*j)(modN)．

1.3 迭代函數(shù)

假設(shè)t0,t1,t2,…是一個大于1的素數(shù)序列，則考慮如下序列

(4)

對于任意的整數(shù)x,0≤x≤N-1,有式(5)成立

x=z0+z1t0+z2t0t1+z3t0t1t2+…+zu-1t0t1…tu-2，

(5)

其中：系數(shù)zj滿足0≤zj

假設(shè)

sk=z0+z1t0+z2t0t1+z3t0t1t2+…+zk-1t0t1…tk-2，0≤k

則k+1個同余系數(shù)乘積之和的迭代公式為

sk+1=sk+zkt0t1…tk-1．

由式(4)，(5)可得

(6)

從式(6)可以看出，z0由x≡z0(modt0)計算，z1由x-z0≡z1t0(modt1)計算，如此重復(fù)，最后zu-1由

x-su-2≡zu-1t0t1…tu-2(modtu-1)

計算，u≥2，即

x≡su-2+zu-1t0t1…tu-1modtu-1，

因此式(6)就是求解的迭代函數(shù)．

1.4 Pollard ρ算法理論分析基礎(chǔ)

引理2給出了離散對數(shù)求解的概率上界，引理3給出了離散對數(shù)求解的下界．

定義令b是一個正整數(shù)，若階N的所有素因子都小于等于b，則稱b是N光滑的．

2 混合迭代算法設(shè)計

算法1 Pohlig-Hellman iteration algorithm

Input：p,g,y,b

Output：sb

1 sb=0,δ=1,η=1,ζ=1,N=p-1 //δ用于計算冪模,η用于迭代計算.

2 γ=inverse(g,p)

3 for i=1 to b

4 {δ=δ*Arr(i),η=η*ζ //δ存儲前i個光滑因子的積,η存儲前i-1個光滑因子的積.

5 if Arr(i)<>ζ then gh=gN/Arr(i)(modp)

6 yt=γsb(modp)

7 yh=y*ytN/δ(modp)

8 for j=0 to Arr(i)-1{ if ghj(modp)=yh then {sb=sb+j*η(mod N),exit}}

9 ζ=Arr(i)

10 }

11 return sb

12 end

在算法2中，先將y值轉(zhuǎn)換為新值y′，即y′=inverse(g,p)sby(modp)，然后再計算y′的離散對數(shù)值，x=loggy′(modN)為所要求解的離散對數(shù)．算法2直接引用了引理1，2的結(jié)論.下面是算法2的設(shè)計實現(xiàn)．

算法2 Pollardρiteration algorithm

Input：p,g,y,b,sb,pl

Output：sp

1 sp=sb,a1=b1=0,r=1,δ=1,η=1,ζ=1,N=p-1

2 γ=inverse(g,p),y′=γsb*y(modp)

3 for θ=b+1 to pl

4 {δ=δ*Arr(θ),η=η*ξ

5 if Arr(θ)<>ξ then gh=gN/Arr(θ)(modp)

6 yt=γsp(modp),yh=y′*ytN/δ(modp)

8 Do while i<=tl // tl為游走到環(huán)上需要的步數(shù)，該循環(huán)將游走到環(huán)上.

9 { if r<=p/3 then {r=r*yh,a1=a1+1}

10 else if p/3

11 else {r=r*gh,b1=b1+1}

12 i=i+1

13 }

14 rs=r,a2=a1,b2=b1,cnt=0

15 Do //在環(huán)上查找碰撞.

16 { if r<=p/3 then {r=r*yh,a2=a2+1}

17 else if p/3

18 else {r=r*gh,b2=b2+1}

19 cnt=cnt+1

21 if rs=r and a1<>a2then

22 {m=(a1-a2)(mod N),n=(b2-b1)(mod N),d=λm+μN(mod N)

23 k=(λ*n/d)(mod N),β=gk(modp),j=0,ε=1

24 yhh=ε*β(mod p)

25 Do while y’<>yhh and j

26 {ε=y’*yhh(mod p),j=j+1,yhh=ε*β(mod p)}

27 if y’=yhh then return sp=sp+k+j*N/d(mod N) else return failure

28 }

29 else return failure

30 ζ=Arr(θ)

31 }

32 end

3 混合迭代算法分析

3.1 算法分析

定理1設(shè)Arr(pl)是階N的最大素因子，且大于光滑界b的素因子個數(shù)僅為1，則混合算法經(jīng)過下列步數(shù)找到一次碰撞：

證明因為y和g在算法2中均需要執(zhí)行N/Arr(pl)的冪次求余運算，這就保證了Arr(pl)是循環(huán)子群的階，而是Arr(pl)又是素數(shù)，由引理2可知，結(jié)論成立．

定理2設(shè)大于光滑界b的素因子個數(shù)為τ，算法2迭代一次的成率為v，則混合算法的成功率為ντ．

證明因為迭代算法是在前一計算結(jié)果正確的基礎(chǔ)上重復(fù)執(zhí)行，而前一迭代和后一迭代又是互相獨立的，所以，混合算法的成功率為ντ．

由定理2可知，要確保求解獲得更大的概率，迭代次數(shù)要盡可能地小，最好不超過2(因為當超過2時，成功求解的概率將大于等于25%)，這樣混合算法才具有求解的優(yōu)越性．

3.2 算法實例

假設(shè)p=71，生成元g=7，光滑界為5，y=32，計算x=log732的離散對數(shù)30．

因為N=p-1=70=2*5*7，所以Arr(1)=2，Arr(2)=5，Arr(3)=7，從而得b=2，pl=3．

首先，來看算法1的執(zhí)行過程．初始sb=0，δ=1，η=1，ζ=1，N=p-1=70．計算γ=inverse(g,p)=61．執(zhí)行for循環(huán)體，當i=1時，δ=1*Arr(1)=2，η=η*ζ=1.因為Arr(1)<>ζ，所以gh=770/2(mod71)=70，yt=610(mod71)=1，yh=(32*1)70/2(mod71)=1.又700=1，從而sb=sb+j*η=0，ζ=Arr(1).當i=2時，δ=δ*Arr(2)=10，η=η*ζ=2，因為Arr(2)<>ζ，所以gh=770/5(mod71)=54，yt=610(mod71)=1，yh=(32*1)70/10(mod71)=1.又540(mod71)=1，從而sb=sb+j*η=0，ζ=Arr(2)．即算法1的迭代結(jié)果為0．

4 結(jié)束語