Math Pro 數學補給站

標題: 用Maxima學密碼學－離散對數問題 [打印本頁]

作者: bugmens 時間: 2020-3-29 22:16 標題: 用Maxima學密碼學－離散對數問題

離散對數問題(Discrete Logarithm Problem，DLP)
已知$\alpha,\beta,p$，$0<\alpha,\beta<p$，$GCD(\alpha,p)=1$，$\alpha^x\equiv \beta \pmod{p}$，當$p$很大時，計算$x$值非常困難。

橢圓曲線離散對數問題(Elliptic Curve Discrete Logarithm Problem，ECDLP)
(1)令$E$為基於有限體$F_p$的橢圓曲線，$P,Q$為橢圓曲線上的點坐標($P,Q\in E(F_p)$)且$Q=kP,k\in N$，當$p$很大時，計算$k$值非常困難。
(2)令$E$為基於二元體$F_{2^n}$的橢圓曲線，$P,Q$為橢圓曲線上的點坐標($P,Q\in E(F_{2^n})$)且$Q=kP,k\in N$，當$n$很大時，計算$k$值非常困難。
以下介紹解離散對數問題和橢圓曲線離散對數問題的各種方法。

作者: bugmens 時間: 2020-4-3 07:41

1.解離散對數問題的方法-小步大步(Baby-step Giant-step)

將答案改寫成$x=im+j$，其中$m=\lceil\;\sqrt{p}\rceil\;$，$0\le i<m$，$0\le j<m$
將原本離散對數問題改成
$\alpha^x \equiv \beta \pmod{p}$
$\alpha^{im+j}\equiv \beta \pmod{p}$
$\alpha^j\equiv \beta(\alpha^{-m})^i \pmod{p}$
計算$\alpha^j$稱為Baby-step
計算$\beta(\alpha^{-m})^i$稱為Giant-step
當某個$i$和$j$值讓$\alpha^j$和$\beta(\alpha^{-m})^i$相等時，就代表找到答案$x=im+j$

虛擬碼
1.$m=Ceiling(\sqrt{p})$
2.for j=0~m-1
　計算$[\alpha^j\pmod{p},j]$數對放在List中
3.計算$\alpha^{-m}$
4.設$\gamma=\beta$
5.for i=0~m-1
　檢查目前$\gamma$值是否等於List中某個$\alpha^j\pmod{p}$
　若是，答案$x=im+j$
　若否，計算$\gamma=\gamma \cdot \alpha^{-m}$

參考資料：https://en.wikipedia.org/wiki/Baby-step_giant-step

Baby_stepGiant_step副程式
(%i1)
Baby_stepGiant_step(alpha,beta,p):=block
([m,gamma,List,inv_am,i,j,Powerj,x:[]],
print("取Giant步長m=Ceiling(",sqrt(p),")=",m:ceiling(sqrt(p))),
print("Baby step，計算",alpha^"0",",",alpha^"1",",...,",alpha,""^(m-1),"(mod ",p,")"),
print("List=",List:create_list(power_mod(alpha,j,p),j,0,m-1)),
print("(",a^"-1",")"^m,"≡(",alpha^"-1",")"^m,"≡",inv_mod(alpha,p),""^m,"≡",inv_am:power_mod(alpha,-m,p),"(mod ",p,")"),
print("令γ=β=",gamma:beta),
print("Giant step，每次γ值再乘上(α"^"-1",")"^m),
for i:0 thru m-1 do
  (print("當i=",i,"時"),
Powerj:sublist_indices(List,lambda([aj],aj=gamma))-1,/*檢查List中是否有gamma值*/
if Powerj#[] then
   (print("List中有γ=",gamma,"值"),
   for j in Powerj do
      (print("j=",j,"次方，找到一解x=i*m+j=",i,"*",m,"+",j,"=",last(x:append(x,[i*m+j])))
      )
   )
  else
   (print("List中沒有γ=",gamma,"值")
   ),
  print("計算γ≡γ*(α"^"-1",")"^m,"≡",gamma,"*",inv_am,"≡",gamma*inv_am,"≡",gamma:mod(gamma*inv_am,p),"(mod ",p,")")

  ),
return(x)
)$

$\alpha^x \equiv \beta\pmod{p}$，$x=$？
(%i4)
alpha:2;
beta:108;
p:181;
(alpha)　2
(beta)　108
(p)　181

利用Baby_stepGiant_step方法解離散對數問題
(%i5)　x:Baby_stepGiant_step(alpha,beta,p);
取Giant步長$m=Ceiling(\sqrt{181})=14$
Babystep，計算$2^0,2^1,\ldots,2^{13}\pmod{181}$
$List=[1,2,4,8,16,32,64,128,75,150,119,57,114,47]$
$(\alpha^{-1})^{14}\equiv(2^{-1})^{14}\equiv91^{14}\equiv52\pmod{181}$
令$\gamma=\beta=108$
Giantstep，每次$\gamma$值再乘上$(\alpha^{-1})^{14}$
當$i=0$時
List中沒有$\gamma=108$值
計算$\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv108*52\equiv5616\equiv5\pmod{181}$
當$i=1$時
List中沒有$\gamma=5$值
計算$\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv5*52\equiv260\equiv79\pmod{181}$
當$i=2$時
List中沒有$\gamma=79$值
計算$\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv79*52\equiv4108\equiv126\pmod{181}$
當$i=3$時
List中沒有$\gamma=126$值
計算$\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv126*52\equiv6552\equiv36\pmod{181}$
當$i=4$時
List中沒有$\gamma=36$值
計算$\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv36*52\equiv1872\equiv62\pmod{181}$
當$i=5$時
List中沒有$\gamma=62$值
計算$\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv62*52\equiv3224\equiv147\pmod{181}$
當$i=6$時
List中沒有$\gamma=147$值
計算$\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv147*52\equiv7644\equiv42\pmod{181}$
當$i=7$時
List中沒有$\gamma=42$值
計算$\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv42*52\equiv2184\equiv12\pmod{181}$
當$i=8$時
List中沒有$\gamma=12$值
計算$\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv12*52\equiv624\equiv81\pmod{181}$
當$i=9$時
List中沒有$\gamma=81$值
計算$\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv81*52\equiv4212\equiv49\pmod{181}$
當$i=10$時
List中沒有$\gamma=49$值
計算$\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv49*52\equiv2548\equiv14\pmod{181}$
當$i=11$時
List中沒有$\gamma=14$值
計算$\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv14*52\equiv728\equiv4\pmod{181}$
當$i=12$時
List中有$\gamma=4$值
j=2次方，找到一解$x=i*m+j=12*14+2=170$
計算$\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv4*52\equiv208\equiv27\pmod{181}$
當$i=13$時
List中沒有$\gamma=27$值
計算$\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv27*52\equiv1404\equiv137\pmod{181}$
(x)　$[170]$

作者: bugmens 時間: 2020-4-5 22:03

2.解離散對數問題的方法-小步大步(Baby-step giant-step)

相同原理提供另一種實作
虛擬碼
1.$m=Ceiling(\sqrt{p})$
2.計算$\alpha^{-m}$
3.for j=0~m-1
　計算$[\alpha^j \pmod{p},j]$數對放在BabyStep List中
4.for i=0~m-1
　計算$[\beta(\alpha^{-m})^i \pmod{p},i]$數對放在GiantStep List中
5.將BabyStep和GiantStep的List由小到大重新排序
6.兩個List互相比較找出相同值
　若有，答案$x=im+j$
　若沒有，答案無解

參考資料：Computational Number Theory and Modern Cryptography

Baby_stepGiant_step副程式
(%i1)
Baby_stepGiant_step(alpha,beta,p):=block
([m,inv_am,BabyStep,GiantStep,indexB:1,indexG:1,i,j,x:[]],
print("取Giant步長m=Ceiling(",sqrt(p),")=",m:ceiling(sqrt(p))),
print("(",a^"-1",")"^m,"≡(",alpha^"-1",")"^m,"≡",inv_mod(alpha,p),""^m,"≡",inv_am:power_mod(alpha,-m,p),"(mod ",p,")"),
print("BabyStep=",BabyStep:create_list([power_mod(alpha,j,p),j],j,0,m-1)),
print("GiantStep=",GiantStep:create_list([mod(beta*power_mod(inv_am,i,p),p),i],i,0,m-1)),
print("由小到大排序"),
print("BabyStep=",BabyStep:sort(BabyStep)),
print("GiantStep=",GiantStep:sort(GiantStep)),
print("BabyStep和GiantStep互相比較找出相同值"),
print("一開始indexB=1,indexG=1"),
while indexB<=m and indexG<=m do
(if BabyStep[indexB][1]=GiantStep[indexG][1] then
   (do
      (i:GiantStep[indexG][2],j:BabyStep[indexB][2],/*第2個值是i和j*/
         print("BabyStep[",indexB,"]=",BabyStep[indexB],"第1個值等於",
               "GiantStep[",indexG,"]=",GiantStep[indexG],"第1個值，得到一解x=i*m+j=",i,"*",m,"+",j,"=",last(x:append(x,[i*m+j]))),
         print("GiantStep移到下一組，indexG=indexG+1=",indexG:indexG+1),
         if indexG=m or GiantStep[indexG][1]#GiantStep[indexG-1][1] then
            (return())
      ),
      print("BabyStep移到下一組，indexB=indexB+1=",indexB:indexB+1)
   )
else if BabyStep[indexB][1]<GiantStep[indexG][1] then
   (print("BabyStep[",indexB,"]=",BabyStep[indexB],"第1個值小於",
            "GiantStep[",indexG,"]=",GiantStep[indexG],"第1個值，BabyStep移到下一組，indexB=indexB+1=",indexB:indexB+1)
   )
else
   (print("BabyStep[",indexB,"]=",BabyStep[indexB],"第1個值大於",
            "GiantStep[",indexG,"]=",GiantStep[indexG],"第1個值，GiantStep移到下一組，indexG=indexG+1=",indexG:indexG+1)
   )
),
return(x)
)$

$\alpha^x \equiv \beta \pmod{p}$，$x=$？
(%i4)
alpha:2;
beta:108;
p:181;
(alpha)　2
(beta)　108
(p)　181

利用Baby_stepGiant_step方法解離散對數問題
(%i5)　Baby_stepGiant_step(alpha,beta,p);
取Giant步長$m=Ceiling(\sqrt{181})=14$
$(a^{-1})^{14}\equiv(2^{-1})^{14}\equiv 91^{14}\equiv52\pmod{181}$
$BabyStep=[[1,0],[2,1],[4,2],[8,3],[16,4],[32,5],[64,6],[128,7],[75,8],[150,9],[119,10],[57,11],[114,12],[47,13]]$
$GiantStep=[[108,0],[5,1],[79,2],[126,3],[36,4],[62,5],[147,6],[42,7],[12,8],[81,9],[49,10],[14,11],[4,12],[27,13]]$
由小到大排序
$BabyStep=[[1,0],[2,1],[4,2],[8,3],[16,4],[32,5],[47,13],[57,11],[64,6],[75,8],[114,12],[119,10],[128,7],[150,9]]$
$GiantStep=[[4,12],[5,1],[12,8],[14,11],[27,13],[36,4],[42,7],[49,10],[62,5],[79,2],[81,9],[108,0],[126,3],[147,6]]$
BabyStep和GiantStep互相比較找出相同值
一開始$indexB=1,indexG=1$
$BabyStep[1]=[1,0]$第1個值小於$GiantStep[1]=[4,12]$第1個值，BabyStep移到下一組，$indexB=indexB+1=2$
$BabyStep[2]=[2,1]$第1個值小於$GiantStep[1]=[4,12]$第1個值，BabyStep移到下一組，$indexB=indexB+1=3$
$BabyStep[3]=[4,2]$第1個值等於$GiantStep[1]=[4,12]$第1個值，得到一解$x=i*m+j=12*14+2=170$
GiantStep移到下一組，$indexG=indexG+1=2$
BabyStep移到下一組，$indexB=indexB+1=4$
$BabyStep[4]=[8,3]$第1個值大於$GiantStep[2]=[5,1]$第1個值，GiantStep移到下一組，$indexG=indexG+1=3$
$BabyStep[4]=[8,3]$第1個值小於$GiantStep[3]=[12,8]$第1個值，BabyStep移到下一組，$indexB=indexB+1=5$
$BabyStep[5]=[16,4]$第1個值大於$GiantStep[3]=[12,8]$第1個值，GiantStep移到下一組，$indexG=indexG+1=4$
$BabyStep[5]=[16,4]$第1個值大於$GiantStep[4]=[14,11]$第1個值，GiantStep移到下一組，$indexG=indexG+1=5$
$BabyStep[5]=[16,4]$第1個值小於$GiantStep[5]=[27,13]$第1個值，BabyStep移到下一組，$indexB=indexB+1=6$
$BabyStep[6]=[32,5]$第1個值大於$GiantStep[5]=[27,13]$第1個值，GiantStep移到下一組，$indexG=indexG+1=6$
$BabyStep[6]=[32,5]$第1個值小於$GiantStep[6]=[36,4]$第1個值，BabyStep移到下一組，$indexB=indexB+1=7$
$BabyStep[7]=[47,13]$第1個值大於$GiantStep[6]=[36,4]$第1個值，GiantStep移到下一組，$indexG=indexG+1=7$
$BabyStep[7]=[47,13]$第1個值大於$GiantStep[7]=[42,7]$第1個值，GiantStep移到下一組，$indexG=indexG+1=8$
$BabyStep[7]=[47,13]$第1個值小於$GiantStep[8]=[49,10]$第1個值，BabyStep移到下一組，$indexB=indexB+1=8$
$BabyStep[8]=[57,11]$第1個值大於$GiantStep[8]=[49,10]$第1個值，GiantStep移到下一組，$indexG=indexG+1=9$
$BabyStep[8]=[57,11]$第1個值小於$GiantStep[9]=[62,5]$第1個值，BabyStep移到下一組，$indexB=indexB+1=9$
$BabyStep[9]=[64,6]$第1個值大於$GiantStep[9]=[62,5]$第1個值，GiantStep移到下一組，$indexG=indexG+1=10$
$BabyStep[9]=[64,6]$第1個值小於$GiantStep[10]=[79,2]$第1個值，BabyStep移到下一組，$indexB=indexB+1=10$
$BabyStep[10]=[75,8]$第1個值小於$GiantStep[10]=[79,2]$第1個值，BabyStep移到下一組，$indexB=indexB+1=11$
$BabyStep[11]=[114,12]$第1個值大於$GiantStep[10]=[79,2]$第1個值，GiantStep移到下一組，$indexG=indexG+1=11$
$BabyStep[11]=[114,12]$第1個值大於$GiantStep[11]=[81,9]$第1個值，GiantStep移到下一組，$indexG=indexG+1=12$
$BabyStep[11]=[114,12]$第1個值大於$GiantStep[12]=[108,0]$第1個值，GiantStep移到下一組，$indexG=indexG+1=13$
$BabyStep[11]=[114,12]$第1個值小於$GiantStep[13]=[126,3]$第1個值，BabyStep移到下一組，$indexB=indexB+1=12$
$BabyStep[12]=[119,10]$第1個值小於$GiantStep[13]=[126,3]$第1個值，BabyStep移到下一組，$indexB=indexB+1=13$
$BabyStep[13]=[128,7]$第1個值大於$GiantStep[13]=[126,3]$第1個值，GiantStep移到下一組，$indexG=indexG+1=14$
$BabyStep[13]=[128,7]$第1個值小於$GiantStep[14]=[147,6]$第1個值，BabyStep移到下一組，$indexB=indexB+1=14$
$BabyStep[14]=[150,9]$第1個值大於$GiantStep[14]=[147,6]$第1個值，GiantStep移到下一組，$indexG=indexG+1=15$
(%o5)　$[170]$

作者: bugmens 時間: 2020-7-25 10:22

3-1.解離散對數問題的方法-小步和倍增步長的大步(Baby-step and double step width Giant-step)

原本的小步大步

小步和倍增步長的大步

將答案改寫成$x=im+j$
其中$m=\lceil\;\sqrt{p}\rceil\;$，$0\le i<m$，$0\le j<m$

$\alpha^x \equiv \beta \pmod{p}$
$\alpha^{im+j}\equiv \beta \pmod{p}$
$\alpha^j \equiv \beta(\alpha^{-m})^i \pmod{p}$
計算$\alpha^j$稱為Baby step
計算$\beta(\alpha^{-m})^i$稱為Giant step
每次步長都是$\alpha^{-m}$

將答案改寫成$x=2^kvq+r$　($x$除以$2^kv$，商數$q$，餘數$r$)
其中$v$為偶數，$k\ge 0$，$1\le r \le 2^kv$

$\alpha^x \equiv \beta \pmod{p}$
$\displaystyle \alpha^{2^kvq+r}\equiv \beta \pmod{p}$
$\displaystyle \beta \alpha^{-r}\equiv (\alpha^{2^kv})^q \pmod{p}$
計算$ \beta\alpha^{-r}$稱為Baby step
計算$(\alpha^{2^kv})^q$稱為Giant step
每次步長$\alpha^{2^kv}$隨著$k$值倍增

Lemma 2.1　設$v$為正偶數，對每一個正整數$x$，存在唯一的$k \ge 0$，$q$和$r$，$\lfloor\;4^{k-1}\rfloor\;v^2\le 2^kvq <4^kv^2$和$1\le r\le 2^kv$，使得$x=y+r$,$y=2^kvq$。

以$2^x \equiv 108 \pmod{181}$，參數$v=2$為例。
－－－－－－－－
當$k=0$時
$BabyStep$：$1\le r \le 2^0v$，$1\le r \le 2$，$r=1,2$
$GiantStep$：$\lfloor\;4^{-1}\rfloor\;v^2\le 2^kvq<4^0v^2$，$0\le 2^kvq<4$，$2^kvq=0,2$，倍增步長為2
可能$x=1,2,3,4$
－－－－－－－－
當$k=1$時
$BabyStep$：$1\le r \le 2^1v$，$1\le r \le 4$，$r=1,2,3,4$
$GiantStep$：$\lfloor\;4^0\rfloor\;v^2\le 2^kvq<4^1v^2$，$4\le 2^kvq<16$，$2^kvq=4,8,12$，倍增步長為4
可能$x=5,6,\ldots,16$
－－－－－－－－
當$k=2$時
$BabyStep$：$1\le r \le 2^2v$，$1\le r \le 8$，$r=1,2,3,4,5,6,7,8$
$GiantStep$：$\lfloor\;4^1\rfloor\;v^2\le 2^kvq<4^2v^2$，$16\le 2^kvq<64$，$2^kvq=16,24,32,40,48,56$，倍增步長為8
可能$x=17,18,\ldots,64$
－－－－－－－－
當$k=3$時
$BabyStep$：$1\le r \le 2^3v$，$1\le r \le 16$，$r=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16$
$GiantStep$：$\lfloor\;4^2\rfloor\;v^2\le 2^kvq<4^3v^2$，$64\le 2^kvq<256$，$2^kvq=64,80,96,112,128,144,160,176,192,208,224,240$，倍增步長為16
可能$x=65,66,\ldots,256$，已經超過全部可能答案$x=1,2,\ldots,181$

參考資料：https://www.ams.org/journals/mco ... 5718-97-00880-6.pdf

Baby_stepDoubleGiant_step副程式
(%i1)
Baby_stepDoubleGiant_step(alpha,beta,p,v):=block
([k:0,BabyStep,GiantStep,GiantPower,indexB:1,indexG:1,LengthB,LengthG,x:[]],
if primep(p)=false then
  (print("參數p=",p,"要是質數"),
return()
  ),
if mod(v,2)=1 then
  (print("參數v=",v,"要是偶數"),
return()
  ),
do
  (print("當k=",k,"時"),
print("1≦r≦",2^"k","v，1≦r≦",2^k*v),
print(alpha^"-1","=",inv_mod(alpha,p),"(mod",p,")"),
print("BabyStep=[",beta,"*",alpha^"-r","(mod",p,"),",r,"]=",
         BabyStep:create_list([mod(beta*power_mod(alpha,-r,p),p),r],r,1,2^k*v)),
print("floor(",4^"k-1",")v"^"2","≦",2^"k","vq<",4^"k","v"^2,"，",floor(4^(k-1))*v^2,"≦",2^"k","vq<",4^k*v^2),
print(2^"k","vq=",GiantPower:create_list(2^k*v*q,q,floor(4^(k-1))/2^k*v,2^k*v-1),
      ",倍增步長為",2^k*v),
print("GiantStep=[",alpha^(2^"k"*"v"*q),"(mod",p,")",",",2^"k"*"v"*q,"]=",
         GiantStep:map(lambda([power],[power_mod(alpha,power,p),power]),GiantPower)),
print("由小到大排序"),
print("BabyStep=",BabyStep:sort(BabyStep)),
print("GiantStep=",GiantStep:sort(GiantStep)),
print("BabyStep和GiantStep互相比較找出相同值"),
LengthB:length(BabyStep),
LengthG:length(GiantStep),
while indexB<=LengthB and indexG<=LengthG do
   (if BabyStep[indexB][1]=GiantStep[indexG][1] then
      (do
         (print("BabyStep[",indexB,"]=",BabyStep[indexB],"和","GiantStep[",indexG,"]=",GiantStep[indexG],"的第一個值相同"),
         print("得到一解x=",BabyStep[indexB][2],"+",GiantStep[indexG][2],
               "=",last(x:append(x,[BabyStep[indexB][2]+GiantStep[indexG][2]]))),
         indexG:indexG+1,
         if indexG>LengthG or GiantStep[indexG][1]#GiantStep[indexG-1][1] then
            (return())
         ),
      indexB:indexB+1
      )
   else if BabyStep[indexB][1]<GiantStep[indexG][1] then
      (indexB:indexB+1)
   else
      (indexG:indexG+1)
   ),
if x=[] then/*沒找到解答*/
   (print("BabyStep和GiantStep沒有相同值"))
else/*找到解答跳出去*/
   (print("將x=",x,"(mod",p-1,")=",x:mod(x,p-1)),
   print("再刪除相同值x=",x:unique(x)),
   return(x)
   ),
if 4^k*v^2>p then
   (print("無解"),
   return()
   ),
k:k+1,/*換下一個k值*/
print("－－－－－－－－")
  )
)$

$\alpha^x\equiv \beta \pmod{p}$，初始步長$v$要是偶數
(%i5)
alpha:2;
beta:108;
p:181;
v:2;
(alpha)　2
(beta)　108
(p)　181
(v)　2

利用Baby_stepDoubleGiant_step方法解離散對數問題
(%i6)　x:Baby_stepDoubleGiant_step(alpha,beta,p,v);
當$k=0$時
$1\le r\le 2^k v$，$1\le r\le 2$
$2^{-1} \equiv 91 \pmod{181}$
$BabyStep=[ 108 * 2^{-r} \pmod{181}, r ]= [[54,1],[27,2]]$
$floor( 4^{k-1} )v^2 \le 2^k vq< 4^k v^2$，$0 \le 2^k vq< 4$
$2^k vq= [0,2]$,倍增步長為 2
$GiantStep=[ 2^{2^kvq} \pmod{181},2^kvq]=[[1,0],[4,2]]$
由小到大排序
$BabyStep= [[27,2],[54,1]]$
$GiantStep= [[1,0],[4,2]]$
$BabyStep$和$GiantStep$互相比較找出相同值
$BabyStep$和$GiantStep$沒有相同值
－－－－－－－－
當$k=1$時
$1\le r\le 2^k v$，$1\le r\le 4$
$2^{-1} \equiv 91 \pmod{181}$
$BabyStep=[ 108 * 2^{-r}\pmod{181},r]=[[54,1],[27,2],[104,3],[52,4]]$
$floor( 4^{k-1})v^2 \le 2^k vq< 4^k v^2$，$4\le 2^k vq< 16$
$2^k vq= [4,8,12]$,倍增步長為 4
$GiantStep=[ 2^{2^kvq} \pmod{181},2^kvq]=[[16,4],[75,8],[114,12]]$
由小到大排序
$BabyStep=[[27,2],[52,4],[54,1],[104,3]]$
$GiantStep=[[16,4],[75,8],[114,12]]$
$BabyStep$和$GiantStep$互相比較找出相同值
$BabyStep$和$GiantStep$沒有相同值
－－－－－－－－
當$k=2$時
$1\le r\le 2^k v$，$1\le r\le 8$
$2^{-1}\equiv 91 \pmod{181}$
$BabyStep=[ 108 * 2^{-r} \pmod{181},r]=[[54,1],[27,2],[104,3],[52,4],[26,5],[13,6],[97,7],[139,8]]$
$floor( 4^{k-1})v^2 \le 2^k vq< 4^k v^2$，$16\le 2^k vq< 64$
$2^k vq= [16,24,32,40,48,56]$,倍增步長為 8
$GiantStep=[ 2^{2^kvq} \pmod{181},2^kvq]=[[14,16],[145,24],[15,32],[39,40],[29,48],[3,56]]$
由小到大排序
$BabyStep=[[13,6],[26,5],[27,2],[52,4],[54,1],[97,7],[104,3],[139,8]]$
$GiantStep=[[3,56],[14,16],[15,32],[29,48],[39,40],[145,24]]$
$BabyStep$和$GiantStep$互相比較找出相同值
$BabyStep$和$GiantStep$沒有相同值
－－－－－－－－
當$k=3$時
$1\le r\le 2^k v$，$1\le r\le 16$
$2^{-1}\equiv 91 \pmod{181}$
$BabyStep=[ 108 * 2^{-r} \pmod{181},r]=[[54,1],[27,2],[104,3],[52,4],[26,5],[13,6],$
$[97,7],[139,8],[160,9],[80,10],[40,11],[20,12],[10,13],[5,14],[93,15],[137,16]]$
$floor( 4^{k-1})v^2 \le 2^k vq< 4^k v^2$，$64 \le 2^k vq< 256$
$2^kvq=[64,80,96,112,128,144,160,176,192,208,224,240]$,倍增步長為 16
$GiantStep=[ 2^{2^kvq} \pmod{181},2^kvq]=[[44,64],[73,80],[117,96],[9,112],$
$[126,128],[135,144],[80,160],[34,176],[114,192],[148,208],[81,224],[48,240]]$
由小到大排序
$BabyStep=[[5,14],[10,13],[13,6],[20,12],[26,5],[27,2],[40,11],[52,4],[54,1],[80,10],$
$[93,15],[97,7],[104,3],[137,16],[139,8],[160,9]]$
$GiantStep=[[9,112],[34,176],[44,64],[48,240],[73,80],[80,160],[81,224],[114,192],$
$[117,96],[126,128],[135,144],[148,208]]$
$BabyStep$和$GiantStep$互相比較找出相同值
$BabyStep[10]=[80,10]$和$GiantStep[6]=[80,160]$的第一個值相同
得到一解$x=10+160=170$
將$x=[170] \pmod{180}=[170]$
再刪除相同值$x=[170]$
(x)　$[170]$

作者: bugmens 時間: 2020-8-6 15:57

3-2.解離散對數問題的方法-小步和倍增步長的大步(Baby-step and double step width Giant-step)

若能理解上一篇文章，再回頭看論中的演算法2.2計算$g$的order。
$g^x \equiv 1\pmod{p}$
$g^{y+r}\equiv 1 \pmod{p}$
$g^y \equiv g^{-r}\pmod{p}$
計算$g^{-r}$稱為Baby step
計算$g^y$稱為Giant step

演算法2.2
輸入：$g\in G$，$|\;g|\;$的下限$C+1$(若已知解答$x$不會在$1\sim C$之間)，初始步長$v$($v$要是偶數)
輸出：$x=|\;g|\;$
(1) $x = 0$
(2) $s = 1; y = v; u = v$
(3) $h = g^{−1}$
(4) $a = h^C; b = g^v; c = b$　　　　/*$a = g^{−C−r};b = g^y; c = g^u$*/
(5) $R=\phi;$
(6) while ($x == 0$) do
(7) 　for ($r = s,s + 1\ldots, u$) do　/*new baby steps*/
(8) 　　$a=a*h$
(9) 　　if ($s==1$) then　　　　　/*check if $1\le x\le v$*/
(10) 　　　if ($a==1$) then
(11) 　　　　$x=r+C$
(12) 　　　　return ($x$)
(13) 　　　　break while
(14) 　　　else
(15) 　　　　$R = R\cup \{\;(a,r)\}\;$
(16) 　　　fi
(17) 　　else
(18) 　　　$R=R\cup \{\;(a,r)\}\;$
(19)  　　fi
(20) 　od
(21) 　while($x==0$ and $y<u^2$)do　　/*giant steps*/
(22) 　　if(there is a number $r$ such that $(b,r)\in R$) then
(23) 　　　$x=y+r+C$
(24) 　　　return($x$)
(25) 　　else
(26) 　　　$y=y+u$
(27) 　　　$b=b*c$
(28) 　　fi
(29) 　od
(30) 　$s=u+1;u=2u$　　　　　　　/*double step-width*/
(31) 　$c=c^2$
(32) od

計算一個元素g的Order副程式
(%i1)
Order(g,p,C,v):=block
([x,r,s,y,u,h,a,b,c,R],
print("1.變數初始化－－－－－－－"),
print("x=0"),x:0,
print("s=",s:1),
print("y=v=",y:v),
print("u=v=",u:v),
print("h=g"^"-1","=",g^"-1","≡",h:inv_mod(g,p),"(mod",p,")"),
print("從",g^concat("-",C),"(mod",p,")開始計算，a=h"^"C","=",h,""^C,"≡",a:power_mod(h,C,p),"(mod",p,")"),
print("b=g"^"v","=",g,""^v,"≡",b:power_mod(g,v,p),"(mod",p,")"),
print("c=b=",c:b),
print("R=",R:[]),
while x=0 do
  (print("2.計算BabyStep－－－－－－－"),
for r:s thru u do
   (print("計算",g^concat("-",C+r),"(mod",p,")","，a=a*h=",a,"*",h,"≡",a:mod(a*h,p),"(mod",p,")"),
   if s=1 then
      (if a=1 then
         (print("解答x=r+C=",r,"+",C,"=",x:r+C),
         return(x)
         )
      else
         (R:append(R,[[a,r]]),
         print("R=R∪",[a,r])
         )
      )
   else
      (R:append(R,[[a,r]]),
      print("R=R∪",[a,r])
      )
   ),
print("BabyStep=",R),
print("3.計算GiantStep－－－－－－－"),
while x=0 and y<u^2 do
   (if (r:assoc(b,R))#false then
      (print("計算",g,""^y,"≡",b,"(mod",p,")在R[",r,"]=",R[r],"裡面"),
      print("解答x=y+r+C=",y,"+",r,"+",C,"=",x:y+r+C),
      return(x)
      )
   else
      (print("計算",g,""^y,"≡",b,"(mod",p,")不在R裡面"),
      print("更新次方y=y+u=",y,"+",u,"=",y:y+u),
      print("b=b*c=",b,"*",c,"≡",b:mod(b*c,p),"(mod",p,")")
      )
   ),
print("s=u+1=",s:u+1),
print("u=2*u=",u:2*u),
print("倍增步長c=c"^2,"=",c:c^2)
  ),
return(x)
)$

$g^x \equiv 1 \pmod{p}$，$C+1$下限，初始步長$v$要是偶數
(%i5)
g:2;
p:181;
C:10;
v:2;
(g)　2
(p)　181
(C)　10
(v)　2

利用Baby_stepDoubleGiant_step方法計算$g$的order
(%i6)　x:Order(g,p,C,v);
1.變數初始化-------
$x=0$
$s=1$
$y=v=2$
$u=v=2$
$h=g^{-1}= 2^{-1}\equiv 91\pmod{181}$
從$2^{-10}\pmod{181}$開始計算，$a=h^C = 91 ^{10} \equiv 108\pmod{181}$
$b=g^v = 2 ^2 \equiv 4\pmod{181}$
$c=b=4$
$R=[]$
2.計算BabyStep-------
計算$2^{-11}\pmod{181}$，$a=a*h= 108 * 91 \equiv 54\pmod{181}$
$R=R\cup[54,1]$
計算$2^{-12}\pmod{181}$，$a=a*h= 54 * 91 \equiv 27\pmod{181}$
$R=R\cup[27,2]$
BabyStep=$[[54,1],[27,2]]$
3.計算GiantStep-------
計算$2^2 \equiv 4\pmod{181}$不在R裡面
更新次方$y=y+u=2+2=4$
$b=b*c= 4 * 4 \equiv 16\pmod{181}$
$s=u+1=3$
$u=2*u=4$
倍增步長$c=c^2=16$
2.計算BabyStep-------
計算$2^{-13}\pmod{181}$，$a=a*h= 27 * 91 \equiv 104\pmod{181}$
$R=R\cup[104,3]$
計算$2^{-14}\pmod{181}$，$a=a*h= 104 * 91 \equiv 52\pmod{181}$
$R=R\cup[52,4]$
BabyStep=$[[54,1],[27,2],[104,3],[52,4]]$
3.計算GiantStep-------
計算$2^4 \equiv 16\pmod{181}$不在R裡面
更新次方$y=y+u=4+4=8$
$b=b*c= 16 * 16 \equiv 75\pmod{181}$
計算$2^8 \equiv 75\pmod{181}$不在R裡面
更新次方$y=y+u= 8 + 4 = 12$
$b=b*c= 75 * 16 \equiv 114\pmod{181}$
計算$2^{12} \equiv 114\pmod{181}$不在R裡面
更新次方$y=y+u=12+4=16$
$b=b*c= 114 * 16 \equiv 14\pmod{181}$
$s=u+1= 5$
$u=2*u= 8$
倍增步長$c=c^2 = 256$
2.計算BabyStep-------
計算$2^{-15}\pmod{181}$，$a=a*h= 52 * 91 \equiv 26\pmod{181}$
$R=R\cup[26,5]$
計算$2^{-16}\pmod{181}$，$a=a*h= 26 * 91 \equiv 13\pmod{181}$
$R=R\cup[13,6]$
計算$2^{-17}\pmod{181}$，$a=a*h= 13 * 91 \equiv 97\pmod{181}$
$R=R\cup[97,7]$
計算$2^{-18}\pmod{181}$，$a=a*h= 97 * 91 \equiv 139\pmod{181}$
$R=R\cup[139,8]$
BabyStep=$[[54,1],[27,2],[104,3],[52,4],[26,5],[13,6],[97,7],[139,8]]$
3.計算GiantStep-------
計算$2^{16} \equiv 14\pmod{181}$不在R裡面
更新次方$y=y+u=16+8=24$
$b=b*c= 14 * 256 \equiv 145\pmod{181}$
計算$2^{24} \equiv 145\pmod{181}$不在R裡面
更新次方$y=y+u= 24 + 8 = 32$
$b=b*c= 145 * 256 \equiv 15\pmod{181}$
計算$2^{32} \equiv 15\pmod{181}$不在R裡面
更新次方$y=y+u= 32 + 8 = 40$
$b=b*c= 15 * 256 \equiv 39\pmod{181}$
計算$2^{40} \equiv 39\pmod{181}$不在R裡面
更新次方$y=y+u= 40 + 8 = 48$
$b=b*c= 39 * 256 \equiv 29\pmod{181}$
計算$2^{48} \equiv 29\pmod{181}$不在R裡面
更新次方$y=y+u= 48 + 8 = 56$
$b=b*c= 29 * 256 \equiv 3\pmod{181}$
計算$2^{56} \equiv 3\pmod{181}$不在R裡面
更新次方$y=y+u= 56 + 8 = 64$
$b=b*c= 3 * 256 \equiv 44\pmod{181}$
$s=u+1= 9$
$u=2*u= 16$
倍增步長$c=c^2 = 65536$
2.計算BabyStep-------
計算$2^{-19}\pmod{181}$，$a=a*h= 139 * 91 \equiv 160\pmod{181}$
$R=R\cup[160,9]$
計算$2^{-20}\pmod{181}$，$a=a*h= 160 * 91 \equiv 80\pmod{181}$
$R=R\cup[80,10]$
計算$2^{-21}\pmod{181}$，$a=a*h= 80 * 91 \equiv 40\pmod{181}$
$R=R\cup[40,11]$
計算$2^{-22}\pmod{181}$，$a=a*h= 40 * 91 \equiv 20\pmod{181}$
$R=R\cup[20,12]$
計算$2^{-23}\pmod{181}$，$a=a*h= 20 * 91 \equiv 10\pmod{181}$
$R=R\cup[10,13]$
計算$2^{-24}\pmod{181}$，$a=a*h= 10 * 91 \equiv 5\pmod{181}$
$R=R\cup[5,14]$
計算$2^{-25}\pmod{181}$，$a=a*h= 5 * 91 \equiv 93\pmod{181}$
$R=R\cup[93,15]$
計算$2^{-26}\pmod{181}$，$a=a*h= 93 * 91 \equiv 137\pmod{181}$
$R=R\cup[137,16]$
BabyStep=$[[54,1],[27,2],[104,3],[52,4],[26,5],[13,6],[97,7],[139,8],$
$[160,9],[80,10],[40,11],[20,12],[10,13],[5,14],[93,15],[137,16]]$
3.計算GiantStep-------
計算$2^{64} \equiv 44\pmod{181}$不在R裡面
更新次方$y=y+u= 64 + 16 = 80$
$b=b*c= 44 * 65536 \equiv 73\pmod{181}$
計算$2^{80} \equiv 73\pmod{181}$不在R裡面
更新次方$y=y+u= 80 + 16 = 96 $
$b=b*c= 73 * 65536 \equiv 117\pmod{181}$
計算$2^{96} \equiv 117\pmod{181}$不在R裡面
更新次方$y=y+u= 96 + 16 = 112 $
$b=b*c= 117 * 65536 \equiv 9\pmod{181}$
計算$2^{112} \equiv 9\pmod{181}$不在R裡面
更新次方$y=y+u= 112 + 16 = 128 $
$b=b*c= 9 * 65536 \equiv 126\pmod{181}$
計算$2^{128} \equiv 126\pmod{181}$不在R裡面
更新次方$y=y+u= 128 + 16 = 144 $
$b=b*c= 126 * 65536 \equiv 135\pmod{181}$
計算$2^{144} \equiv 135\pmod{181}$不在R裡面
更新次方$y=y+u= 144 + 16 = 160 $
$b=b*c= 135 * 65536 \equiv 80\pmod{181}$
計算$2^{160} \equiv 80\pmod{181}$在$R[10]=[80,10]$裡面
解答$x=y+r+C= 160 + 10 + 10 = 180 $
$s=u+1= 17$
$u=2*u= 32$
倍增步長$c=c^2 = 4294967296$
(x)　180

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
論文中演算法3.1將計算order和解離散對數問題結合在一起
$g^x \equiv d \pmod{p}$
$g^{y+r}\equiv d \pmod{p}$
$d^{-1}g^y\equiv g^{-r}\pmod{p}$
計算$g^{-r}$稱為Baby step
計算$d^{-1}g^y$稱為Giant step

輸入：$d,g \in G(d\ne 1)$，初始步長$v$($v$要是偶數)
輸出：執行結果$t=1$，若$d \in \langle\;g \rangle\;$，則離散對數問題的解$x=log_g d$
　　　執行結果$t=0$，若$d \notin \langle\;g \rangle\;$，則$g$的oder為$x=|\;\langle\;g \rangle\; |\;$
(1) $t=2;x=0$
(2) $s=1;y=v;u=v$
(3) $h=g^{−1}$
(4) $a=1;b=g^v;c=b$　　　/*$a=g^{−r},b=g^y,c=g^u$*/
(5) $R=\phi$
(6) $f=d^{−1}$
(7) while($t==2$)do
(8) 　for($r=s,s+1\ldots,u$) do　　/*new baby steps*/
(9) 　　$a=a*h$
(10) 　　$if(s==1)then$　　　　　/*check if $1\le x\le v$*/
(11) 　　　if($a==f$)then
(12) 　　　　$x=r;t=1$
(13) 　　　　break while
(14) 　　　else
(15) 　　　　if($a==1$)then
(16) 　　　　　$x=r;t=0$
(17) 　　　　　break while
(18) 　　　　else
(19) 　　　　　$R=R\cup \{\;(a,r) \}\;$
(20) 　　　　fi
(21) 　　　fi
(22) 　　else
(23) 　　　　$R=R\cup \{\;(a,r) \}\;$
(24)　　　fi
(25) 　od
(26) 　while($t==2$ and $y<u^2$) do　　/*giant steps*/
(27) 　　if(there is a number $r$ such　/*checking for discrete log.*/
(28) 　　　that $(f*b,r)\in R)$ then
(29) 　　　$x=y+r;t=1$
(30) 　　else
(31) 　　　if (there is a number $r$ such　　/*checking for the order of $g$*/
(32) 　　　　that $(b,r)\in R$) then
(33) 　　　　$x=y+r;t=0$
(34) 　　　else
(35) 　　　　$y=y+u$
(36) 　　　　$b=b*c$
(37) 　　　fi
(38) 　　fi
(39) 　od
(40) 　$s=u+1;u=2u$　　　　　　　　　　　/*double step-width*/
(41) 　$c=c^2$　　　　　　　　　　　　　　　
(42) od
(43) return($t,x$)

利用Baby_stepDoubleGiant_step方法解離散對數問題副程式
(%i1)
DiscreteLogarithm(d,g,p,v):=block
([t,x,s,y,u,h,a,b,c,R,f,r],
print("1.變數初始化－－－－－－－－－－－－"),
print("t=",t:2),
print("x=",x:0),
print("s=",s:1),
print("y=v=",y:v),
print("u=v=",u:v),
print("h=","g"^"-1","=",g^"-1","≡",h:inv_mod(g,p),"(mod",p,")"),
print("a=",a:1),
print("b=g"^"v","=",b:g^v),
print("c=b=",c:b),
print("R=",R:[]),
print("f=","d"^"-1","=",d^"-1","≡",f:inv_mod(d,p),"(mod",p,")"),
while t=2 do
  (print("2.計算BabyStep－－－－－－－－－－－－"),
for r:s thru u do
   (print("計算",g^concat("-",r),"(mod",p,")，a=a*h=",a,"*",h,"≡",a:mod(a*h,p),"(mod",p,")"),
   if s=1 then
      (if a=f then
         (print("x=r=",x:r),
         print("t=1",t:1),
         return(x)
         )
      else
         (if a=1 then
            (print("x=r=",x:r),
            print("t=0",t:0),
            return(x)
            )
         else
            (R:append(R,[[a,r]]),
            print("R=R∪",[a,r])
            )
         )
      )
   else
      (R:append(R,[[a,r]]),
      print("R=R∪",[a,r])
      )
   ),
print("BabyStep=",R),
print("3.計算GiantStep－－－－－－－－－－－－"),
while t=2 and y<u^2 do
   (if (r:assoc(mod(f*b,p),R))#false then
      (print("計算",d^"-1","*",g,""^y,"(mod",p,")，f*b=",f,"*",b,"≡",mod(f*b,p),"(mod",p,")在R[",r,"]=",R[r],"裡面"),
      print("解答x=y+r=",y,"+",r,"=",x:y+r),
      print("狀態t=",t:1),
      return(x)
      )
   else
      (print("計算",d^"-1","*",g,""^y,"(mod",p,")，f*b=",f,"*",b,"≡",mod(f*b,p),"(mod",p,")不在R裡面"),
      print("更新次方，y=y+u=",y,"+",u,"=",y:y+u),
      print("計算",g,""^y,"(mod",p,")，b=b*c=",b,"*",c,"≡",b:mod(b*c,p),"(mod",p,")")
      )
   ),
print("s=u+1=",s:u+1),
print("u=2*u=",u:2*u),
print("倍增步長，c=c"^2,"=",c:c^2),
k:k+1
  ),
return([t,x])
)$

$g^x \equiv d\pmod{p}$，初始步長$v$要是偶數
(%i5)
d:108;
g:2;
p:181;
v:2;
(d)　108
(g)　2
(p)　181
(v)　2

利用Baby_stepDoubleGiant_step方法計算g的order或解離散對數問題
(%i6)　[t,x]: DiscreteLogarithm(d,g,p,v);
1.變數初始化------------
$t=2$
$x=0$
$s=1$
$y=v=2$
$u=v=2$
$h=g^{-1}=2^{-1} \equiv 91 \pmod{181}$
$a=1$
$b=g^v=4$
$c=b=4$
$R=[]$
$f=d^{-1}=108^{-1} \equiv 119 \pmod{181}$
2.計算BabyStep------------
計算$2^{-1} \pmod{181}$，$a=a*h= 1*91 \equiv 91 \pmod{181}$
$R=R\cup [91,1]$
計算$2^{-2} \pmod{181}$，$a=a*h= 91*91 \equiv 136 \pmod{181}$
$R=R\cup [136,2]$
BabyStep$=[[91,1],[136,2]]$
3.計算GiantStep------------
計算$108^{-1}*2^2 \pmod{181}$，$f*b= 119*4 \equiv 114 \pmod{181}$不在R裡面
更新次方，$y=y+u=2+2=4$
計算$2^4 \pmod{181}$，$b=b*c= 4*4 \equiv 16 \pmod{181}$
$s=u+1=3$
$u=2*u=4$
倍增步長，$c=c^2=16$
2.計算BabyStep------------
計算$2^{-3} \pmod{181}$，$a=a*h= 136*91 \equiv 68 \pmod{181}$
$R=R\cup [68,3]$
計算$2^{-4} \pmod{181}$，$a=a*h= 68*91 \equiv 34 \pmod{181}$
$R=R\cup[34,4]$
BabyStep$=[[91,1],[136,2],[68,3],[34,4]]$
3.計算GiantStep------------
計算$108^{-1}*2^4 \pmod{181}$，$f*b= 119*16 \equiv 94 \pmod{181}$不在R裡面
更新次方，$y=y+u=4+4=8$
計算$2^8 \pmod{181}$，$b=b*c=16*16 \equiv 75 \pmod{181}$
計算$108^{-1}*2^8 \pmod{181}$，$f*b= 119*75 \equiv 56 \pmod{181}$不在R裡面
更新次方，$y=y+u=8+4=12$
計算$2^{12} \pmod{181}$，$b=b*c=75*16 \equiv 114 \pmod{181}$
計算$108^{-1}*2^{12} \pmod{181}$，$f*b= 119*114 \equiv 172 \pmod{181}$不在R裡面
更新次方，$y=y+u=12+4=16$
計算$2^{16} \pmod{181}$，$b=b*c=114*16 \equiv 14 \pmod{181}$
$s=u+1=5$
$u=2*u=8$
倍增步長，$c=c^2=256$
2.計算BabyStep------------
計算$2^{-5} \pmod{181}$，$a=a*h= 34*91 \equiv 17 \pmod{181}$
$R=R\cup [17,5]$
計算$2^{-6} \pmod{181}$，$a=a*h= 17*91 \equiv 99 \pmod{181}$
$R=R\cup [99,6]$
計算$2^{-7} \pmod{181}$，$a=a*h= 99*91 \equiv 140 \pmod{181}$
$R=R\cup [140,7]$
計算$2^{-8} \pmod{181}$，$a=a*h= 140*91 \equiv 70 \pmod{181}$
$R=R\cup [70,8]$
BabyStep$=[[91,1],[136,2],[68,3],[34,4],[17,5],[99,6],[140,7],[70,8]]$
3.計算GiantStep------------
計算$108^{-1}*2^{16} \pmod{181}$，$f*b= 119*14 \equiv 37 \pmod{181}$不在R裡面
更新次方，$y=y+u=16+8=24$
計算$2^{24} \pmod{181}$，$b=b*c= 14*256 \equiv 145 \pmod{181}$
計算$108^{-1}*2^{24} \pmod{181}$，$f*b= 119*145 \equiv 60 \pmod{181}$不在R裡面
更新次方，$y=y+u=24+8=32$
計算$2^{32} \pmod{181}$，$b=b*c= 145*256 \equiv 15 \pmod{181}$
計算$108^{-1}*2^{32} \pmod{181}$，$f*b= 119*15 \equiv 156 \pmod{181}$不在R裡面
更新次方，y=y+u= 32 + 8=40
計算$2^{40} \pmod{181}$，$b=b*c= 15*256 \equiv 39 \pmod{181}$
計算$108^{-1}*2^{40} \pmod{181}$，$f*b= 119*39 \equiv 116 \pmod{181}$不在R裡面
更新次方，y=y+u= 40 + 8=48
計算$2^{48} \pmod{181}$，$b=b*c= 39*256 \equiv 29 \pmod{181}$
計算$108^{-1}*2^{48} \pmod{181}$，$f*b= 119*29 \equiv 12 \pmod{181}$不在R裡面
更新次方，y=y+u= 48 + 8=56
計算$2^{56} \pmod{181}$，$b=b*c= 29*256 \equiv 3 \pmod{181}$
計算$108^{-1}*2^{56} \pmod{181}$，$f*b= 119*3 \equiv 176 \pmod{181}$不在R裡面
更新次方，y=y+u= 56 + 8=64
計算$2^{64} \pmod{181}$，$b=b*c= 3*256 \equiv 44 \pmod{181}$
$s=u+1=9$
$u=2*u=16$
倍增步長，$c=c^2=65536$
2.計算BabyStep------------
計算$2^{-9} \pmod{181}，a=a*h= 70*91 \equiv 35 \pmod{181}$
$R=R\cup [35,9]$
計算$2^{-10} \pmod{181}，a=a*h= 35*91 \equiv 108 \pmod{181}$
$R=R\cup [108,10]$
計算$2^{-11} \pmod{181}，a=a*h= 108*91 \equiv 54 \pmod{181}$
$R=R\cup [54,11]$
計算$2^{-12} \pmod{181}，a=a*h= 54*91 \equiv 27 \pmod{181}$
$R=R\cup [27,12]$
計算$2^{-13} \pmod{181}，a=a*h= 27*91 \equiv 104 \pmod{181}$
$R=R\cup [104,13]$
計算$2^{-14} \pmod{181}，a=a*h= 104*91 \equiv 52 \pmod{181}$
$R=R\cup [52,14]$
計算$2^{-15} \pmod{181}，a=a*h= 52*91 \equiv 26 \pmod{181}$
$R=R\cup [26,15]$
計算$2^{-16} \pmod{181}，a=a*h= 26*91 \equiv 13 \pmod{181}$
$R=R\cup [13,16]$
BabyStep$=[[91,1],[136,2],[68,3],[34,4],[17,5],[99,6],[140,7],[70,8],$
$[35,9],[108,10],[54,11],[27,12],[104,13],[52,14],[26,15],[13,16]]$
3.計算GiantStep------------
計算$108^{-1}*2^{64} \pmod{181}$，$f*b= 119*44 \equiv 168 \pmod{181}$不在R裡面
更新次方，y=y+u= 64 + 16=80
計算$2^{80} \pmod{181}$，$b=b*c= 44*65536 \equiv 73 \pmod{181}$
計算$108^{-1}*2^{80} \pmod{181}$，$f*b= 119*73 \equiv 180 \pmod{181}$不在R裡面
更新次方，y=y+u= 80 + 16=96
計算$2^{96} \pmod{181}$，$b=b*c= 73*65536 \equiv 117 \pmod{181}$
計算$108^{-1}*2^{96} \pmod{181}$，$f*b= 119*117 \equiv 167 \pmod{181}$不在R裡面
更新次方，y=y+u= 96 + 16=112
計算$2^{112} \pmod{181}$，$b=b*c= 117*65536 \equiv 9 \pmod{181}$
計算$108^{-1}*2^{112} \pmod{181}$，$f*b= 119*9 \equiv 166 \pmod{181}$不在R裡面
更新次方，y=y+u= 112 + 16=128
計算$2^{128} \pmod{181}$，$b=b*c= 9*65536 \equiv 126 \pmod{181}$
計算$108^{-1}*2^{128} \pmod{181}$，$f*b= 119*126 \equiv 152 \pmod{181}$不在R裡面
更新次方，y=y+u= 128 + 16=144
計算$2^{144} \pmod{181}$，$b=b*c= 126*65536 \equiv 135 \pmod{181}$
計算$108^{-1}*2^{144} \pmod{181}$，$f*b= 119*135 \equiv 137 \pmod{181}$不在R裡面
更新次方，y=y+u= 144 + 16=160
計算$2^{160} \pmod{181}$，$b=b*c= 135*65536 \equiv 80 \pmod{181}$
計算$108^{-1}*2^{160} \pmod{181}$，$f*b= 119*80 \equiv 108 \pmod{181}$在$R[10]=[108,10]$ 裡面
解答$x=y+r=160+10=170$
狀態$t=1$
$s=u+1=17$
$u=2*u=32$
倍增步長，$c=c^2=4294967296$
(%o6)　$[1,170]$

作者: bugmens 時間: 2020-8-25 08:24

4.解離散對數問題的方法-小步和線性增加步長的大步

原本的小步大步	小步和倍增步長的大步	小步和線性增加步長的大步
將答案改寫成$x=im+j$ 其中$m=\lceil\;\sqrt{p}\rceil\;$，$0\le i<m$，$0\le j<m$ $\alpha^x \equiv \beta \pmod{p}$ $\alpha^{im+j}\equiv \beta \pmod{p}$ $\alpha^j \equiv \beta(\alpha^{-m})^i \pmod{p}$ 計算$\alpha^j$稱為Baby step 計算$\beta(\alpha^{-m})^i$稱為Giant step 每次步長都是$\alpha^{-m}$	將答案改寫成$x=2^kvq+r$　($x$除以$2^kv$，商數$q$，餘數$r$) 其中$v$為偶數，$k\ge 0$，$1\le r \le 2^kv$ $\alpha^x \equiv \beta \pmod{p}$ $\displaystyle \alpha^{2^kvq+r}\equiv \beta \pmod{p}$ $\displaystyle \beta \alpha^{-r}\equiv (\alpha^{2^kv})^q \pmod{p}$ 計算$ \beta\alpha^{-r}$稱為Baby step 計算$(\alpha^{2^kv})^q$稱為Giant step 每次步長$\alpha^{2^kv}$隨著$k$值倍增	將答案改寫成$x=t_j-i$ 其中$t_0=2v$，$t_{j+1}=t_j+j+v+1$ $\alpha^x \equiv \beta \pmod{p}$ $\alpha^{t_j-i}\equiv \beta \pmod{p}$ $\alpha^{t_j} \equiv \beta \alpha^i \pmod{p}$ 計算$\beta \alpha^i$稱為Baby Step 計算$\alpha^{t_j}$稱為Giant Step 每次步長$\alpha^{t_j}$隨著$j$值線性增加($t_{j+1}=t_j+j+v+1$)

以$2^n \equiv 1\pmod{181}$，參數$v=2$為例。
\(\matrix{　&BabyStep&GiantStep\cr
　&2^0\equiv1\pmod{181}&　\cr
　&2^1\equiv2\pmod{181}&　\cr
j=0&2^2\equiv4\pmod{181}&t=2v=4\cr
j=j+1=1&2^{j+v}=2^3\equiv8\pmod{181}&t=t+j+v=4+1+2=7，2^7\equiv128\pmod{181}\cr
j=j+1=2&2^{j+v}=2^4\equiv16\pmod{181}&t=t+j+v=7+2+2=11，2^{11}\equiv57\pmod{181}\cr
j=j+1=3&2^{j+v}=2^5\equiv32\pmod{181}&t=t+j+v=11+3+2=16，2^{16}\equiv14\pmod{181}\cr
j=j+1=4&2^{j+v}=2^6\equiv64\pmod{181}&t=t+j+v=16+4+2=22，2^{22}\equiv172\pmod{181}\cr
j=j+1=5&2^{j+v}=2^7\equiv128\pmod{181}&t=t+j+v=22+5+2=29，2^{29}\equiv115\pmod{181}\cr
j=j+1=6&2^{j+v}=2^8\equiv75\pmod{181}&t=t+j+v=29+6+2=37，2^{37}\equiv118\pmod{181}\cr
j=j+1=7&2^{j+v}=2^9\equiv150\pmod{181}&t=t+j+v=37+7+2=46，2^{46}\equiv143\pmod{181}\cr
j=j+1=8&2^{j+v}=2^{10}\equiv119\pmod{181}&t=t+j+v=46+8+2=56，2^{56}\equiv3\pmod{181}\cr
j=j+1=9&2^{j+v}=\color{blue}{2^{11}\equiv57}\pmod{181}&t=t+j+v=56+9+2=67，2^{67}\equiv171\pmod{181}\cr
j=j+1=10&2^{j+v}=2^{12}\equiv114\pmod{181}&t=t+j+v=67+10+2=79，2^{79}\equiv127\pmod{181}\cr
j=j+1=11&2^{j+v}=2^{13}\equiv47\pmod{181}&t=t+j+v=79+11+2=92，2^{92}\equiv177\pmod{181}\cr
j=j+1=12&2^{j+v}=2^{14}\equiv94\pmod{181}&t=t+j+v=92+12+2=106，2^{106}\equiv167\pmod{181}\cr
j=j+1=13&2^{j+v}=2^{15}\equiv7\pmod{181}&t=t+j+v=106+13+2=121，2^{121}\equiv83\pmod{181}\cr
j=j+1=14&2^{j+v}=2^{16}\equiv14\pmod{181}&t=t+j+v=121+14+2=137，2^{137}\equiv76\pmod{181}\cr
j=j+1=15&2^{j+v}=2^{17}\equiv28\pmod{181}&t=t+j+v=137+15+2=154，2^{154}\equiv137\pmod{181}\cr
j=j+1=16&2^{j+v}=2^{18}\equiv56\pmod{181}&t=t+j+v=154+16+2=172，2^{172}\equiv70\pmod{181}\cr
j=j+1=17&2^{j+v}=2^{19}\equiv112\pmod{181}&t=t+j+v=172+17+2=191，\color{blue}{2^{191}\equiv57}\pmod{181}}\)
找到$2^{11}=2^{191}\equiv 57\pmod{181}$，故$n=191-11=180$，$2^{180}\equiv 1\pmod{181}$

演算法2.1，計算$g$的order。
輸入：$g \in G$，$v \in Z$，$v\ge 2$
輸出：$n=|\;g|\;$
(1)if (g == 1) then　　　　　　　　　　　　/* trivial case */
(2)　return (1)
(3)else
(4)　n = 0; i = 1; R ={(1, 0),(g,1)}; a = g　　　/* initialization */
(5)　while (n == 0 and i < v) do
(6)　　a = g*a; i = i + 1　　　　　　　　　　/* baby steps */
(7)　　if (a == 1) then
(8)　　　n = i　　　　　　　　　　　　　　/* found order among baby steps */
(9)　　　return (n)
(10)　　else
(11)　　　R = R ∪ {(a,i)}　　　　　　　　　/* update hash table */
(12)　　fi
(13)　od
(14)　j = 0; b = a*a; t = 2*v　　　　　　　　/* initialize giant steps ($t = t_j$) */
(15)　while (n == 0) do
(16)　　if (there exists a number i such that (b; i) 2 R) then  /* table lookup */
(17)　　　n = t - i　　　　　　　　　　　　　/* order of g */
(18)　　　return (n)
(19)　　　break while
(20)　　else
(21)　　　a = g*a; j = j + 1; R = R∪{(a,j + v)}　/*baby step */
(22)　　　b = a*b; t = t + j + v　　　　　　　　/* giant step */
(23)　　fi
(24)　od
(25)fi

參考資料：https://www.ams.org/journals/mco ... 5718-99-01141-2.pdf

計算一個元素g的Order副程式
(%i1)
Order(g,p,v):=block
([n,i,R,a],
if g=1 then
  (return(1)
  )
else
  (print("1.變數初始化－－－－－－－"),
print("n=",n:0),
print("i=",i:1),
print("R=",R:[[1,0],[g,1]]),
print("a=",a:g),
print("2.計算i=2~v的BabyStep－－－－－－－"),
while n=0 and i<v do
   (print("i=i+1=",i:i+1),
   print("計算",g,""^i,"(mod",p,")，","a=g*a=",g,"*",a,"≡",a:mod(g*a,p),"(mod",p,")"),
   if a=1 then
      (print("解答n=",n:i),
      return(n)
      )
   else
      (print("R=R∪[a,i]=",R:append(R,[[a,i]]))
      )
   ),
print("3.計算BabyStep和GiantStep－－－－－－－"),
print("j=",j:0),
print("b=a*a=",a,"*",a,"=",b:a^2),
print("t=2*v=2*",v,"=",t:2*v),
while n=0 do
   (if (i:assoc(b,R))#false then
      (print("R=",R),
      print("b=",b,"在R[",i+1,"]=",R[i+1],"裡面"),
      print("解答n=t-i=",t,"-",i,"=",n:t-i),
      return(n)
      )
   else
      (print("b=",b,"不在R裡面"),
      print("更新次方j=j+1=",j:j+1),
      print("計算BabyStep，",g^"j+v","=",g,""^(j+v),"(mod",p,")，","a=g*a=",g,"*",a,"≡",a:mod(g*a,p),"(mod",p,")"),
      print("R=R∪",[a,j+v]),R:append(R,[[a,j+v]]),
      print("更新次方t=t+j+v=",t,"+",j,"+",v,"=",t:t+j+v),
      print("計算GiantStep，g"^"t","=",g,""^t,"(mod",p,")，b=a*b=",a,"*",b,"≡",b:mod(a*b,p),"(mod",p,")")
      ),
   print("－－－－－－－－")
   )
  )
)$

$g^x \equiv 1\pmod{p}$，初始值v
(%i4)
g:2;
p:181;
v:2;
(g)　2
(p)　181
(v)　2

利用Baby_stepLinearGiant_step方法計算g的order
(%i5)　n:Order(g,p,v);
1.變數初始化-------
$n=0$
$i=1$
$R=[[1,0],[2,1]]$
$a=2$
2.計算i=2~v的BabyStep-------
$i=i+1= 2$
計算$2^2\pmod{181}$，$a=g*a=2 * 2 \equiv 4\pmod{181}$
$R=R\cup[a,i]= [[1,0],[2,1],[4,2]]$
3.計算BabyStep和GiantStep-------
$j=0$
$b=a*a=4*4=16$
$t=2*v=2*2=4$
$b=16$不在R裡面
更新次方$j=j+1=1$
計算BabyStep，$2^{j+v}=2^3\pmod{181}$，$a=g*a=2*4 \equiv 8\pmod{181}$
$R=R\cup [8,3]$
更新次方$t=t+j+v=4+1+2=7$
計算GiantStep，$g^t=2 ^7\pmod{181}$，$b=a*b=8*16 \equiv 128\pmod{181}$
--------
$b=128$不在R裡面
更新次方$j=j+1=2$
計算BabyStep，$2^{j+v}=2^4\pmod{181}$，$a=g*a=2*8 \equiv 16\pmod{181}$
$R=R\cup [16,4]$
更新次方$t=t+j+v=7+2+2=11$
計算GiantStep，$g^t=2^{11}\pmod{181}$，$b=a*b=16*128 \equiv 57\pmod{181}$
--------
$b=57$不在R裡面
更新次方$j=j+1=3$
計算BabyStep，$2^{j+v}=2^5\pmod{181}$，$a=g*a=2*16 \equiv 32\pmod{181}$
$R=R\cup [32,5]$
更新次方$t=t+j+v=11+3+2=16$
計算GiantStep，$g^t=2^{16}\pmod{181}$，$b=a*b=32*57 \equiv 14\pmod{181}$
--------
$b=14$不在R裡面
更新次方$j=j+1=4$
計算BabyStep，$2^{j+v}=2^6\pmod{181}$，$a=g*a=2*32 \equiv 64\pmod{181}$
$R=R\cup [64,6]$
更新次方$t=t+j+v=16+4+2=22$
計算GiantStep，$g^t=2 ^{22}\pmod{181}$，$b=a*b=64*14 \equiv 172\pmod{181}$
--------
$b=172$不在R裡面
更新次方$j=j+1=5$
計算BabyStep，$2^{j+v}=2^7\pmod{181}$，$a=g*a=2*64 \equiv 128\pmod{181}$
$R=R\cup [128,7]$
更新次方$t=t+j+v=22+5+2=29$
計算GiantStep，$g^t=2 ^{29}\pmod{181}$，$b=a*b=128*172 \equiv 115\pmod{181}$
--------
$b=115$不在R裡面
更新次方$j=j+1=6$
計算BabyStep，$2^{j+v}=2^8\pmod{181}$，$a=g*a=2*128 \equiv 75\pmod{181}$
$R=R\cup [75,8]$
更新次方$t=t+j+v=29+6+2=37$
計算GiantStep，$g^t=2^{37}\pmod{181}$，$b=a*b=75*115 \equiv 118\pmod{181}$
--------
$b=118$不在R裡面
更新次方$j=j+1=7$
計算BabyStep，$2^{j+v}=2^9\pmod{181}$，$a=g*a=2*75 \equiv 150\pmod{181}$
$R=R\cup [150,9]$
更新次方$t=t+j+v=37+7+2=46$
計算GiantStep，$g^t=2^{46}\pmod{181}$，$b=a*b=150*118 \equiv 143\pmod{181}$
--------
$b=143$不在R裡面
更新次方$j=j+1=8$
計算BabyStep，$2^{j+v}=2^{10}\pmod{181}$，$a=g*a=2*150 \equiv 119\pmod{181}$
$R=R\cup [119,10]$
更新次方$t=t+j+v=46+8+2=56$
計算GiantStep，$g^t=2^{56}\pmod{181}$，$b=a*b=119*143 \equiv 3\pmod{181}$
--------
$b=3$不在R裡面
更新次方$j=j+1=9$
計算BabyStep，$2^{j+v}=2^{11}\pmod{181}$，$a=g*a=2*119 \equiv 57\pmod{181}$
$R=R\cup [57,11]$
更新次方$t=t+j+v=56+9+2=67$
計算GiantStep，$g^t=2^{67}\pmod{181}$，$b=a*b=57*3 \equiv 171\pmod{181}$
--------
$b=171$不在R裡面
更新次方$j=j+1=10$
計算BabyStep，$2^{j+v}=2^{12}\pmod{181}$，$a=g*a=2*57 \equiv 114\pmod{181}$
$R=R\cup [114,12]$
更新次方$t=t+j+v=67+10+2=79$
計算GiantStep，$g^t=2^{79}\pmod{181}$，$b=a*b=114*171 \equiv 127\pmod{181}$
--------
$b=127$不在R裡面
更新次方$j=j+1=11$
計算BabyStep，$2^{j+v}=2^{13}\pmod{181}$，$a=g*a=2*114 \equiv 47\pmod{181}$
$R=R\cup [47,13]$
更新次方$t=t+j+v=79+11+2=92$
計算GiantStep，$g^t=2^{92}\pmod{181}$，$b=a*b=47*127 \equiv 177\pmod{181}$
--------
$b=177$不在R裡面
更新次方$j=j+1=12$
計算BabyStep，$2^{j+v}=2^{14}\pmod{181}$，$a=g*a=2*47 \equiv 94\pmod{181}$
$R=R\cup [94,14]$
更新次方$t=t+j+v=92+12+2=106$
計算GiantStep，$g^t=2^{106}\pmod{181}$，$b=a*b=94*177 \equiv 167\pmod{181}$
--------
$b=167$不在R裡面
更新次方$j=j+1=13$
計算BabyStep，$2^{j+v}=2^{15}\pmod{181}$，$a=g*a=2*94 \equiv 7\pmod{181}$
$R=R\cup [7,15]$
更新次方$t=t+j+v=106+13+2=121$
計算GiantStep，$g^t=2^{121}\pmod{181}$，$b=a*b=7*167 \equiv 83\pmod{181}$
--------
$b=83$不在R裡面
更新次方$j=j+1=14$
計算BabyStep，$2^{j+v}=2^{16}\pmod{181}$，$a=g*a=2*7 \equiv 14\pmod{181}$
$R=R\cup [14,16]$
更新次方$t=t+j+v=121+14+2=137$
計算GiantStep，$g^t=2^{137}\pmod{181}$，$b=a*b=14*83 \equiv 76\pmod{181}$
--------
$b=76$不在R裡面
更新次方$j=j+1=15$
計算BabyStep，$2^{j+v}=2^{17}\pmod{181}$，$a=g*a=2*14 \equiv 28\pmod{181}$
$R=R\cup [28,17]$
更新次方$t=t+j+v=137+15+2=154$
計算GiantStep，$g^t=2^{154}\pmod{181}$，$b=a*b=28*76 \equiv 137\pmod{181}$
--------
$b=137$不在R裡面
更新次方$j=j+1=16$
計算BabyStep，$2^{j+v}=2^{18}\pmod{181}$，$a=g*a=2*28 \equiv 56\pmod{181}$
$R=R\cup [56,18]$
更新次方$t=t+j+v=154+16+2=172$
計算GiantStep，$g^t=2^{172}\pmod{181}$，$b=a*b=56*137 \equiv 70\pmod{181}$
--------
$b=70$不在R裡面
更新次方$j=j+1=17$
計算BabyStep，$2^{j+v}=2^{19}\pmod{181}$，$a=g*a=2*56 \equiv 112\pmod{181}$
$R=R\cup [112,19]$
更新次方$t=t+j+v=172+17+2=191$
計算GiantStep，$g^t=2^{191}\pmod{181}$，$b=a*b=112*70 \equiv 57\pmod{181}$
--------
$R= [[1,0],[2,1],[4,2],[8,3],[16,4],[32,5],[64,6],[128,7],[75,8],[150,9],$
$[119,10],[57,11],[114,12],[47,13],[94,14],[7,15],[14,16],[28,17],[56,18],[112,19]]$
$b=57$在$R[12]=[57,11]$裡面
解答$n=t-i=191-11=180$
(n)　180

作者: bugmens 時間: 2020-9-15 21:32

5-1.低漢明權重(Low Hamming Weight)的離散對數問題-Heiman-Odlyzko方法

原本的離散對數問題$\alpha^x \equiv \beta \pmod{p}$的解$x$以二進位表示為
$\displaystyle x=\sum_{i=0}^{m-1}x_i2^i$，$x_i \in \{\;0,1 \}\;$，$0\le i \le m-1$，$m=\lceil\;log_2 ord(\alpha)\rceil\;$，$ord(\alpha)$代表$\alpha$的order
以$wt(x)$表示$x$的二進位中有多少個1，稱為$x$的漢明權重(Hamming Weight)。實務上以平方-相乘方法計算$\alpha^x$時，先將$x$表示成二進位，當遇到數字0時計算平方，遇到數字1時計算相乘，因為計算平方快於計算相乘，解$x$的二進位以較少的1來減少相乘運算，此時解$x$的漢明權重偏少，但$x$的漢明權重$wt(x)=t$太少時，有方法可以解出$x$。

以$2^x\equiv 108 \pmod{181}$，已知$x$的漢明權重為$t=4$為例。
$m=\lceil\;log_2 ord(2)\rceil\;=\lceil\;log_2 180\rceil\;=8$
$Z_m=\{\; 0,1,2,3,4,5,6,7\}\;$
取$Z_m$所有元素個數為2($\displaystyle |\;Y_1|\;=|\;Y_2|\;=\frac{t}{2}=2$)的子集合$Y_1$和$Y_2$。
\(\matrix{Y_1或Y_2 & val(Y_1)或val(Y_2) & \alpha^{val(Y_1)}\pmod{181}& \beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;0,1\}\;&2^0+2^1=3&2^3\equiv8&108*2^{-3}\equiv104 \cr
\{\;0,2\}\;&2^0+2^2=5&2^5\equiv32&108*2^{-5}\equiv26 \cr
\{\;0,3\}\;&2^0+2^3=9&2^9\equiv150&108*2^{-9}\equiv160 \cr
\{\;0,4\}\;&2^0+2^4=17&2^{17}\equiv28&108*2^{-17}\equiv159 \cr
\{\;0,5\}\;&2^0+2^5=33&2^{33}\equiv30&108*2^{-33}\equiv76 \cr
\{\;0,6\}\;&2^0+2^6=65&2^{65}\equiv88&108*2^{-65}\equiv174 \cr
\{\;0,7\}\;&2^0+2^7=129&2^{129}\equiv71&108*2^{-129}\equiv78 \cr
\{\;1,2\}\;&2^1+2^2=6&2^6\equiv64&108*2^{-6}\equiv13 \cr
\{\;1,3\}\;&2^1+2^3=10&2^{10}\equiv119&108*2^{-10}\equiv80 \cr
\{\;1,4\}\;&2^1+2^4=18&2^{18}\equiv56&108*2^{-18}\equiv170 \cr
\{\;1,5\}\;&2^1+2^5=34&2^{34}\equiv60&108*2^{-34}\equiv38 \cr
\{\;1,6\}\;&2^1+2^6=66&2^{66}\equiv176&108*2^{-66}\equiv87 \cr
\{\;1,7\}\;&2^1+2^7=130&2^{130}\equiv142&108*2^{-130}\equiv39 \cr
\{\;2,3\}\;&2^2+2^3=12&2^{12}\equiv114&108*2^{-12}\equiv20 \cr
\{\;2,4\}\;&2^2+2^4=20&2^{20}\equiv43&108*2^{-20}\equiv133 \cr
\{\;2,5\}\;&2^2+2^5=36&2^{36}\equiv59&108*2^{-36}\equiv100 \cr
\{\;2,6\}\;&2^2+2^6=68&2^{68}\equiv161&108*2^{-68}\equiv67 \cr
\{\;2,7\}\;&2^2+2^7=132&2^{132}\equiv25&108*2^{-132}\equiv55 \cr
\{\;3,4\}\;&2^3+2^4=24&2^{24}\equiv145&108*2^{-24}\equiv178 \cr
\{\;3,5\}\;&2^3+2^5=40&2^{40}\equiv39&108*2^{-40}\equiv142 \cr
\{\;3,6\}\;&2^3+2^6=72&2^{72}\equiv42&108*2^{-72}\equiv106 \cr
\{\;3,7\}\;&2^3+2^7=136&2^{136}\equiv38&108*2^{-136}\equiv60 \cr
\{\;4,5\}\;&2^4+2^5=48&2^{48}\equiv29&108*2^{-48}\equiv166 \cr
\{\;4,6\}\;&2^4+2^6=80&2^{80}\equiv73&108*2^{-80}\equiv180 \cr
\{\;4,7\}\;&2^4+2^7=144&2^{144}\equiv135&108*2^{-144}\equiv37 \cr
\{\;5,6\}\;&2^5+2^6=96&2^{96}\equiv117&108*2^{-96}\equiv168 \cr
\{\;5,7\}\;&2^5+2^7=160&2^{160}\equiv80&108*2^{-160}\equiv119 \cr
\{\;6,7\}\;&2^6+2^7=192&2^{192}\equiv114&108*2^{-192}\equiv20}\)
可找到
$2^{136}\equiv 108*2^{-34}\equiv 38\pmod{181}$，$Y_1=\{\;3,7 \}\;,Y_2=\{\;1,5 \}\;$，$x=136+34=170$
$2^{40}\equiv 108*2^{-130}\equiv 39\pmod{181}$，$Y_1=\{\;3,5 \}\;,Y_2=\{\;1,7 \}\;$，$x=40+130=170$
$2^{34}\equiv 108*2^{-136}\equiv 60\pmod{181}$，$Y_1=\{\;1,5 \}\;,Y_2=\{\;3,7 \}\;$，$x=34+136=170$
$2^{160}\equiv 108*2^{-10}\equiv 80\pmod{181}$，$Y_1=\{\;5,7 \}\;,Y_2=\{\;1,3 \}\;$，$x=160+10=170$
$2^{10}\equiv 108*2^{-160}\equiv 119\pmod{181}$，$Y_1=\{\;1,3 \}\;,Y_2=\{\;5,7 \}\;$，$x=10+160=170$
$2^{130}\equiv 108*2^{-40}\equiv 142\pmod{181}$，$Y_1=\{\;1,7 \}\;,Y_2=\{\;3,5 \}\;$，$x=130+40=170$
$170=(10101010)_2$漢明權重為4(4個1)。

演算法1
1. INPUT: $\alpha,\beta \in G$, an integer $m$ and an even integer $t$
2. For all $Y_1 \subseteq Z_m$ such that $|\;Y_1|\;=t/2$, compute $\alpha^{val(Y_1)}$
3. Sort the list of ordered pairs $(val(Y_1),\alpha^{val(Y_1)})$ by their second coordinates
4. For all $Y_2 \subseteq Z_m$ such that $|\;Y_1|\;=t/2$, compute $(\beta(\alpha^{val(Y_2)})^{-1})$
5. Sort the list of ordered pairs $(val(Y_2),\beta(\alpha^{val(Y_2)})^{-1})$ by their second coordinates
6. If possible, find $Y_1,Y_2$ such that $\alpha^{val(Y_1)}=\beta(\alpha^{val(Y_2)})^{-1}$
7. If the previous step is successful, output $log_{\alpha}\beta=(val(Y_1)+val(Y_2))\pmod{ord(\alpha)}$. Otherwise, output fail.

參考資料：https://citeseerx.ist.psu.edu/vi ... p=rep1&type=pdf

從L中取n個元素的子集合副程式
(%i1)
Combination(L,n):=block
([c:[],s],
if length(L)>n then
  (for r in L do
   (s:delete(r,L),
   c:unique(append(c,Combination(s,n)))
   )
  )
else
  (c:[L]),
return(c)
)$

例子：從[0,1,2,3]中取2個元素的子集合，共C(4,2)=6個
(%i2)　Combination([0,1,2,3],2);
(%o2)　$[[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]]$

解低漢明權重的離散對數問題Heiman-Odlyzko方法副程式
(%i3)
LowHammingWeightDLP1(alpha,beta,p,t):=block
([m,order,Zm:[],Y:[],valY:[],lenY,inv_alpha,ListY1:[],ListY2:[],indexY1:1,indexY2:1,x1:0,x2:0,x:0],
if mod(t,2)#0 then
  (print("t要是偶數"),return()),
print("ord(",alpha,")=",order:zn_order(alpha,p),"，",alpha^string(order),"≡1(mod",p,")"),
print("m=Ceiling(log2",order,")=",m:ceiling(log(order)/log(2))),
print("Zm=",Zm:makelist(i,i,0,m-1)),
print("從Zm取元素個數為","t"/2,"=",t/2,"個的子集合Y，共C(",m,",",t/2,")=",lenY:m!/((m-t/2)!*(t/2)!),"個"),
print("Y=",Y:Combination(Zm,t/2)),
print("val(Y)=Σ2"^"y","=",valY:create_list(apply("+",y),y,2^Y)),
print("計算[",alpha^"val(Y1)",",","val(Y1)]數對"),
print("ListY1=",ListY1:create_list([power_mod(alpha,valY[ i ],p),valY[ i ]],i,1,lenY)),
inv_alpha:inv_mod(alpha,p),
print("計算[",beta,"*",alpha^"-val(Y2)",",","val(Y2)]數對"),
print("ListY2=",ListY2:create_list([mod(beta*power_mod(inv_alpha,valY[ i ],p),p),valY[ i ]],i,1,lenY)),
print("由小到大排序"),
print("ListY1=",ListY1:sort(ListY1)),
print("ListY2=",ListY2:sort(ListY2)),
print("ListY1和ListY2互相比較找出相同值"),
while indexY1<=lenY and indexY2<=lenY do
  (if ListY1[indexY1][1]=ListY2[indexY2][1] then
   (x1: ListY1[indexY1][2],x2: ListY2[indexY2][2],
   print(alpha^string(x1),"≡",beta,"*",alpha^concat("-",x2),"≡",ListY1[indexY1][1],"(mod",p,")"),
   indexY1:indexY1+1,
   indexY2:indexY2+1
   )
else if ListY1[indexY1][1]<ListY2[indexY2][1] then
   (indexY1:indexY1+1)
else
   (indexY2:indexY2+1)
  ),
if x1=0 and x2=0 then
  (print("無解"),
return()
  )
else
  (return(x:mod(x1+x2,order)))
)$

$\alpha^x \equiv \beta\pmod{p}$，已知x的漢明權重$t=4$
(%i7)
alpha:2;
beta:108;
p:181;
t:4;
(alpha)　2
(beta)　108
(p)　181
(t)　4

解低漢明權重的離散對數問題-Heiman-Odlyzko方法
(%i8)　x: LowHammingWeightDLP1(alpha,beta,p,t);
$ord(2)=180$，$2^{180}\equiv 1 \pmod{181}$
$m=Ceiling(log_2 180)=8$
$Zm=[0,1,2,3,4,5,6,7]$
從$Zm$取元素個數為$\displaystyle \frac{t}{2}=2$個的子集合$Y$，共$C(8,2)=28$個
$Y=[[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],$
　　$[2,3],[2,4],[2,5],[2,6],[2,7],[3,4],[3,5],[3,6],[3,7],[4,5],[4,6],[4,7],[5,6],[5,7],[6,7]] $
$val(Y)=Σ2^y = [3,5,9,17,33,65,129,6,10,18,34,66,130,12,20,36,68,132,24,40,72,136,48,80,144,96,160,192] $
計算$[ 2^{val(Y1)},val(Y1)]$數對
$ListY1= [[8,3],[32,5],[150,9],[28,17],[30,33],[88,65],[71,129],[64,6],[119,10],[56,18],[60,34],[176,66],[142,130],[114,12],$
　　　　　$[43,20],[59,36],[161,68],[25,132],[145,24],[39,40],[42,72],[38,136],[29,48],[73,80],[135,144],[117,96],[80,160],[114,192]] $
計算$[ 108 * 2^{-val(Y2)},val(Y2)]$數對
$ListY2= [[104,3],[26,5],[160,9],[159,17],[76,33],[174,65],[78,129],[13,6],[80,10],[170,18],[38,34],[87,66],[39,130],[20,12],$
　　　　　$[133,20],[100,36],[67,68],[55,132],[178,24],[142,40],[106,72],[60,136],[166,48],[180,80],[37,144],[168,96],[119,160],[20,192]] $
由小到大排序
$ListY1= [[8,3],[25,132],[28,17],[29,48],[30,33],[32,5],[38,136],[39,40],[42,72],[43,20],[56,18],[59,36],[60,34],[64,6],$
　　　　　$[71,129],[73,80],[80,160],[88,65],[114,12],[114,192],[117,96],[119,10],[135,144],[142,130],[145,24],[150,9],[161,68],[176,66]] $
$ListY2= [[13,6],[20,12],[20,192],[26,5],[37,144],[38,34],[39,130],[55,132],[60,136],[67,68],[76,33],[78,129],[80,10],[87,66],$
　　　　　$[100,36],[104,3],[106,72],[119,160],[133,20],[142,40],[159,17],[160,9],[166,48],[168,96],[170,18],[174,65],[178,24],[180,80]] $
$ListY1$和$ListY2$互相比較找出相同值
$2^{136} \equiv 108 * 2^{-34} \equiv 38\pmod{181}$
$2^{40} \equiv 108 * 2^{-130} \equiv 39\pmod{181}$
$2^{34} \equiv 108 * 2^{-136} \equiv 60\pmod{181}$
$2^{160} \equiv 108 * 2^{-10} \equiv 80\pmod{181}$
$2^{10} \equiv 108 * 2^{-160} \equiv 119\pmod{181}$
$2^{130} \equiv 108 * 2^{-40} \equiv 142\pmod{181}$
(x)　170

作者: bugmens 時間: 2020-10-10 13:15

5-2.低漢明權重(Low Hamming Weight)的離散對數問題-Coppersmith方法

從上一篇文章可以發現Heiman-Odlyzko方法的關鍵在於列舉解$x=(10101010)_2$中1的可能位置$Y_1,Y_2$，$Y_1,Y_2$各有$C(m,\frac{t}{2})=C(8,2)=28$種，當$\alpha^{val(Y_1)}\equiv \beta \alpha^{-val(Y_2)}\pmod{p}$時，解$x=val(Y_1)+val(Y_2)\pmod{ord(\alpha)}$。

Coppersmith方法將解$x$二進位切成兩等份，每個等份再分別列舉1的可能位置，
$\{\;0,1,2,3 \}\;$任取2個的子集合$Y_1$，$\{\;4,5,6,7 \}\;$任取2個的子集合$Y_2$
$\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;0,1\}\;&2^0+2^1=3&2^3\equiv 8&\{\;4,5\}\;&2^4+2^5=48&108*2^{-48}\equiv 166\cr
\{\;0,2\}\;&2^0+2^2=5&2^5\equiv 32&\{\;4,6\}\;&2^4+2^6=80&108*2^{-80}\equiv 180\cr
\{\;0,3\}\;&2^0+2^3=9&2^9\equiv 150&\{\;4,7\}\;&2^4+2^7=144&108*2^{-144}\equiv 37\cr
\{\;1,2\}\;&2^1+2^2=6&2^6\equiv 64&\{\;5,6\}\;&2^5+2^6=96&108*2^{-96}\equiv 168\cr
\{\;1,3\}\;&2^1+2^3=10&2^{10}\equiv 119&\{\;5,7\}\;&2^5+2^7=160&108*2^{-160}\equiv 119\cr
\{\;2,3\}\;&2^2+2^3=12&2^{12}\equiv 114&\{\;6,7\}\;&2^6+2^7=192&108*2^{-192}\equiv 20}$
可找到
$2^{10}\equiv 108*2^{-160}\equiv 119 \pmod{181}$，$Y_1=\{\;1,3 \}\;$，$Y_2=\{\;5,7 \}\;$，$x=10+160=170$

再以$2^{142}\equiv 79\pmod{181}$為例，解$x=(142)_{10}=(10001110)_2$，1的分佈不平均。
$\{\;0,1,2,3 \}\;$任取2個的子集合$Y_1$，$\{\;4,5,6,7 \}\;$任取2個的子集合$Y_2$
$\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;0,1\}\;&2^0+2^1=3&2^3\equiv 8&\{\;4,5\}\;&2^4+2^5=48&79*2^{-48}\equiv 165\cr
\{\;0,2\}\;&2^0+2^2=5&2^5\equiv 32&\{\;4,6\}\;&2^4+2^6=80&79*2^{-80}\equiv 11\cr
\{\;0,3\}\;&2^0+2^3=9&2^9\equiv 150&\{\;4,7\}\;&2^4+2^7=144&79*2^{-144}\equiv 136\cr
\{\;1,2\}\;&2^1+2^2=6&2^6\equiv 64&\{\;5,6\}\;&2^5+2^6=96&79*2^{-96}\equiv 143\cr
\{\;1,3\}\;&2^1+2^3=10&2^{10}\equiv 119&\{\;5,7\}\;&2^5+2^7=160&79*2^{-160}\equiv 139\cr
\{\;2,3\}\;&2^2+2^3=12&2^{12}\equiv 114&\{\;6,7\}\;&2^6+2^7=192&79*2^{-192}\equiv 142}$
找不到$Y_1,Y_2$使得$\alpha^{val(Y_1)}\equiv \beta \alpha^{-val(Y_2)}\pmod{p}$

Coppersmitth方法將$Y_1,Y_2$各平移1個元素再重新列舉
$\{\;1,2,3,4 \}\;$任取2個的子集合$Y_1$，$\{\;5,6,7,0 \}\;$任取2個的子集合$Y_2$
$\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;1,2\}\;&2^1+2^2=6&2^6\equiv 64&\{\;0,5\}\;&2^0+2^5=33&79*2^{-33}\equiv 69\cr
\{\;1,3\}\;&2^1+2^3=10&2^{10}\equiv 119&\{\;0,6\}\;&2^0+2^6=65&79*2^{-65}\equiv 77\cr
\{\;1,4\}\;&2^1+2^4=18&2^{18}\equiv 56&\{\;0,7\}\;&2^0+2^7=129&79*2^{-129}\equiv 47\cr
\{\;2,3\}\;&2^2+2^3=12&2^{12}\equiv 114&\{\;5,6\}\;&2^5+2^6=96&79*2^{-96}\equiv 143\cr
\{\;2,4\}\;&2^2+2^4=20&2^{20}\equiv 43&\{\;5,7\}\;&2^5+2^7=160&79*2^{-160}\equiv 139\cr
\{\;3,4\}\;&2^3+2^4=24&2^{24}\equiv 145&\{\;6,7\}\;&2^6+2^7=192&79*2^{-192}\equiv 142}$
找不到$Y_1,Y_2$使得$\alpha^{val(Y_1)}\equiv \beta \alpha^{-val(Y_2)}\pmod{p}$

再將$Y_1,Y_2$各平移1個元素再重新列舉
$\{\;2,3,4,5 \}\;$任取2個的子集合$Y_1$，$\{\;6,7,0,1 \}\;$任取2個的子集合$Y_2$
$\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;2,3\}\;&2^2+2^3=12&2^{12}\equiv 114&\{\;0,1\}\;&2^0+2^1=3&79*2^{-3}\equiv 123\cr
\{\;2,4\}\;&2^2+2^4=20&2^{20}\equiv 43&\{\;0,6\}\;&2^0+2^6=65&79*2^{-65}\equiv 77\cr
\{\;2,5\}\;&2^2+2^5=36&2^{36}\equiv 59&\{\;0,7\}\;&2^0+2^7=129&79*2^{-129}\equiv 47\cr
\{\;3,4\}\;&2^3+2^4=24&2^{24}\equiv 145&\{\;1,6\}\;&2^1+2^6=66&79*2^{-66}\equiv 129\cr
\{\;3,5\}\;&2^3+2^5=40&2^{40}\equiv 39&\{\;1,7\}\;&2^1+2^7=130&79*2^{-130}\equiv 114\cr
\{\;4,5\}\;&2^4+2^5=48&2^{48}\equiv 29&\{\;6,7\}\;&2^6+2^7=192&79*2^{-192}\equiv 142}$
可找到
$2^{12}\equiv 79 *2^{-130}\equiv 114\pmod{181}$，$Y_1=\{\;2,3 \}\;$，$Y_2=\{\;1,7 \}\;$，$x=12+130=142$

Splitting families
假設$m$和$t$都是偶數且$0<t<m$，定義$(m,t)$的splitting system是符合以下2點的數對$(X,\cal{B})$
1.集合$X$有$m$個元素，集合$\beta$有$\displaystyle \frac{m}{2}$個$X$的子集合，$\cal{B}$稱為區塊(blocks)。
2.對所有$X$的子集合$Y$，$Y$有$t$個元素，存在一個區塊$B$使得$B$和$Y$的交集個數為$\displaystyle \frac{t}{2}$。

Coppersmith也提供一種產生$\displaystyle (\frac{m}{2};m,t)$的splitting system方法。
令$X=Z_m$，定義$B_i=\{\;i+j\pmod{m}:0\le j\le m/2-1\}\;$，$\cal B$$=\{\;B_i:0\le i \le m/2-1\}\;$

以$m=8,t=4$為例
$X=Z_m=\{\;0,1,2,3,4,5,6,7\}\;$，$B_0=\{\;0,1,2,3\}\;$，$B_1=\{\;1,2,3,4\}\;$，$B_2=\{\;2,3,4,5\}\;$，$B_3=\{\;3,4,5,6\}\;$，$\cal B$$=\{\;B_0,B_1,B_2,B_3\}\;$
子集合$Y=\{\;0,2,4,6\}\;$有4個元素，存在$B_0,B_1,B_2,B_3$和$Y$交集2個元素。
子集合$Y=\{\;1,3,5,7\}\;$有4個元素，存在$B_0,B_1,B_2,B_3$和$Y$交集2個元素。
子集合$Y=\{\;0,1,6,7\}\;$有4個元素，存在$B_0$和$Y$交集2個元素。
子集合$Y=\{\;0,2,5,7\}\;$有4個元素，存在$B_0$和$Y$交集2個元素。
子集合$Y=\{\;4,5,6,7\}\;$有4個元素，存在$B_2,B_3$和$Y$交集2個元素。

演算法2
1. INPUT:$\alpha,\beta \in G$, even integers $m$ and $t$, and an $(N; m, t)$-SS, $(Z_m,\cal{B})$, where $\cal B$$= \{\;B_i : 0 \le i \le N − 1\}\;$.
2. For $i = 0,\ldots,N−1$, perform the following steps:
(a) For all $Y_1\subseteq B_i$ such that $|\;Y_1|\; = t/2$, compute $\alpha^{val(Y_1)}$
(b) Sort the list of ordered pairs $(val(Y_1), \alpha^{val(Y_1)})$ by their second coordinates
(c) For all $Y_2 \subseteq Z_m\backslash\; B_i$ such that $|\;Y_2|\; = t/2$, compute $\beta(\alpha^{val(Y_2)})^{−1}$
(d) Sort the list of ordered pairs $(val(Y_2), \beta(\alpha^{val(Y_2)})^{−1})$ by their second coordinates
(e) If possible, find $Y_1$, $Y_2$ such that $\alpha^{val(Y_1)} = \beta(\alpha^{val(Y_2)})^{−1}$.
(f) If the previous step is successful, output $log_{\alpha}\beta=val(Y_1)+val(Y_2) \pmod{ord(\alpha)}$and QUIT. Otherwise, proceed to the next iteration of the FOR loop.

演算法3則隨機產生集合$B$，其中包含$\displaystyle \frac{m}{2}$個子集合，其餘步驟和演算法1,2相同。
演算法 3
1. INPUT: $\alpha,\beta \in G$, and even integers $m$ and $t$.
2. REPEAT the following steps:
(a) Let $B$ be a random $\displaystyle \frac{m}{2}$-subset of $X$
(b) For all $Y_1 \subseteq B$ such that $|\;Y_1|\;=t/2$, compute $\alpha^{val(Y_1)}$
(c) Sort the list of ordered pairs $(val(Y_1), \alpha^{val(Y_1)})$ by their second coordinates
(d) For all $Y_2 \subseteq Z_m\backslash\;B$ such that $|\;Y_2|\;=t/2$, compute $\beta(\alpha^{val(Y_2)})^{−1}$
(e) Sort the list of ordered pairs $(val(Y_2),\beta(\alpha^{val(Y_2)})^{−1})$ by their second coordinates
(f) If possible, find $Y_1$, $Y_2$ such that $\alpha^{val(Y_1)} =\beta(\alpha^{val(Y_2)})^{−1}$.
(g) If the previous step is successful, output $log_{\alpha}\beta=val(Y_1)+val(Y_2) \pmod{ord(\alpha)}$ and QUIT. Otherwise, proceed to the next iteration of the REPEAT loop.

參考資料：https://citeseerx.ist.psu.edu/vi ... p=rep1&type=pdf

從L中取n個元素的子集合副程式
(%i1)
Combination(L,n):=block
([c:[],s],
if length(L)>n then
  (for r in L do
   (s:delete(r,L),
   c:unique(append(c,Combination(s,n)))
   )
  )
else
  (c:[L]),
return(c)
)$

解低漢明權重的離散對數問題Coppersmith方法副程式
(%i2)
LowHammingWeightDLP2(alpha,beta,p,t):=block
([m,order,Beta,inv_alpha,i,Y1,Y2,valY1,valY2,lenY1,lenY2,ListY1,ListY2,indexY1:1,indexY2:1,x1:0,x2:0,x:0],
if mod(t,2)#0 then
  (print("t要是偶數"),return()),
print("ord(",alpha,")=",order:zn_order(alpha,p),"，",alpha^string(order),"≡1(mod",p,")"),
print("m=Ceiling(log2",order,")=",m:ceiling(log(order)/log(2))),
if mod(m,2)#0 then
  (print("m要是偶數"),return()),
print("Zm=",create_list(i,i,0,m-1)),
print("Bi={i+j (mod m):0≤j≤m/2-1}，β={Bi:0≤i≤m/2-1}"),
print("β=",Beta:create_list(create_list(mod(i+j,m),i,0,m/2-1),j,0,m/2-1)),
print("－－－－－－－－"),
inv_alpha:inv_mod(alpha,p),
for i:1 thru m/2 do
  (print("B",i-1,"=",Beta[ i ]),
print("從B",i-1,"取元素個數為","t"/2,"=",t/2,"個的子集合Y1，共C(","m"/2,",","t"/2,")=C(",m/2,",",t/2,")=",lenY1: (m/2)!/((t/2)!*(m/2-t/2)!),"個"),
print("Y1=",Y1:Combination(Beta[ i ],t/2)),
print("val(Y1)=Σ2"^"y","=",valY1:create_list(apply("+",y),y,2^Y1)),
print("計算[",alpha^"val(Y1)",",val(Y1)]數對"),
print("ListY1=",ListY1:create_list([power_mod(alpha,valY1[ i ],p),valY1[ i ]],i,1,lenY1)),
print("Zm\\B",i-1,"=",mod(Beta[ i ]+m/2,m)),
print("從Zm\\B",i-1,"取元素個數為","t"/2,"=",t/2,"個的子集合Y1，共C(","m"/2,",","t"/2,")=C(",m/2,",",t/2,")=",lenY2: (m/2)!/((t/2)!*(m/2-t/2)!),"個"),
print("Y2=",Y2:Combination(sort(mod(Beta[ i ]+m/2,m)),t/2)),
print("val(Y2)=Σ2"^"y","=",valY2:create_list(apply("+",y),y,2^Y2)),
print("計算[",beta,"*",alpha^"-val(Y2)",",","val(Y2)]數對"),
print("ListY2=",ListY2:create_list([mod(beta*power_mod(inv_alpha,valY2[ i ],p),p),valY2[ i ]],i,1,lenY2)),
print("由小到大排序"),
print("ListY1=",ListY1:sort(ListY1)),
print("ListY2=",ListY2:sort(ListY2)),
indexY1:1,indexY2:1,x1:0,x2:0,
while indexY1<=lenY1 and indexY2<=lenY2 do
   (if ListY1[indexY1][1]=ListY2[indexY2][1] then
      (print("ListY1和ListY2互相比較找到相同值"),
      x1: ListY1[indexY1][2],x2: ListY2[indexY2][2],
      print(alpha^string(x1),"≡",beta,"*",alpha^concat("-",x2),"≡",ListY1[indexY1][1],"(mod",p,")"),
      print("x=",x1,"+",x2,"=",x:mod(x1+x2,order)),
      indexY1:indexY1+1,
      indexY2:indexY2+1
      )
   else if ListY1[indexY1][1]<ListY2[indexY2][1] then
      (indexY1:indexY1+1)
   else
      (indexY2:indexY2+1)
   ),
if x1=0 and x2=0 then
   (print("ListY1和ListY2互相比較沒找到相同值")),
print("－－－－－－－－")
  ),
if x=0 then
  (print("無解"),
return()
  )
else
  (return(x))
)$

$\alpha^x \equiv \beta \pmod{p}$，已知$x$的漢明權重$t=4$
(%i6)
alpha:2;
beta:79;
p:181;
t:4;
(alpha)　2
(beta)　108
(p)　181
(t)　4

解低漢明權重的離散對數問題-Coppersmith方法
(%i7)　x: LowHammingWeightDLP2(alpha,beta,p,t);
$ord(2)=180$，$2^{180}\equiv 1\pmod{181}$
$m=Ceiling(log_2 180)=8$
$Zm= [\;0,1,2,3,4,5,6,7]\;$
$Bi=\{\; i+j \pmod{m}:0 \le j \le m/2-1 \}\;$，$\beta=\{\;Bi:0 \le i \le m/2-1 \};$
$\beta=[\;[\;0,1,2,3]\;,[\;1,2,3,4]\;,[\;2,3,4,5]\;,[\;3,4,5,6]\;]\;$
－－－－－－－－
$B0=[\;0,1,2,3]\;$
從$B0$取元素個數為$\displaystyle \frac{t}{2}=2$個的子集合$Y1$，共$\displaystyle C(\frac{m}{2},\frac{t}{2})=C(4,2)=6$個
$Y1=[\;[\;0,1]\;,[\;0,2]\;,[\;0,3]\;,[\;1,2]\;,[\;1,3]\;,[\;2,3]\;]\;$
$val(Y1)=Σ2^y = [\;3,5,9,6,10,12]\;$
計算$[\; 2^{val(Y1)},val(Y1)]\;$數對
$ListY1=[\;[\;8,3]\;,[\;32,5]\;,[\;150,9]\;,[\;64,6]\;,[\;119,10]\;,[\;114,12]\;]\;$
$Zm\backslash\; B0=[\;4,5,6,7]\;$
從$Zm \backslash\;B0$取元素個數為$\displaystyle \frac{t}{2}=2$個的子集合$Y1$，共$\displaystyle C(\frac{m}{2},\frac{t}{2})=C(4,2)=6$個
$Y2=[\;[\;4,5]\;,[\;4,6]\;,[\;4,7]\;,[\;5,6]\;,[\;5,7]\;,[\;6,7]\;]\;$
$val(Y2)=Σ2^y=[\;48,80,144,96,160,192]\;$
計算$[\;79 * 2^{-val(Y2)}, val(Y2)]\;$數對
$ListY2=[\;[\;165,48]\;,[\;11,80]\;,[\;136,144]\;,[\;143,96]\;,[\;139,160]\;,[\;142,192]\;]\;$
由小到大排序
$ListY1=[\;[\;8,3]\;,[\;32,5]\;,[\;64,6]\;,[\;114,12]\;,[\;119,10]\;,[\;150,9]\;]\;$
$ListY2=[\;[\;11,80]\;,[\;136,144]\;,[\;139,160]\;,[\;142,192]\;,[\;143,96]\;,[\;165,48]\;]\;$
$ListY1$和$ListY2$互相比較沒找到相同值
－－－－－－－－
$B1 = [\;1,2,3,4]\;$
從$B1$取元素個數為$\displaystyle  \frac{t}{2}=2$個的子集合$Y1$，共$\displaystyle C(\frac{m}{2},\frac{t}{2})=C(4,2)=6$個
$Y1= [\;[\;1,2]\;,[\;1,3]\;,[\;1,4]\;,[\;2,3]\;,[\;2,4]\;,[\;3,4]\;]\;$
$val(Y1)=Σ2^y = [\;6,10,18,12,20,24]\;$
計算$[\; 2^{val(Y1)},val(Y1)]\;$數對
$ListY1=[\;[\;64,6]\;,[\;119,10]\;,[\;56,18]\;,[\;114,12]\;,[\;43,20]\;,[\;145,24]\;]\;$
$Zm\backslash\;B1 = [\;5,6,7,0]\;$
從$Zm\backslash\;B1$取元素個數為$\displaystyle  \frac{t}{2}=2$個的子集合$Y1$，共$\displaystyle C(\frac{m}{2},\frac{t}{2})=C(4,2)=6$個
$Y2= [\;[\;0,5]\;,[\;0,6]\;,[\;0,7]\;,[\;5,6]\;,[\;5,7]\;,[\;6,7]\;]\;$
$val(Y2)=Σ2^y = [\;33,65,129,96,160,192]\;$
計算$[\; 79 * 2^{-val(Y2)}, val(Y2)]\;$數對
$ListY2=[\;[\;69,33]\;,[\;77,65]\;,[\;47,129]\;,[\;143,96]\;,[\;139,160]\;,[\;142,192]\;]\;$
由小到大排序
$ListY1=[\;[\;43,20]\;,[\;56,18]\;,[\;64,6]\;,[\;114,12]\;,[\;119,10]\;,[\;145,24]\;]\;$
$ListY2=[\;[\;47,129]\;,[\;69,33]\;,[\;77,65]\;,[\;139,160]\;,[\;142,192]\;,[\;143,96]\;]\;$
$ListY1$和$ListY2$互相比較沒找到相同值
－－－－－－－－
$B2=[\;2,3,4,5]\;$
從$B2$取元素個數為$\displaystyle  \frac{t}{2}=2$個的子集合$Y1$，共$\displaystyle C(\frac{m}{2},\frac{t}{2})=C(4,2)=6$個
$Y1=[\;[\;2,3]\;,[\;2,4]\;,[\;2,5]\;,[\;3,4]\;,[\;3,5]\;,[\;4,5]\;]\;$
$val(Y1)=Σ2^y=[\;12,20,36,24,40,48]\;$
計算$[\; 2^{val(Y1)},val(Y1)]\;$數對
$ListY1=[\;[\;114,12]\;,[\;43,20]\;,[\;59,36]\;,[\;145,24]\;,[\;39,40]\;,[\;29,48]\;]\;$
$Zm\backslash\;B2 = [\;6,7,0,1]\;$
從$Zm\backslash\;B2$取元素個數為$\displaystyle \frac{t}{2}=2$個的子集合$Y1$，共$\displaystyle C(\frac{m}{2},\frac{t}{2})=C(4,2)=6$個
$Y2= [\;[\;0,1]\;,[\;0,6]\;,[\;0,7]\;,[\;1,6]\;,[\;1,7]\;,[\;6,7]\;]\;$
$val(Y2)=Σ2^y = [\;3,65,129,66,130,192]\;$
計算$[\; 79 * 2^{-val(Y2)}, val(Y2)]\;$數對
$ListY2=[\;[\;123,3]\;,[\;77,65]\;,[\;47,129]\;,[\;129,66]\;,[\;114,130]\;,[\;142,192]\;]\;$
由小到大排序
$ListY1=[\;[\;29,48]\;,[\;39,40]\;,[\;43,20]\;,[\;59,36]\;,[\;114,12]\;,[\;145,24]\;]\;$
$ListY2=[\;[\;47,129]\;,[\;77,65]\;,[\;114,130]\;,[\;123,3]\;,[\;129,66]\;,[\;142,192]\;]\;$
$ListY1$和$ListY2$互相比較找到相同值
$2^{12}\equiv 79 * 2^{-130}\equiv 114 \pmod{181}$
$x=12+130=142$
－－－－－－－－
$B3 = [\;3,4,5,6]\;$
從$B3$取元素個數為$\displaystyle  \frac{t}{2}=2$個的子集合$Y1$，共$\displaystyle C(\frac{m}{2},\frac{t}{2})=C(4,2)=6$個
$Y1= [\;[\;3,4]\;,[\;3,5]\;,[\;3,6]\;,[\;4,5]\;,[\;4,6]\;,[\;5,6]\;]\;$
$val(Y1)=Σ2^y = [\;24,40,72,48,80,96]\;$
計算$[\; 2^{val(Y1)},val(Y1)]\;$數對
$ListY1=[\;[\;145,24]\;,[\;39,40]\;,[\;42,72]\;,[\;29,48]\;,[\;73,80]\;,[\;117,96]\;]\;$
$Zm\backslash\;B3 = [\;7,0,1,2]\;$
從$Zm\backslash\;B3$取元素個數為$\displaystyle  \frac{t}{2}=2$個的子集合$Y1$，共$\displaystyle C(\frac{m}{2},\frac{t}{2})=C(4,2)=6$個
$Y2= [\;[\;0,1]\;,[\;0,2]\;,[\;0,7]\;,[\;1,2]\;,[\;1,7]\;,[\;2,7]\;]\;$
$val(Y2)=Σ2^y = [\;3,5,129,6,130,132]\;$
計算$[\; 79 * 2^{-val(Y2)}, val(Y2)]\;$數對
$ListY2=[\;[\;123,3]\;,[\;76,5]\;,[\;47,129]\;,[\;38,6]\;,[\;114,130]\;,[\;119,132]\;]\;$
由小到大排序
$ListY1=[\;[\;29,48]\;,[\;39,40]\;,[\;42,72]\;,[\;73,80]\;,[\;117,96]\;,[\;145,24]\;]\;$
$ListY2=[\;[\;38,6]\;,[\;47,129]\;,[\;76,5]\;,[\;114,130]\;,[\;119,132]\;,[\;123,3]\;]\;$
$ListY1$和$ListY2$互相比較沒找到相同值
－－－－－－－－
(x)　142

作者: bugmens 時間: 2021-1-4 16:05

5-3.低漢明權重(Low Hamming Weight)的離散對數問題-可變參數的Splitting System

上一篇Coppersmitch方法將解$x$二進位切成兩等份，每個等份再分別列舉1的可能位置。可變參數的Splitting System方法則根據$t_s$值，調整集合$\cal{B}$的大小來列舉1的可能位置，所以說Coppersmitch方法可算是可變參數的Splitting System的特例。以下表格為兩種方法的比較。

Coppersmith Splitting System	可變參數的Splitting System
定義假設$m$和$t$都是偶數且$0<t<m$，定義$(m,t)$的splitting system是符合以下2點的數對$(X,\cal{B})$ 1.集合$X$有$m$個元素，集合$\cal{B}$有$\displaystyle \frac{m}{2}$個$X$的子集合，$\cal{B}$稱為區塊(blocks)。 2.對所有$X$的子集合$Y$，$Y$有$t$個元素，存在一個區塊$B$使得$B$和$Y$的交集個數為$\displaystyle \frac{t}{2}$。	定義假設$m$、$t$和$t_s$和都是整數且$0<t<m$、$0\le t_s \le t$，定義$(m,t,t_s)$的可變參數splitting system是符合以下2點的數對$(X,\cal{B})$ 1.集合$X$有$m$個元素，集合$\cal{B}$有$\displaystyle \Bigg\lfloor\; \frac{t_s m}{t}\Bigg\rfloor\;$個$X$的子集合，$\cal{B}$稱為區塊(blocks)。 2.對所有$X$的子集合$Y$，$Y$有$t$個元素，存在一個區塊$B$使得$B$和$Y$的交集個數為$\displaystyle t_s$。
產生$\displaystyle (\frac{m}{2};m,t)$的Coppersmith splitting system方法令$X=Z_m$，定義$B_i=\{\;i+j\pmod{m}:0\le j\le m/2-1\}\;$ $\cal B$$=\{\;B_i:0\le i \le m/2-1\}\;$	產生$\displaystyle (m;m,t,t_s)$的可變參數splitting system方法令$X=Z_m$，定義$B_i=\{\;i+j\pmod{m}:0\le j\le \Bigg\lfloor\;\frac{t_sm}{t}\Bigg\rfloor\;-1\}\;$ $\cal B$$=\{\;B_i:0\le i \le m-1\}\;$
以$m=8,t=4$為例(解$x$有8位元，其中有4個1，分成2個1和2個1分別列舉) $X=Z_m=\{\;0,1,2,3,4,5,6,7\}\;$，$B_0=\{\;0,1,2,3\}\;$，$B_1=\{\;1,2,3,4\}\;$，$B_2=\{\;2,3,4,5\}\;$，$B_3=\{\;3,4,5,6\}\;$，$\cal B$$=\{\;B_0,B_1,B_2,B_3\}\;$ 子集合$Y=\{\;0,2,4,6\}\;$有4個元素，存在$B_0,B_1,B_2,B_3$和$Y$交集2個元素。子集合$Y=\{\;1,3,5,7\}\;$有4個元素，存在$B_0,B_1,B_2,B_3$和$Y$交集2個元素。子集合$Y=\{\;0,1,6,7\}\;$有4個元素，存在$B_0$和$Y$交集2個元素。子集合$Y=\{\;0,2,5,7\}\;$有4個元素，存在$B_0$和$Y$交集2個元素。子集合$Y=\{\;4,5,6,7\}\;$有4個元素，存在$B_2,B_3$和$Y$交集2個元素。	以$m=8,t=4,t_s=1$為例(解$x$有8位元，其中有4個1，分成1個1和3個1分別列舉) $X=Z_m=\{\;0,1,2,3,4,5,6,7\}\;$，$B_0=\{\;0,1\}\;$，$B_1=\{\;1,2\}\;$，$B_2=\{\;2,3\}\;$，$B_3=\{\;3,4\}\;$，$B_4=\{\;4,5\}\;$，$B_5=\{\;5,6\}\;$，$B_6=\{\;6,7\}\;$，$B_7=\{\;7,0\}\;$，$\cal B$$=\{\;B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\}\;$ 子集合$Y=\{\;0,2,4,6\}\;$有4個元素，存在$B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7$和$Y$交集1個元素。子集合$Y=\{\;1,3,5,7\}\;$有4個元素，存在$B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7$和$Y$交集1個元素。子集合$Y=\{\;0,1,6,7\}\;$有4個元素，存在$B_0,B_1,B_5,B_6,B_7$和$Y$交集1個元素。子集合$Y=\{\;0,2,5,7\}\;$有4個元素，存在$B_0,B_1,B_2,B_4,B_5,B_6,B_7$和$Y$交集1個元素。子集合$Y=\{\;4,5,6,7\}\;$有4個元素，存在$B_3,B_4,B_5,B_6,B_7$和$Y$交集1個元素。
	以$m=8,t=4,t_s=2$為例 $X=Z_m=\{\;0,1,2,3,4,5,6,7\}\;$，$B_0=\{\;0,1,2,3\}\;$，$B_1=\{\;1,2,3,4\}\;$，$B_2=\{\;2,3,4,5\}\;$，$B_3=\{\;3,4,5,6\}\;$，$B_4=\{\;4,5,6,7\}\;$，$B_5=\{\;5,6,7,0\}\;$，$B_6=\{\;6,7,0,1\}\;$，$B_7=\{\;7,0,1,2\}\;$，$\cal B$$=\{\;B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\}\;$ $B_0,B_1,B_2,B_3$和Coppersmith splitting system相同 $B_4,B_5,B_6,B_7$則是$B_0,B_1,B_2,B_3$的補集。

演算法和上一篇大致相同，僅集合$\cal{B}$大小不同。

以$2^{142}\equiv 79\pmod{181}$為例，解$x=(142)_{10}=(10001110)_2$，1的分佈不平均。

$\{\;0,1 \}\;$任取1個的子集合$Y_1$，$\{\;2,3,4,5,6,7 \}\;$任取3個的子集合$Y_2$
\(\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;0\}\;&2^0=1&2^1\equiv 2&\{\;2,3,4\}\;& 2^2+2^3+2^4=28&79*2^{-28}\equiv 36\cr
\{\;1\}\;&2^1=2&2^2\equiv 4&\{\;2,3,5\}\;&2^2+2^3+2^5=44&79*2^{-44}\equiv 106\cr
&&&\{\;2,3,6\}\;&2^2+2^3+2^6=76&79*2^{-76}\equiv 176\cr
&&&\{\;2,3,7\}\;&2^2+2^3+2^7=140&79*2^{-140}\equiv 4\cr
&&&\{\;2,4,5\}\;&2^2+2^4+2^5=52&79*2^{-52}\equiv 180\cr
&&&\{\;2,4,6\}\;&2^2+2^4+2^6=84&79*2^{-84}\equiv 12\cr
&&&\{\;2,4,7\}\;&2^2+2^4+2^7=148&79*2^{-148}\equiv 99\cr
&&&\{\;2,5,6\}\;&2^2+2^5+2^6=100&79*2^{-100}\equiv 156\cr
&&&\{\;2,5,7\}\;&2^2+2^5+2^7=164&79*2^{-164}\equiv 20\cr
&&&\{\;2,6,7\}\;&2^2+2^6+2^7=196&79*2^{-196}\equiv 122\cr
&&&\{\;3,4,5\}\;&2^3+2^4+2^5=56&79*2^{-56}\equiv 147\cr
&&&\{\;3,4,6\}\;&2^3+2^4+2^6=88&79*2^{-88}\equiv 46\cr
&&&\{\;3,4,7\}\;&2^3+2^4+2^7=152&79*2^{-152}\equiv 108\cr
&&&\{\;3,5,6\}\;&2^3+2^5+2^6=104&79*2^{-104}\equiv 55\cr
&&&\{\;3,5,7\}\;&2^3+2^5+2^7=168&79*2^{-168}\equiv 137\cr
&&&\{\;3,6,7\}\;&2^3+2^6+2^7=200&79*2^{-200}\equiv 166\cr
&&&\{\;4,5,6\}\;&2^4+2^5+2^6=112&79*2^{-112}\equiv 49\cr
&&&\{\;4,5,7\}\;&2^4+2^5+2^7=176&79*2^{-176}\equiv 178\cr
&&&\{\;4,6,7\}\;&2^4+2^6+2^7=208&79*2^{-208}\equiv 36\cr
&&&\{\;5,6,7\}\;&2^5+2^6+2^7=224&79*2^{-224}\equiv 106}\)
可找到
$2^2\equiv79*2^{-140}\equiv 4\pmod{181}$，$Y_1=\{\;1\}\;$，$Y_2=\{\;2,3,7\}\;$，$x=2+140=142$

$\{\;1,2 \}\;$任取1個的子集合$Y_1$，$\{\;0,3,4,5,6,7 \}\;$任取3個的子集合$Y_2$
\(\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;1\}\;&2^1=2&2^2\equiv 4&\{\;0,3,4\}\;&2^0+2^3+2^4=25&79*2^{-25}\equiv107\cr
\{\;2\}\;&2^2=4&2^4\equiv 16&\{\;0,3,5\}\;&2^0+2^3+2^5=41&79*2^{-41}\equiv124\cr
&&&\{\;0,3,6\}\;&2^0+2^3+2^6=73&79*2^{-73}\equiv141\cr
&&&\{\;0,3,7\}\;&2^0+2^3+2^7=137&79*2^{-137}\equiv32\cr
&&&\{\;0,4,5\}\;&2^0+2^4+2^5=49&79*2^{-49}\equiv173\cr
&&&\{\;0,4,6\}\;&2^0+2^4+2^6=81&79*2^{-81}\equiv96\cr
&&&\{\;0,4,7\}\;&2^0+2^4+2^7=145&79*2^{-145}\equiv68\cr
&&&\{\;0,5,6\}\;&2^0+2^5+2^6=97&79*2^{-97}\equiv162\cr
&&&\{\;0,5,7\}\;&2^0+2^5+2^7=161&79*2^{-161}\equiv160\cr
&&&\{\;0,6,7\}\;&2^0+2^6+2^7=193&79*2^{-193}\equiv71\cr
&&&\{\;3,4,5\}\;&2^3+2^4+2^5=56&79*2^{-56}\equiv147\cr
&&&\{\;3,4,6\}\;&2^3+2^4+2^6=88&79*2^{-88}\equiv46\cr
&&&\{\;3,4,7\}\;&2^3+2^4+2^7=152&79*2^{-152}\equiv108\cr
&&&\{\;3,5,6\}\;&2^3+2^5+2^6=104&79*2^{-104}\equiv55\cr
&&&\{\;3,5,7\}\;&2^3+2^5+2^7=168&79*2^{-168}\equiv137\cr
&&&\{\;3,6,7\}\;&2^3+2^6+2^7=200&79*2^{-200}\equiv166\cr
&&&\{\;4,5,6\}\;&2^4+2^5+2^6=112&79*2^{-112}\equiv49\cr
&&&\{\;4,5,7\}\;&2^4+2^5+2^7=176&79*2^{-176}\equiv178\cr
&&&\{\;4,6,7\}\;&2^4+2^6+2^7=208&79*2^{-208}\equiv36\cr
&&&\{\;5,6,7\}\;&2^5+2^6+2^7=224&79*2^{-224}\equiv106}\)
找不到$Y_1,Y_2$使得$\alpha^{val(Y_1)}\equiv \beta \alpha^{-val(Y_2)}\pmod{p}$

$\{\;2,3 \}\;$任取1個的子集合$Y_1$，$\{\;0,1,4,5,6,7 \}\;$任取3個的子集合$Y_2$
\(\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;2\}\;&2^2=4&2^4\equiv 16&\{\;0,1,4\}\;&2^0+2^1+2^4=19&79*2^{-19}\equiv151\cr
\{\;3\}\;&2^3=8&2^8\equiv 75&\{\;0,1,5\}\;&2^0+2^1+2^5=35&79*2^{-35}\equiv153\cr
&&&\{\;0,1,6\}\;&2^0+2^1+2^6=67&79*2^{-67}\equiv155\cr
&&&\{\;0,1,7\}\;&2^0+2^1+2^7=131&79*2^{-131}\equiv57\cr
&&&\{\;0,4,5\}\;&2^0+2^4+2^5=49&79*2^{-49}\equiv173\cr
&&&\{\;0,4,6\}\;&2^0+2^4+2^6=81&79*2^{-81}\equiv96\cr
&&&\{\;0,4,7\}\;&2^0+2^4+2^7=145&79*2^{-145}\equiv68\cr
&&&\{\;0,5,6\}\;&2^0+2^5+2^6=97&79*2^{-97}\equiv162\cr
&&&\{\;0,5,7\}\;&2^0+2^5+2^7=161&79*2^{-161}\equiv160\cr
&&&\{\;0,6,7\}\;&2^0+2^6+2^7=193&79*2^{-193}\equiv71\cr
&&&\{\;1,4,5\}\;&2^1+2^4+2^5=50&79*2^{-50}\equiv177\cr
&&&\{\;1,4,6\}\;&2^1+2^4+2^6=82&79*2^{-82}\equiv48\cr
&&&\{\;1,4,7\}\;&2^1+2^4+2^7=146&79*2^{-146}\equiv34\cr
&&&\{\;1,5,6\}\;&2^1+2^5+2^6=98&79*2^{-98}\equiv81\cr
&&&\{\;1,5,7\}\;&2^1+2^5+2^7=162&79*2^{-162}\equiv80\cr
&&&\{\;1,6,7\}\;&2^1+2^6+2^7=194&79*2^{-194}\equiv126\cr
&&&\{\;4,5,6\}\;&2^4+2^5+2^6=112&79*2^{-112}\equiv49\cr
&&&\{\;4,5,7\}\;&2^4+2^5+2^7=176&79*2^{-176}\equiv178\cr
&&&\{\;4,6,7\}\;&2^4+2^6+2^7=208&79*2^{-208}\equiv36\cr
&&&\{\;5,6,7\}\;&2^5+2^6+2^7=224&79*2^{-224}\equiv106}\)
找不到$Y_1,Y_2$使得$\alpha^{val(Y_1)}\equiv \beta \alpha^{-val(Y_2)}\pmod{p}$

$\{\;3,4 \}\;$任取1個的子集合$Y_1$，$\{\;0,1,2,5,6,7 \}\;$任取3個的子集合$Y_2$
\(\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;3\}\;&2^3=8&2^8\equiv 75&\{\;0,1,2\}\;&2^0+2^1+2^2=7&79*2^{-7}\equiv19\cr
\{\;4\}\;&2^4=16&2^{16}\equiv 14&\{\;0,1,5\}\;&2^0+2^1+2^5=35&79*2^{-35}\equiv153\cr
&&&\{\;0,1,6\}\;&2^0+2^1+2^6=67&79*2^{-67}\equiv155\cr
&&&\{\;0,1,7\}\;&2^0+2^1+2^7=131&79*2^{-131}\equiv57\cr
&&&\{\;0,2,5\}\;&2^0+2^2+2^5=37&79*2^{-37}\equiv174\cr
&&&\{\;0,2,6\}\;&2^0+2^2+2^6=69&79*2^{-69}\equiv84\cr
&&&\{\;0,2,7\}\;&2^0+2^2+2^7=133&79*2^{-133}\equiv150\cr
&&&\{\;0,5,6\}\;&2^0+2^5+2^6=97&79*2^{-97}\equiv162\cr
&&&\{\;0,5,7\}\;&2^0+2^5+2^7=161&79*2^{-161}\equiv160\cr
&&&\{\;0,6,7\}\;&2^0+2^6+2^7=193&79*2^{-193}\equiv71\cr
&&&\{\;1,2,5\}\;&2^1+2^2+2^5=38&79*2^{-38}\equiv87\cr
&&&\{\;1,2,6\}\;&2^1+2^2+2^6=70&79*2^{-70}\equiv42\cr
&&&\{\;1,2,7\}\;&2^1+2^2+2^7=134&79*2^{-134}\equiv75\cr
&&&\{\;1,5,6\}\;&2^1+2^5+2^6=98&79*2^{-98}\equiv81\cr
&&&\{\;1,5,7\}\;&2^1+2^5+2^7=162&79*2^{-162}\equiv80\cr
&&&\{\;1,6,7\}\;&2^1+2^6+2^7=194&79*2^{-194}\equiv126\cr
&&&\{\;2,5,6\}\;&2^2+2^5+2^6=100&79*2^{-100}\equiv156\cr
&&&\{\;2,5,7\}\;&2^2+2^5+2^7=164&79*2^{-164}\equiv20\cr
&&&\{\;2,6,7\}\;&2^2+2^6+2^7=196&79*2^{-196}\equiv122\cr
&&&\{\;5,6,7\}\;&2^5+2^6+2^7=224&79*2^{-224}\equiv106}\)
可找到
$2^8\equiv79*2^{-134}\equiv 75\pmod{181}$，$Y_1=\{\;3\}\;$，$Y_2=\{\;1,2,7\}\;$，$x=8+134=142$

$\{\;4,5 \}\;$任取1個的子集合$Y_1$，$\{\;0,1,2,3,6,7 \}\;$任取3個的子集合$Y_2$
\(\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;4\}\;&2^4=16&2^{16}\equiv 14&\{\;0,1,2\}\;&2^0+2^1+2^2=7&79*2^{-7}\equiv19\cr
\{\;5\}\;&2^5=32&2^{32}\equiv 15&\{\;0,1,3\}\;&2^0+2^1+2^3=11&79*2^{-11}\equiv103\cr
&&&\{\;0,1,6\}\;&2^0+2^1+2^6=67&79*2^{-67}\equiv155\cr
&&&\{\;0,1,7\}\;&2^0+2^1+2^7=131&79*2^{-131}\equiv57\cr
&&&\{\;0,2,3\}\;&2^0+2^2+2^3=13&79*2^{-13}\equiv71\cr
&&&\{\;0,2,6\}\;&2^0+2^2+2^6=69&79*2^{-69}\equiv84\cr
&&&\{\;0,2,7\}\;&2^0+2^2+2^7=133&79*2^{-133}\equiv150\cr
&&&\{\;0,3,6\}\;&2^0+2^3+2^6=73&79*2^{-73}\equiv141\cr
&&&\{\;0,3,7\}\;&2^0+2^3+2^7=137&79*2^{-137}\equiv32\cr
&&&\{\;0,6,7\}\;&2^0+2^6+2^7=193&79*2^{-193}\equiv71\cr
&&&\{\;1,2,3\}\;&2^1+2^2+2^3=14&79*2^{-14}\equiv126\cr
&&&\{\;1,2,6\}\;&2^1+2^2+2^6=70&79*2^{-70}\equiv42\cr
&&&\{\;1,2,7\}\;&2^1+2^2+2^7=134&79*2^{-134}\equiv75\cr
&&&\{\;1,3,6\}\;&2^1+2^3+2^6=74&79*2^{-74}\equiv161\cr
&&&\{\;1,3,7\}\;&2^1+2^3+2^7=138&79*2^{-138}\equiv16\cr
&&&\{\;1,6,7\}\;&2^1+2^6+2^7=194&79*2^{-194}\equiv126\cr
&&&\{\;2,3,6\}\;&2^2+2^3+2^6=76&79*2^{-76}\equiv176\cr
&&&\{\;2,3,7\}\;&2^2+2^3+2^7=140&79*2^{-140}\equiv4\cr
&&&\{\;2,6,7\}\;&2^2+2^6+2^7=196&79*2^{-196}\equiv122\cr
&&&\{\;3,6,7\}\;&2^3+2^6+2^7=200&79*2^{-200}\equiv166}\)
找不到$Y_1,Y_2$使得$\alpha^{val(Y_1)}\equiv \beta \alpha^{-val(Y_2)}\pmod{p}$

$\{\;5,6 \}\;$任取1個的子集合$Y_1$，$\{\;0,1,2,3,4,7 \}\;$任取3個的子集合$Y_2$
\(\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;5\}\;&2^5=32&2^{32}\equiv 15&\{\;0,1,2\}\;&2^0+2^1+2^2=7&79*2^{-7}\equiv19\cr
\{\;6\}\;&2^6=64&2^{64}\equiv 44&\{\;0,1,3\}\;&2^0+2^1+2^3=11&79*2^{-11}\equiv103\cr
&&&\{\;0,1,4\}\;&2^0+2^1+2^4=19&79*2^{-19}\equiv151\cr
&&&\{\;0,1,7\}\;&2^0+2^1+2^7=131&79*2^{-131}\equiv57\cr
&&&\{\;0,2,3\}\;&2^0+2^2+2^3=13&79*2^{-13}\equiv71\cr
&&&\{\;0,2,4\}\;&2^0+2^2+2^4=21&79*2^{-21}\equiv83\cr
&&&\{\;0,2,7\}\;&2^0+2^2+2^7=133&79*2^{-133}\equiv150\cr
&&&\{\;0,3,4\}\;&2^0+2^3+2^4=25&79*2^{-25}\equiv107\cr
&&&\{\;0,3,7\}\;&2^0+2^3+2^7=137&79*2^{-137}\equiv32\cr
&&&\{\;0,4,7\}\;&2^0+2^4+2^7=145&79*2^{-145}\equiv68\cr
&&&\{\;1,2,3\}\;&2^1+2^2+2^3=14&79*2^{-14}\equiv126\cr
&&&\{\;1,2,4\}\;&2^1+2^2+2^4=22&79*2^{-22}\equiv132\cr
&&&\{\;1,2,7\}\;&2^1+2^2+2^7=134&79*2^{-134}\equiv75\cr
&&&\{\;1,3,4\}\;&2^1+2^3+2^4=26&79*2^{-26}\equiv144\cr
&&&\{\;1,3,7\}\;&2^1+2^3+2^7=138&79*2^{-138}\equiv16\cr
&&&\{\;1,4,7\}\;&2^1+2^4+2^7=146&79*2^{-146}\equiv34\cr
&&&\{\;2,3,4\}\;&2^2+2^3+2^4=28&79*2^{-28}\equiv36\cr
&&&\{\;2,3,7\}\;&2^2+2^3+2^7=140&79*2^{-140}\equiv4\cr
&&&\{\;2,4,7\}\;&2^2+2^4+2^7=148&79*2^{-148}\equiv99\cr
&&&\{\;3,4,7\}\;&2^3+2^4+2^7=152&79*2^{-152}\equiv108}\)
找不到$Y_1,Y_2$使得$\alpha^{val(Y_1)}\equiv \beta \alpha^{-val(Y_2)}\pmod{p}$

$\{\;6,7 \}\;$任取1個的子集合$Y_1$，$\{\;0,1,2,3,4,5 \}\;$任取3個的子集合$Y_2$
\(\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;6\}\;&2^6=64&2^{64}\equiv 44&\{\;0,1,2\}\;&2^0+2^1+2^2=7&79*2^{-7}\equiv19\cr
\{\;7\}\;&2^7=128&2^{128}\equiv 126&\{\;0,1,3\}\;&2^0+2^1+2^3=11&79*2^{-11}\equiv103\cr
&&&\{\;0,1,4\}\;&2^0+2^1+2^4=19&79*2^{-19}\equiv151\cr
&&&\{\;0,1,5\}\;&2^0+2^1+2^5=35&79*2^{-35}\equiv153\cr
&&&\{\;0,2,3\}\;&2^0+2^2+2^3=13&79*2^{-13}\equiv71\cr
&&&\{\;0,2,4\}\;&2^0+2^2+2^4=21&79*2^{-21}\equiv83\cr
&&&\{\;0,2,5\}\;&2^0+2^2+2^5=37&79*2^{-37}\equiv174\cr
&&&\{\;0,3,4\}\;&2^0+2^3+2^4=25&79*2^{-25}\equiv107\cr
&&&\{\;0,3,5\}\;&2^0+2^3+2^5=41&79*2^{-41}\equiv124\cr
&&&\{\;0,4,5\}\;&2^0+2^4+2^5=49&79*2^{-49}\equiv173\cr
&&&\{\;1,2,3\}\;&2^1+2^2+2^3=14&79*2^{-14}\equiv126\cr
&&&\{\;1,2,4\}\;&2^1+2^2+2^4=22&79*2^{-22}\equiv132\cr
&&&\{\;1,2,5\}\;&2^1+2^2+2^5=38&79*2^{-38}\equiv87\cr
&&&\{\;1,3,4\}\;&2^1+2^3+2^4=26&79*2^{-26}\equiv144\cr
&&&\{\;1,3,5\}\;&2^1+2^3+2^5=42&79*2^{-42}\equiv62\cr
&&&\{\;1,4,5\}\;&2^1+2^4+2^5=50&79*2^{-50}\equiv177\cr
&&&\{\;2,3,4\}\;&2^2+2^3+2^4=28&79*2^{-28}\equiv36\cr
&&&\{\;2,3,5\}\;&2^2+2^3+2^5=44&79*2^{-44}\equiv106\cr
&&&\{\;2,4,5\}\;&2^2+2^4+2^5=52&79*2^{-52}\equiv180\cr
&&&\{\;3,4,5\}\;&2^3+2^4+2^5=56&79*2^{-56}\equiv147}\)
可找到
$2^{128}\equiv79*2^{-14}\equiv 126\pmod{181}$，$Y_1=\{\;7\}\;$，$Y_2=\{\;1,2,3\}\;$，$x=128+14=142$

$\{\;7,0 \}\;$任取1個的子集合$Y_1$，$\{\;1,2,3,4,5,6 \}\;$任取3個的子集合$Y_2$
\(\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;7\}\;&2^7=128&2^{128}\equiv 126&\{\;1,2,3\}\;&2^1+2^2+2^3=14&79*2^{-14}\equiv126\cr
\{\;0\}\;&2^0=1&2^1\equiv 2&\{\;1,2,4\}\;&2^1+2^2+2^4=22&79*2^{-22}\equiv132\cr
&&&\{\;1,2,5\}\;&2^1+2^2+2^5=38&79*2^{-38}\equiv87\cr
&&&\{\;1,2,6\}\;&2^1+2^2+2^6=70&79*2^{-70}\equiv42\cr
&&&\{\;1,3,4\}\;&2^1+2^3+2^4=26&79*2^{-26}\equiv144\cr
&&&\{\;1,3,5\}\;&2^1+2^3+2^5=42&79*2^{-42}\equiv62\cr
&&&\{\;1,3,6\}\;&2^1+2^3+2^6=74&79*2^{-74}\equiv161\cr
&&&\{\;1,4,5\}\;&2^1+2^4+2^5=50&79*2^{-50}\equiv177\cr
&&&\{\;1,4,6\}\;&2^1+2^4+2^6=82&79*2^{-82}\equiv48\cr
&&&\{\;1,5,6\}\;&2^1+2^5+2^6=98&79*2^{-98}\equiv81\cr
&&&\{\;2,3,4\}\;&2^2+2^3+2^4=28&79*2^{-28}\equiv36\cr
&&&\{\;2,3,5\}\;&2^2+2^3+2^5=44&79*2^{-44}\equiv106\cr
&&&\{\;2,3,6\}\;&2^2+2^3+2^6=76&79*2^{-76}\equiv176\cr
&&&\{\;2,4,5\}\;&2^2+2^4+2^5=52&79*2^{-52}\equiv180\cr
&&&\{\;2,4,6\}\;&2^2+2^4+2^6=84&79*2^{-84}\equiv12\cr
&&&\{\;2,5,6\}\;&2^2+2^5+2^6=100&79*2^{-100}\equiv156\cr
&&&\{\;3,4,5\}\;&2^3+2^4+2^5=56&79*2^{-56}\equiv147\cr
&&&\{\;3,4,6\}\;&2^3+2^4+2^6=88&79*2^{-88}\equiv46\cr
&&&\{\;3,5,6\}\;&2^3+2^5+2^6=104&79*2^{-104}\equiv55\cr
&&&\{\;4,5,6\}\;&2^4+2^5+2^6=112&79*2^{-112}\equiv49}\)
可找到
$2^{128}\equiv79*2^{-14}\equiv 126\pmod{181}$，$Y_1=\{\;7\}\;$，$Y_2=\{\;1,2,3\}\;$，$x=128+14=142$

參考資料：
Sungwook Kim, Jung Hee Cheon:A Parameterized Splitting System and Its Application to the Discrete Logarithm Problem with Low Hamming Weight Product Exponents. Public Key Cryptography 2008: 328-343
https://www.iacr.org/archive/pkc2008/49390329/49390329.pdf

從L中取n個元素的子集合副程式
(%i1)
Combination(L,n):=block
([c:[],s],
if length(L)>n then
  (for r in L do
   (s:delete(r,L),
   c:unique(append(c,Combination(s,n)))
   )
  )
else
  (c:[L]),
return(c)
)$

解低漢明權重的離散對數問題可變參數Splitting System方法副程式
(%i2)
LowHammingWeightDLP3(alpha,beta,p,t,ts):=block
([m,order,SetBnumber,Beta,inv_alpha,i,Y1,Y2,valY1,valY2,lenY1,lenY2,SetBcomplement,ListY1,ListY2,indexY1:1,indexY2:1,x1:0,x2:0,x:0],
print("ord(",alpha,")=",order:zn_order(alpha,p),"，",alpha^string(order),"≡1(mod",p,")"),
print("m=Ceiling(log2",order,")=",m:ceiling(log(order)/log(2))),
print("Zm=",create_list(i,i,0,m-1)),
print("|Bi|=Floor(ts*m/t)=",SetBnumber:floor(ts*m/t)),
print("Bi={i+j (mod m):0≤j≤Floor(ts*m/t)-1}，β={Bi:0≤i≤m-1}"),
print("β=",Beta:create_list(create_list(mod(i+j,m),j,0,SetBnumber-1),i,0,m-1)),
print("－－－－－－－－"),
inv_alpha:inv_mod(alpha,p),
for i:1 thru m do
  (print("B",i-1,"=",Beta[ i ]),
print("從B",i-1,"取元素個數為ts=",ts,"個的子集合Y1，共C(Floor(ts*m/t),ts)=C(",SetBnumber,",",ts,")=",lenY1: (SetBnumber)!/((ts)!*(SetBnumber-ts)!),"個"),
print("Y1=",Y1:Combination(Beta[ i ],ts)),
print("val(Y1)=Σ2"^"y","=",valY1:create_list(apply("+",y),y,2^Y1)),
print("計算[",alpha^"val(Y1)",",val(Y1)]數對"),
print("ListY1=",ListY1:create_list([power_mod(alpha,valY1[ i ],p),valY1[ i ]],i,1,lenY1)),
print("Zm\\B",i-1,"=",SetBcomplement:sort(create_list(mod(i-1-j,m),j,1,m-SetBnumber))),
print("從Zm\\B",i-1,"取元素個數為t-ts=",t-ts,"個的子集合Y1，共C(m-floor(ts*m/t),t-ts)=C(",m-SetBnumber,",",t-ts,")=",lenY2: (m-SetBnumber)!/((m-SetBnumber-t+ts)!*(t-ts)!),"個"),
print("Y2=",Y2:Combination(SetBcomplement,t-ts)),
print("val(Y2)=Σ2"^"y","=",valY2:create_list(apply("+",y),y,2^Y2)),
print("計算[",beta,"*",alpha^"-val(Y2)",",","val(Y2)]數對"),
print("ListY2=",ListY2:create_list([mod(beta*power_mod(inv_alpha,valY2[ i ],p),p),valY2[ i ]],i,1,lenY2)),
print("由小到大排序"),
print("ListY1=",ListY1:sort(ListY1)),
print("ListY2=",ListY2:sort(ListY2)),
indexY1:1,indexY2:1,x1:0,x2:0,
while indexY1<=lenY1 and indexY2<=lenY2 do
   (if ListY1[indexY1][1]=ListY2[indexY2][1] then
      (print("ListY1和ListY2互相比較找到相同值"),
      x1: ListY1[indexY1][2],x2: ListY2[indexY2][2],
      print(alpha^string(x1),"≡",beta,"*",alpha^concat("-",x2),"≡",ListY1[indexY1][1],"(mod",p,")"),
      print("x=",x1,"+",x2,"=",x:mod(x1+x2,order)),
      indexY1:indexY1+1,
      indexY2:indexY2+1
      )
   else if ListY1[indexY1][1]<ListY2[indexY2][1] then
      (indexY1:indexY1+1)
   else
      (indexY2:indexY2+1)
   ),
if x1=0 and x2=0 then
   (print("ListY1和ListY2互相比較沒找到相同值")),
print("－－－－－－－－")
  ),
if x=0 then
  (print("無解"),
return()
  )
else
  (return(x))
)$

$\alpha^x \equiv \beta \pmod{p}$，已知x的漢明權重$t=4$，參數$t_s=1$
(%i7)
alpha:2;
beta:79;
p:181;
t:4;
ts:1;
(alpha)　2
(beta)　79
(p)　181
(t)　4
(ts)　1

解低漢明權重的離散對數問題-可變參數Splitting System方法
(%i8)　x: LowHammingWeightDLP3(alpha,beta,p,t,ts);
$ord(2)=180$，$2^{180}\equiv 1\pmod{181}$
$m=Ceiling(log_2 180)=8$
$Zm=[0,1,2,3,4,5,6,7]$
$|\;Bi|\;=Floor(ts*m/t)=2$
$Bi=\{\;i+j\pmod{m}:0\le j\le Floor(ts*m/t)-1\}\;$，$\beta=\{\;Bi:0\le i\le m-1\}\;$
$\beta=[[0,1],[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[7,0]]$
－－－－－－－－
$B0=[0,1]$
從B0取元素個數為$ts=1$個的子集合$Y1$，共$C(Floor(ts*m/t),ts)=C(2,1)=2$個
$Y1=[[0],[1]]$
$val(Y1)=Σ2^y=[1,2]$
計算$[2^{val(Y1)},val(Y1)]$數對
$ListY1=[[2,1],[4,2]]$
$Zm\backslash\;B0=[2,3,4,5,6,7]$
從$Zm\backslash\;B0$取元素個數為$t-ts=3$個的子集合$Y1$，共$C(m-floor(ts*m/t),t-ts)=C(6,3)=20$個
$Y2=[[2,3,4],[2,3,5],[2,3,6],[2,3,7],[2,4,5],[2,4,6],[2,4,7],[2,5,6],[2,5,7],[2,6,7],$
$[3,4,5],[3,4,6],[3,4,7],[3,5,6],[3,5,7],[3,6,7],[4,5,6],[4,5,7],[4,6,7],[5,6,7]]$
$val(Y2)=Σ2^y=[28,44,76,140,52,84,148,100,164,196,56,88,152,104,168,200,112,176,208,224]$
計算$[79*2^{-val(Y2)},val(Y2)]$數對
$ListY2=[[36,28],[106,44],[176,76],[4,140],[180,52],[12,84],[99,148],[156,100],[20,164],[122,196],$
$[147,56],[46,88],[108,152],[55,104],[137,168],[166,200],[49,112],[178,176],[36,208],[106,224]]$
由小到大排序
$ListY1=[[2,1],[4,2]]$
$ListY2=[[4,140],[12,84],[20,164],[36,28],[36,208],[46,88],[49,112],[55,104],[99,148],[106,44],$
$[106,224],[108,152],[122,196],[137,168],[147,56],[156,100],[166,200],[176,76],[178,176],[180,52]]$
$ListY1$和$ListY2$互相比較找到相同值
$2^2\equiv 79*2^{-140}\equiv 4\pmod{181}$
$x=2+140=142$
－－－－－－－－
$B1=[1,2]$
從$B1$取元素個數為$ts=1$個的子集合$Y1$，共$C(Floor(ts*m/t),ts)=C(2,1)=2$個
$Y1=[[1],[2]]$
$val(Y1)=Σ2^y=[2,4]$
計算$[2^{val(Y1)},val(Y1)]$數對
$ListY1=[[4,2],[16,4]]$
$Zm\backslash\;B1=[0,3,4,5,6,7]$
從$Zm\backslash\;B1$取元素個數為$t-ts=3$個的子集合$Y1$，共$C(m-floor(ts*m/t),t-ts)=C(6,3)=20$個
$Y2=[[0,3,4],[0,3,5],[0,3,6],[0,3,7],[0,4,5],[0,4,6],[0,4,7],[0,5,6],[0,5,7],[0,6,7],$
$[3,4,5],[3,4,6],[3,4,7],[3,5,6],[3,5,7],[3,6,7],[4,5,6],[4,5,7],[4,6,7],[5,6,7]]$
$val(Y2)=Σ2^y=[25,41,73,137,49,81,145,97,161,193,56,88,152,104,168,200,112,176,208,224]$
計算$[79*2^{-val(Y2)},val(Y2)]$數對
$ListY2=[[107,25],[124,41],[141,73],[32,137],[173,49],[96,81],[68,145],[162,97],[160,161],[71,193],$
$[147,56],[46,88],[108,152],[55,104],[137,168],[166,200],[49,112],[178,176],[36,208],[106,224]]$
由小到大排序
$ListY1=[[4,2],[16,4]]$
$ListY2=[[32,137],[36,208],[46,88],[49,112],[55,104],[68,145],[71,193],[96,81],[106,224],[107,25],$
$[108,152],[124,41],[137,168],[141,73],[147,56],[160,161],[162,97],[166,200],[173,49],[178,176]]$
$ListY1$和$ListY2$互相比較沒找到相同值
－－－－－－－－
$B2=[2,3]$
從$B2$取元素個數為$ts=1$個的子集合$Y1$，共$C(Floor(ts*m/t),ts)=C(2,1)=2$個
$Y1=[[2],[3]]$
$val(Y1)=Σ2^y=[4,8]$
計算$[2^{val(Y1)},val(Y1)]$數對
$ListY1=[[16,4],[75,8]]$
$Zm\backslash\;B2=[0,1,4,5,6,7]$
從$Zm\backslash\;B2$取元素個數為$t-ts=3$個的子集合$Y1$，共$C(m-floor(ts*m/t),t-ts)=C(6,3)=20$個
$Y2=[[0,1,4],[0,1,5],[0,1,6],[0,1,7],[0,4,5],[0,4,6],[0,4,7],[0,5,6],[0,5,7],[0,6,7],$
$[1,4,5],[1,4,6],[1,4,7],[1,5,6],[1,5,7],[1,6,7],[4,5,6],[4,5,7],[4,6,7],[5,6,7]]$
$val(Y2)=Σ2^y=[19,35,67,131,49,81,145,97,161,193,50,82,146,98,162,194,112,176,208,224]$
計算$[79*2^{-val(Y2)},val(Y2)]$數對
$ListY2=[[151,19],[153,35],[155,67],[57,131],[173,49],[96,81],[68,145],[162,97],[160,161],[71,193],$
$[177,50],[48,82],[34,146],[81,98],[80,162],[126,194],[49,112],[178,176],[36,208],[106,224]]$
由小到大排序
$ListY1=[[16,4],[75,8]]$
$ListY2=[[34,146],[36,208],[48,82],[49,112],[57,131],[68,145],[71,193],[80,162],[81,98],[96,81],$
$[106,224],[126,194],[151,19],[153,35],[155,67],[160,161],[162,97],[173,49],[177,50],[178,176]]$
$ListY1$和$ListY2$互相比較沒找到相同值
－－－－－－－－
$B3=[3,4]$
從$B3$取元素個數為$ts=1$個的子集合$Y1$，共$C(Floor(ts*m/t),ts)=C(2,1)=2$個
$Y1=[[3],[4]]$
$val(Y1)=Σ2^y=[8,16]$
計算$[2^{val(Y1)},val(Y1)]$數對
$ListY1=[[75,8],[14,16]]$
$Zm\backslash\;B3=[0,1,2,5,6,7]$
從$Zm\backslash\;B3$取元素個數為$t-ts=3$個的子集合$Y1$，共$C(m-floor(ts*m/t),t-ts)=C(6,3)=20$個
$Y2=[[0,1,2],[0,1,5],[0,1,6],[0,1,7],[0,2,5],[0,2,6],[0,2,7],[0,5,6],[0,5,7],[0,6,7],$
$[1,2,5],[1,2,6],[1,2,7],[1,5,6],[1,5,7],[1,6,7],[2,5,6],[2,5,7],[2,6,7],[5,6,7]]$
$val(Y2)=Σ2^y=[7,35,67,131,37,69,133,97,161,193,38,70,134,98,162,194,100,164,196,224]$
計算$[79*2^{-val(Y2)},val(Y2)]$數對
$ListY2=[[19,7],[153,35],[155,67],[57,131],[174,37],[84,69],[150,133],[162,97],[160,161],[71,193],$
$[87,38],[42,70],[75,134],[81,98],[80,162],[126,194],[156,100],[20,164],[122,196],[106,224]]$
由小到大排序
$ListY1=[[14,16],[75,8]]$
$ListY2=[[19,7],[20,164],[42,70],[57,131],[71,193],[75,134],[80,162],[81,98],[84,69],[87,38],$
$[106,224],[122,196],[126,194],[150,133],[153,35],[155,67],[156,100],[160,161],[162,97],[174,37]]$
$ListY1$和$ListY2$互相比較找到相同值
$2^8\equiv 79*2^{-134}\equiv 75\pmod{181}$
$x=8+134=142$
－－－－－－－－
$B4=[4,5]$
從$B4$取元素個數為$ts=1$個的子集合$Y1$，共$C(Floor(ts*m/t),ts)=C(2,1)=2$個
$Y1=[[4],[5]]$
$val(Y1)=Σ2^y=[16,32]$
計算$[2^{val(Y1)},val(Y1)]$數對
$ListY1=[[14,16],[15,32]]$
$Zm\backslash\;B4=[0,1,2,3,6,7]$
從$Zm\backslash\;B4$取元素個數為$t-ts=3$個的子集合$Y1$，共$C(m-floor(ts*m/t),t-ts)=C(6,3)=20$個
$Y2=[[0,1,2],[0,1,3],[0,1,6],[0,1,7],[0,2,3],[0,2,6],[0,2,7],[0,3,6],[0,3,7],[0,6,7],$
$[1,2,3],[1,2,6],[1,2,7],[1,3,6],[1,3,7],[1,6,7],[2,3,6],[2,3,7],[2,6,7],[3,6,7]]$
$val(Y2)=Σ2^y=[7,11,67,131,13,69,133,73,137,193,14,70,134,74,138,194,76,140,196,200]$
計算$[79*2^{-val(Y2)},val(Y2)]$數對
$ListY2=[[19,7],[103,11],[155,67],[57,131],[71,13],[84,69],[150,133],[141,73],[32,137],[71,193],$
$[126,14],[42,70],[75,134],[161,74],[16,138],[126,194],[176,76],[4,140],[122,196],[166,200]]$
由小到大排序
$ListY1=[[14,16],[15,32]]$
$ListY2=[[4,140],[16,138],[19,7],[32,137],[42,70],[57,131],[71,13],[71,193],[75,134],[84,69],$
$[103,11],[122,196],[126,14],[126,194],[141,73],[150,133],[155,67],[161,74],[166,200],[176,76]]$
$ListY1$和$ListY2$互相比較沒找到相同值
－－－－－－－－
$B5=[5,6]$
從$B5$取元素個數為$ts=1$個的子集合$Y1$，共$C(Floor(ts*m/t),ts)=C(2,1)=2$個
$Y1=[[5],[6]]$
$val(Y1)=Σ2^y=[32,64]$
計算$[2^{val(Y1)},val(Y1)]$數對
$ListY1=[[15,32],[44,64]]$
$Zm\backslash\;B5=[0,1,2,3,4,7]$
從$Zm\backslash\;B5$取元素個數為$t-ts=3$個的子集合$Y1$，共$C(m-floor(ts*m/t),t-ts)=C(6,3)=20$個
$Y2=[[0,1,2],[0,1,3],[0,1,4],[0,1,7],[0,2,3],[0,2,4],[0,2,7],[0,3,4],[0,3,7],[0,4,7],$
$[1,2,3],[1,2,4],[1,2,7],[1,3,4],[1,3,7],[1,4,7],[2,3,4],[2,3,7],[2,4,7],[3,4,7]]$
$val(Y2)=Σ2^y=[7,11,19,131,13,21,133,25,137,145,14,22,134,26,138,146,28,140,148,152]$
計算$[79*2^{-val(Y2)},val(Y2)]$數對
$ListY2=[[19,7],[103,11],[151,19],[57,131],[71,13],[83,21],[150,133],[107,25],[32,137],[68,145],$
$[126,14],[132,22],[75,134],[144,26],[16,138],[34,146],[36,28],[4,140],[99,148],[108,152]]$
由小到大排序
$ListY1=[[15,32],[44,64]]$
$ListY2=[[4,140],[16,138],[19,7],[32,137],[34,146],[36,28],[57,131],[68,145],[71,13],[75,134],$
$[83,21],[99,148],[103,11],[107,25],[108,152],[126,14],[132,22],[144,26],[150,133],[151,19]]$
$ListY1$和$ListY2$互相比較沒找到相同值
－－－－－－－－
$B6=[6,7]$
從$B6$取元素個數為$ts=1$個的子集合$Y1$，共$C(Floor(ts*m/t),ts)=C(2,1)=2$個
$Y1=[[6],[7]]$
$val(Y1)=Σ2^y=[64,128]$
計算$[2^{val(Y1)},val(Y1)]$數對
$ListY1=[[44,64],[126,128]]$
$Zm\backslash\;B6=[0,1,2,3,4,5]$
從$Zm\backslash\;B6$取元素個數為$t-ts=3$個的子集合$Y1$，共$C(m-floor(ts*m/t),t-ts)=C(6,3)=20$個
$Y2=[[0,1,2],[0,1,3],[0,1,4],[0,1,5],[0,2,3],[0,2,4],[0,2,5],[0,3,4],[0,3,5],[0,4,5],$
$[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]$
$val(Y2)=Σ2^y=[7,11,19,35,13,21,37,25,41,49,14,22,38,26,42,50,28,44,52,56]$
計算$[79*2^{-val(Y2)},val(Y2)]$數對
$ListY2=[[19,7],[103,11],[151,19],[153,35],[71,13],[83,21],[174,37],[107,25],[124,41],[173,49],$
$[126,14],[132,22],[87,38],[144,26],[62,42],[177,50],[36,28],[106,44],[180,52],[147,56]]$
由小到大排序
$ListY1=[[44,64],[126,128]]$
$ListY2=[[19,7],[36,28],[62,42],[71,13],[83,21],[87,38],[103,11],[106,44],[107,25],[124,41],$
$[126,14],[132,22],[144,26],[147,56],[151,19],[153,35],[173,49],[174,37],[177,50],[180,52]]$
$ListY1$和$ListY2$互相比較找到相同值
$2^{128}\equiv79*2^{-14}\equiv126\pmod{181}$
$x=128+14=142$
－－－－－－－－
$B7=[7,0]$
從$B7$取元素個數為$ts=1$個的子集合$Y1$，共$C(Floor(ts*m/t),ts)=C(2,1)=2$個
$Y1=[[0],[7]]$
$val(Y1)=Σ2^y=[1,128]$
計算$[2^{val(Y1)},val(Y1)]$數對
$ListY1=[[2,1],[126,128]]$
$Zm\backslash\;B7=[1,2,3,4,5,6]$
從$Zm\backslash\;B7$取元素個數為$t-ts=3$個的子集合$Y1$，共$C(m-floor(ts*m/t),t-ts)=C(6,3)=20$個
$Y2=[[1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,3,4],[1,3,5],[1,3,6],[1,4,5],[1,4,6],[1,5,6],$
$[2,3,4],[2,3,5],[2,3,6],[2,4,5],[2,4,6],[2,5,6],[3,4,5],[3,4,6],[3,5,6],[4,5,6]]$
$val(Y2)=Σ2^y=[14,22,38,70,26,42,74,50,82,98,28,44,76,52,84,100,56,88,104,112]$
計算$[79*2^{-val(Y2)},val(Y2)]$數對
$ListY2=[[126,14],[132,22],[87,38],[42,70],[144,26],[62,42],[161,74],[177,50],[48,82],[81,98],$
$[36,28],[106,44],[176,76],[180,52],[12,84],[156,100],[147,56],[46,88],[55,104],[49,112]]$
由小到大排序
$ListY1=[[2,1],[126,128]]$
$ListY2=[[12,84],[36,28],[42,70],[46,88],[48,82],[49,112],[55,104],[62,42],[81,98],[87,38],$
$[106,44],[126,14],[132,22],[144,26],[147,56],[156,100],[161,74],[176,76],[177,50],[180,52]]$
$ListY1$和$ListY2$互相比較找到相同值
$2^{128}\equiv79*2^{-14}\equiv126\pmod{181}$
$x=128+14=142$
－－－－－－－－
(x)　142

作者: bugmens 時間: 2021-1-24 10:24

5-4.低漢明權重(Low Hamming Weight)的離散對數問題-可變參數的Splitting System(2010版)

Kim和Cheon在2008年發表可變參數的Splitting System之後，又在2010年發表新版論文，新版方法僅小地方更新對解決整個問題改善不多。

可變參數的Splitting System(2008版)	可變參數的Splitting System(2010版)
定義假設$m$、$t$和$t_s$和都是整數且$0<t<m$、$0\le t_s \le t$，定義$(m,t,t_s)$的可變參數splitting system是符合以下2點的數對$(X,\cal{B})$ 1.集合$X$有$m$個元素，集合$\cal{B}$有$\displaystyle \Bigg\lfloor\; \frac{t_s m}{t}\Bigg\rfloor\;$個$X$的子集合，$\cal{B}$稱為區塊(blocks)。 2.對所有$X$的子集合$Y$，$Y$有$t$個元素，存在一個區塊$B$使得$B$和$Y$的交集個數為$\displaystyle t_s$。	定義相同
產生$\displaystyle (m;m,t,t_s)$的可變參數splitting system方法令$X=Z_m$，定義$B_i=\{\;i+j\pmod{m}:0\le j\le \Bigg\lfloor\;\frac{t_sm}{t}\Bigg\rfloor\;-1\}\;$ $\cal B$$=\{\;B_i:0\le i \le m-1\}\;$	產生方法相同
以$m=8,t=4,t_s=3$為例(解$x$有8位元，其中有4個1，分成3個1和1個1分別列舉) $X=Z_m=\{\;0,1,2,3,4,5,6,7\}\;$，$B_0=\{\;0,1,2,3,4,5\}\;$，$B_1=\{\;1,2,3,4,5,6\}\;$，$B_2=\{\;2,3,4,5,6,7\}\;$，$B_3=\{\;3,4,5,6,7,0\}\;$，$B_4=\{\;4,5,6,7,0,1\}\;$，$B_5=\{\;5,6,7,0,1,2\}\;$，$B_6=\{\;6,7,0,1,2,3\}\;$，$B_7=\{\;7,0,1,2,3,4\}\;$，$\cal B$$=\{\;B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\}\;$ 子集合$Y=\{\;0,2,4,6\}\;$有4個元素，存在$B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7$和$Y$交集3個元素。子集合$Y=\{\;1,3,5,7\}\;$有4個元素，存在$B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7$和$Y$交集3個元素。子集合$Y=\{\;0,1,6,7\}\;$有4個元素，存在$B_3,B_7$和$Y$交集3個元素。子集合$Y=\{\;0,2,5,7\}\;$有4個元素，存在$B_0,B_2,B_3,B_4,B_6,B_7$和$Y$交集3個元素。子集合$Y=\{\;4,5,6,7\}\;$有4個元素，存在$B_1,B_5$和$Y$交集3個元素。	集合$X$相同，集合$B_0,B_1,\ldots,B_7$相同，集合$\cal{B}$相同
差異處集合$B_i$有6個元素，列舉3個元素是1的位置，共$C_3^6=20$種	差異處集合$B_i$有6個元素，假設第i個位元是1，再列舉2個元素是1的位置，共$C_2^5=10$種

以$2^{142}\equiv 79\pmod{181}$為例，解$x=(142)_{10}=(10001110)_2$，1的分佈不平均。

$\{\;0,1,2,3,4,5 \}\;$，假設第0個位元是1，再任取2個的子集合$Y_1$，$\{\;6,7 \}\;$任取1個的子集合$Y_2$
$\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;0,1,2\}\;&2^0+2^1+2^2=7&2^{7}\equiv128&\{\;6\}\;&2^6=64&79*2^{-64}\equiv154\cr
\{\;0,1,3\}\;&2^0+2^1+2^3=11&2^{11}\equiv57&\{\;7\}\;&2^7=128&79*2^{-128}\equiv94\cr
\{\;0,1,4\}\;&2^0+2^1+2^4=19&2^{19}\equiv112&&&\cr
\{\;0,1,5\}\;&2^0+2^1+2^5=35&2^{35}\equiv120&&&\cr
\{\;0,2,3\}\;&2^0+2^2+2^3=13&2^{13}\equiv47&&&\cr
\{\;0,2,4\}\;&2^0+2^2+2^4=21&2^{21}\equiv86&&&\cr
\{\;0,2,5\}\;&2^0+2^2+2^5=37&2^{37}\equiv118&&&\cr
\{\;0,3,4\}\;&2^0+2^3+2^4=25&2^{25}\equiv109&&&\cr
\{\;0,3,5\}\;&2^0+2^3+2^5=41&2^{41}\equiv78&&&\cr
\{\;0,4,5\}\;&2^0+2^4+2^5=49&2^{49}\equiv58}$
找不到$Y_1,Y_2$使得$\alpha^{val(Y_1)}\equiv \beta \alpha^{-val(Y_2)}\pmod{p}$

$\{\;1,2,3,4,5,6 \}\;$，假設第1個位元是1，再任取2個的子集合$Y_1$，$\{\;7,0 \}\;$任取1個的子集合$Y_2$
$\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;1,2,3\}\;&2^1+2^2+2^3=14&2^{14}\equiv94&\{\;7\}\;&2^7=128&79*2^{-128}\equiv94\cr
\{\;1,2,4\}\;&2^1+2^2+2^4=22&2^{22}\equiv172&\{\;0\}\;&2^0=1&79*2^{-1}\equiv130\cr
\{\;1,2,5\}\;&2^1+2^2+2^5=38&2^{38}\equiv55&&&\cr
\{\;1,2,6\}\;&2^1+2^2+2^6=70&2^{70}\equiv101&&&\cr
\{\;1,3,4\}\;&2^1+2^3+2^4=26&2^{26}\equiv37&&&\cr
\{\;1,3,5\}\;&2^1+2^3+2^5=42&2^{42}\equiv156&&&\cr
\{\;1,3,6\}\;&2^1+2^3+2^6=74&2^{74}\equiv168&&&\cr
\{\;1,4,5\}\;&2^1+2^4+2^5=50&2^{50}\equiv116&&&\cr
\{\;1,4,6\}\;&2^1+2^4+2^6=82&2^{82}\equiv111&&&\cr
\{\;1,5,6\}\;&2^1+2^5+2^6=98&2^{98}\equiv106}$
可找到
$2^{14}\equiv 79*2^{-128}\equiv 94\pmod{181}$，$Y_1=\{\;1,2,3\}\;$，$Y_2=\{\;7\}\;$，$x=14+128=142$

$\{\;2,3,4,5,6,7 \}\;$，假設第2個位元是1，再任取2個的子集合$Y_1$，$\{\;0,1 \}\;$任取1個的子集合$Y_2$
$\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;2,3,4\}\;&2^2+2^3+2^4=28&2^{28}\equiv148&\{\;0\}\;&2^0=1&79*2^{-1}\equiv130\cr
\{\;2,3,5\}\;&2^2+2^3+2^5=44&2^{44}\equiv81&\{\;1\}\;&2^1=2&79*2^{-2}\equiv65\cr
\{\;2,3,6\}\;&2^2+2^3+2^6=76&2^{76}\equiv129&&&\cr
\{\;2,3,7\}\;&2^2+2^3+2^7=140&2^{140}\equiv65&&&\cr
\{\;2,4,5\}\;&2^2+2^4+2^5=52&2^{52}\equiv102&&&\cr
\{\;2,4,6\}\;&2^2+2^4+2^6=84&2^{84}\equiv82&&&\cr
\{\;2,4,7\}\;&2^2+2^4+2^7=148&2^{148}\equiv169&&&\cr
\{\;2,5,6\}\;&2^2+2^5+2^6=100&2^{100}\equiv62&&&\cr
\{\;2,5,7\}\;&2^2+2^5+2^7=164&2^{164}\equiv13&&&\cr
\{\;2,6,7\}\;&2^2+2^6+2^7=196&2^{196}\equiv14}$
可找到
$2^{140}\equiv 79*2^{-2}\equiv 65\pmod{181}$，$Y_1=\{\;2,3,7\}\;$，$Y_2=\{\;1\}\;$，$x=140+2=142$

$\{\;3,4,5,6,7,0 \}\;$，假設第3個位元是1，再任取2個的子集合$Y_1$，$\{\;1,2 \}\;$任取1個的子集合$Y_2$
$\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;3,4,0\}\;&2^3+2^4+2^0=25&2^{25}\equiv109&\{\;1\}\;&2^1=2&79*2^{-2}\equiv65\cr
\{\;3,4,5\}\;&2^3+2^4+2^5=56&2^{56}\equiv3&\{\;2\}\;&2^2=4&79*2^{-4}\equiv152\cr
\{\;3,4,6\}\;&2^3+2^4+2^6=88&2^{88}\equiv45&&&\cr
\{\;3,4,7\}\;&2^3+2^4+2^7=152&2^{152}\equiv170&&&\cr
\{\;3,5,0\}\;&2^3+2^5+2^0=41&2^{41}\equiv78&&&\cr
\{\;3,5,6\}\;&2^3+2^5+2^6=104&2^{104}\equiv87&&&\cr
\{\;3,5,7\}\;&2^3+2^5+2^7=168&2^{168}\equiv27&&&\cr
\{\;3,6,0\}\;&2^3+2^6+2^0=73&2^{73}\equiv84&&&\cr
\{\;3,6,7\}\;&2^3+2^6+2^7=200&2^{200}\equiv43&&&\cr
\{\;3,7,0\}\;&2^3+2^7+2^0=137&2^{137}\equiv76}$
找不到$Y_1,Y_2$使得$\alpha^{val(Y_1)}\equiv \beta \alpha^{-val(Y_2)}\pmod{p}$

$\{\;4,5,6,7,0,1 \}\;$，假設第4個位元是1，再任取2個的子集合$Y_1$，$\{\;2,3 \}\;$任取1個的子集合$Y_2$
$\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;4,0,1\}\;&2^4+2^0+2^1=19&2^{19}\equiv112&\{\;2\}\;&2^2=4&79*2^{-4}\equiv152\cr
\{\;4,5,0\}\;&2^4+2^5+2^0=49&2^{49}\equiv58&\{\;3\}\;&2^3=8&79*2^{-8}\equiv100\cr
\{\;4,5,1\}\;&2^4+2^5+2^1=50&2^{50}\equiv116&&&\cr
\{\;4,5,6\}\;&2^4+2^5+2^6=112&2^{112}\equiv9&&&\cr
\{\;4,5,7\}\;&2^4+2^5+2^7=176&2^{176}\equiv34&&&\cr
\{\;4,6,0\}\;&2^4+2^6+2^0=81&2^{81}\equiv146&&&\cr
\{\;4,6,1\}\;&2^4+2^6+2^1=82&2^{82}\equiv111&&&\cr
\{\;4,6,7\}\;&2^4+2^6+2^7=208&2^{208}\equiv148&&&\cr
\{\;4,7,0\}\;&2^4+2^7+2^0=145&2^{145}\equiv89&&&\cr
\{\;4,7,1\}\;&2^4+2^7+2^1=146&2^{146}\equiv178}$
找不到$Y_1,Y_2$使得$\alpha^{val(Y_1)}\equiv \beta \alpha^{-val(Y_2)}\pmod{p}$

$\{\;5,6,7,0,1,2 \}\;$，假設第5個位元是1，再任取2個的子集合$Y_1$，$\{\;3,4 \}\;$任取1個的子集合$Y_2$
$\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;5,0,1\}\;&2^5+2^0+2^1=35&2^{35}\equiv120&\{\;3\}\;&2^3=8&79*2^{-8}\equiv100\cr
\{\;5,0,2\}\;&2^5+2^0+2^2=37&2^{37}\equiv118&\{\;4\}\;&2^4=16&79*2^{-16}\equiv122\cr
\{\;5,1,2\}\;&2^5+2^1+2^2=38&2^{38}\equiv55&&&\cr
\{\;5,6,0\}\;&2^5+2^6+2^0=97&2^{97}\equiv53&&&\cr
\{\;5,6,1\}\;&2^5+2^6+2^1=98&2^{98}\equiv106&&&\cr
\{\;5,6,2\}\;&2^5+2^6+2^2=100&2^{100}\equiv62&&&\cr
\{\;5,6,7\}\;&2^5+2^6+2^7=224&2^{224}\equiv81&&&\cr
\{\;5,7,0\}\;&2^5+2^7+2^0=161&2^{161}\equiv160&&&\cr
\{\;5,7,1\}\;&2^5+2^7+2^1=162&2^{162}\equiv139&&&\cr
\{\;5,7,2\}\;&2^5+2^7+2^2=164&2^{164}\equiv13}$
找不到$Y_1,Y_2$使得$\alpha^{val(Y_1)}\equiv \beta \alpha^{-val(Y_2)}\pmod{p}$

$\{\;6,7,0,1,2,3 \}\;$，假設第6個位元是1，再任取2個的子集合$Y_1$，$\{\;4,5 \}\;$任取1個的子集合$Y_2$
$\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;6,0,1\}\;&2^6+2^0+2^1=67&2^{67}\equiv171&\{\;4\}\;&2^4=16&79*2^{-16}\equiv122\cr
\{\;6,0,2\}\;&2^6+2^0+2^2=69&2^{69}\equiv141&\{\;5\}\;&2^5=32&79*2^{-32}\equiv138\cr
\{\;6,0,3\}\;&2^6+2^0+2^3=73&2^{73}\equiv84&&&\cr
\{\;6,1,2\}\;&2^6+2^1+2^2=70&2^{70}\equiv101&&&\cr
\{\;6,1,3\}\;&2^6+2^1+2^3=74&2^{74}\equiv168&&&\cr
\{\;6,2,3\}\;&2^6+2^2+2^3=76&2^{76}\equiv129&&&\cr
\{\;6,7,0\}\;&2^6+2^7+2^0=193&2^{193}\equiv47&&&\cr
\{\;6,7,1\}\;&2^6+2^7+2^1=194&2^{194}\equiv94&&&\cr
\{\;6,7,2\}\;&2^6+2^7+2^2=196&2^{196}\equiv14&&&\cr
\{\;6,7,3\}\;&2^6+2^7+2^3=200&2^{200}\equiv43}$
找不到$Y_1,Y_2$使得$\alpha^{val(Y_1)}\equiv \beta \alpha^{-val(Y_2)}\pmod{p}$

$\{\;7,0,1,2,3,4 \}\;$，假設第7個位元是1，再任取2個的子集合$Y_1$，$\{\;5,6 \}\;$任取1個的子集合$Y_2$
$\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;7,0,1\}\;&2^7+2^0+2^1=131&2^{131}\equiv103&\{\;5\}\;&2^5=32&79*2^{-32}\equiv138\cr
\{\;7,0,2\}\;&2^7+2^0+2^2=133&2^{133}\equiv50&\{\;6\}\;&2^6=64&79*2^{-64}\equiv154\cr
\{\;7,0,3\}\;&2^7+2^0+2^3=137&2^{137}\equiv76&&&\cr
\{\;7,0,4\}\;&2^7+2^0+2^4=145&2^{145}\equiv89&&&\cr
\{\;7,1,2\}\;&2^7+2^1+2^2=134&2^{134}\equiv100&&&\cr
\{\;7,1,3\}\;&2^7+2^1+2^3=138&2^{138}\equiv152&&&\cr
\{\;7,1,4\}\;&2^7+2^1+2^4=146&2^{146}\equiv178&&&\cr
\{\;7,2,3\}\;&2^7+2^2+2^3=140&2^{140}\equiv65&&&\cr
\{\;7,2,4\}\;&2^7+2^2+2^4=148&2^{148}\equiv169&&&\cr
\{\;7,3,4\}\;&2^7+2^3+2^4=152&2^{152}\equiv170}$
找不到$Y_1,Y_2$使得$\alpha^{val(Y_1)}\equiv \beta \alpha^{-val(Y_2)}\pmod{p}$

參考資料：
Sungwook Kim, Jung Hee Cheon:Parameterized splitting systems for the discrete logarithm. IEEE Trans. Inf. Theory 56(5): 2528-2535 (2010)
https://ieeexplore.ieee.org/document/5452195

從L中取n個元素的子集合副程式
(%i1)
Combination(L,n):=block
([c:[],s],
if length(L)>n then
  (for r in L do
   (s:delete(r,L),
   c:unique(append(c,Combination(s,n)))
   )
  )
else
  (c:[L]),
return(c)
)$

解低漢明權重的離散對數問題可變參數Splitting System方法副程式
(%i2)
LowHammingWeightDLP4(alpha,beta,p,t,ts):=block
([m,order,SetBnumber,Beta,inv_alpha,i,Y1,Y2,valY1,valY2,lenY1,lenY2,SetBcomplement,ListY1,ListY2,indexY1:1,indexY2:1,x1:0,x2:0,x:0],
print("ord(",alpha,")=",order:zn_order(alpha,p),"，",alpha^string(order),"≡1(mod",p,")"),
print("m=Ceiling(log2",order,")=",m:ceiling(log(order)/log(2))),
print("Zm=",create_list(i,i,0,m-1)),
print("|Bi|=Floor(ts*m/t)=",SetBnumber:floor(ts*m/t)),
print("Bi={i+j (mod m):0≤j≤Floor(ts*m/t)-1}，β={Bi:0≤i≤m-1}"),
print("β=",Beta:create_list(create_list(mod(i+j,m),j,0,SetBnumber-1),i,0,m-1)),
print("－－－－－－－－"),
inv_alpha:inv_mod(alpha,p),
for i:1 thru m do
  (print("B",i-1,"=",Beta[ i ]),
print("假設第",i-1,"個位元是1，再取元素個數為ts-1=",ts-1,"個的子集合Y1，共C(Floor(ts*m/t)-1,ts-1)=C(",SetBnumber-1,",",ts-1,")=",lenY1: (SetBnumber-1)!/((ts-1)!*(SetBnumber-ts)!),"個"),
print("Y1=",Y1:map(lambda([beta],append([i-1],beta)),Combination(rest(Beta[ i ],1),ts-1))),
print("val(Y1)=Σ2"^"y","=",valY1:create_list(apply("+",y),y,2^Y1)),
print("計算[",alpha^"val(Y1)",",val(Y1)]數對"),
print("ListY1=",ListY1:create_list([power_mod(alpha,valY1[ i ],p),valY1[ i ]],i,1,lenY1)),
print("Zm\\B",i-1,"=",SetBcomplement:sort(create_list(mod(i-1-j,m),j,1,m-SetBnumber))),
print("從Zm\\B",i-1,"取元素個數為t-ts=",t-ts,"個的子集合Y1，共C(m-floor(ts*m/t),t-ts)=C(",m-SetBnumber,",",t-ts,")=",lenY2: (m-SetBnumber)!/((m-SetBnumber-t+ts)!*(t-ts)!),"個"),
print("Y2=",Y2:Combination(SetBcomplement,t-ts)),
print("val(Y2)=Σ2"^"y","=",valY2:create_list(apply("+",y),y,2^Y2)),
print("計算[",beta,"*",alpha^"-val(Y2)",",","val(Y2)]數對"),
print("ListY2=",ListY2:create_list([mod(beta*power_mod(inv_alpha,valY2[ i ],p),p),valY2[ i ]],i,1,lenY2)),
print("由小到大排序"),
print("ListY1=",ListY1:sort(ListY1)),
print("ListY2=",ListY2:sort(ListY2)),
indexY1:1,indexY2:1,x1:0,x2:0,
while indexY1<=lenY1 and indexY2<=lenY2 do
   (if ListY1[indexY1][1]=ListY2[indexY2][1] then
      (print("ListY1和ListY2互相比較找到相同值"),
      x1: ListY1[indexY1][2],x2: ListY2[indexY2][2],
      print(alpha^string(x1),"≡",beta,"*",alpha^concat("-",x2),"≡",ListY1[indexY1][1],"(mod",p,")"),
      print("x=",x1,"+",x2,"=",x:mod(x1+x2,order)),
      indexY1:indexY1+1,
      indexY2:indexY2+1
      )
   else if ListY1[indexY1][1]<ListY2[indexY2][1] then
      (indexY1:indexY1+1)
   else
      (indexY2:indexY2+1)
   ),
if x1=0 and x2=0 then
   (print("ListY1和ListY2互相比較沒找到相同值")),
print("－－－－－－－－")
  ),
if x=0 then
  (print("無解"),
return()
  )
else
  (return(x))
)$

$\alpha^x\equiv \beta \pmod{p}$，已知x的漢明權重t=4，參數ts=3
(%i7)
alpha:2;
beta:79;
p:181;
t:4;
ts:3;
(alpha)　2
(beta)　79
(p)　181
(t)　4
(ts)　3

(%i8)　x: LowHammingWeightDLP4(alpha,beta,p,t,ts);
$ord(2)=180$，$2^{180}\equiv1\pmod{181}$
$m=Ceiling(log_2 180)=8$
$Zm=[0,1,2,3,4,5,6,7]$
$|\;Bi|\;=Floor(ts*m/t)=6$
$Bi=\{\;i+j\pmod{m}:0\le j\le Floor(ts*m/t)-1\}\;$，$\beta=\{\;Bi:0\le i\le m-1\}\;$
$\beta=[[0,1,2,3,4,5],[1,2,3,4,5,6],[2,3,4,5,6,7],[3,4,5,6,7,0],[4,5,6,7,0,1],[5,6,7,0,1,2],[6,7,0,1,2,3],[7,0,1,2,3,4]]$
－－－－－－－－
$B0=[0,1,2,3,4,5]$
假設第0個位元是1，再取元素個數為$ts-1=2$個的子集合$Y1$，共$C(Floor(ts*m/t)-1,ts-1)=C(5,2)=10$個
$Y1=[[0,1,2],[0,1,3],[0,1,4],[0,1,5],[0,2,3],[0,2,4],[0,2,5],[0,3,4],[0,3,5],[0,4,5]]$
$val(Y1)=Σ2^y=[7,11,19,35,13,21,37,25,41,49]$
計算$[2^{val(Y1)},val(Y1)]$數對
$ListY1=[[128,7],[57,11],[112,19],[120,35],[47,13],[86,21],[118,37],[109,25],[78,41],[58,49]]$
$Zm\backslash\;B0=[6,7]$
從$Zm\backslash\;B0$取元素個數為$t-ts=1$個的子集合$Y1$，共$C(m-floor(ts*m/t),t-ts)=C(2,1)=2$個
$Y2=[[6],[7]]$
$val(Y2)=Σ2^y=[64,128]$
計算$[79*2^{-val(Y2)},val(Y2)]$數對
$ListY2=[[154,64],[94,128]]$
由小到大排序
$ListY1=[[47,13],[57,11],[58,49],[78,41],[86,21],[109,25],[112,19],[118,37],[120,35],[128,7]]$
$ListY2=[[94,128],[154,64]]$
$ListY1$和$ListY2$互相比較沒找到相同值
－－－－－－－－
$B1=[1,2,3,4,5,6]$
假設第1個位元是1，再取元素個數為$ts-1=2$個的子集合$Y1$，共$C(Floor(ts*m/t)-1,ts-1)=C(5,2)=10$個
$Y1=[[1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,3,4],[1,3,5],[1,3,6],[1,4,5],[1,4,6],[1,5,6]]$
$val(Y1)=Σ2^y=[14,22,38,70,26,42,74,50,82,98]$
計算$[2^{val(Y1)},val(Y1)]$數對
$ListY1=[[94,14],[172,22],[55,38],[101,70],[37,26],[156,42],[168,74],[116,50],[111,82],[106,98]]$
$Zm\backslash\;B1=[0,7]$
從$Zm\backslash\;B1$取元素個數為$t-ts=1$個的子集合$Y1$，共$C(m-floor(ts*m/t),t-ts)=C(2,1)=2$個
$Y2=[[0],[7]]$
$val(Y2)=Σ2^y=[1,128]$
計算$[79*2^{-val(Y2)},val(Y2)]$數對
$ListY2=[[130,1],[94,128]]$
由小到大排序
$ListY1=[[37,26],[55,38],[94,14],[101,70],[106,98],[111,82],[116,50],[156,42],[168,74],[172,22]]$
$ListY2=[[94,128],[130,1]]$
$ListY1$和$ListY2$互相比較找到相同值
$2^{14}\equiv79*2^{-128}\equiv94\pmod{181}$
$x=14+128=142$
－－－－－－－－
$B2=[2,3,4,5,6,7]$
假設第2個位元是1，再取元素個數為$ts-1=2$個的子集合$Y1$，共$C(Floor(ts*m/t)-1,ts-1)=C(5,2)=10$個
$Y1=[[2,3,4],[2,3,5],[2,3,6],[2,3,7],[2,4,5],[2,4,6],[2,4,7],[2,5,6],[2,5,7],[2,6,7]]$
$val(Y1)=Σ2^y=[28,44,76,140,52,84,148,100,164,196]$
計算$[2^{val(Y1)},val(Y1)]$數對
$ListY1=[[148,28],[81,44],[129,76],[65,140],[102,52],[82,84],[169,148],[62,100],[13,164],[14,196]]$
$Zm\backslash\;B2=[0,1]$
從$Zm\backslash\;B2$取元素個數為$t-ts=1$個的子集合$Y1$，共$C(m-floor(ts*m/t),t-ts)=C(2,1)=2$個
$Y2=[[0],[1]]$
$val(Y2)=Σ2^y=[1,2]$
計算$[79*2^{-val(Y2)},val(Y2)]$數對
$ListY2=[[130,1],[65,2]]$
由小到大排序
$ListY1=[[13,164],[14,196],[62,100],[65,140],[81,44],[82,84],[102,52],[129,76],[148,28],[169,148]]$
$ListY2=[[65,2],[130,1]]$
$ListY1$和$ListY2$互相比較找到相同值
$2^{140}\equiv79*2^{-2}\equiv65\pmod{181}$
$x=140+2=142$
－－－－－－－－
$B3=[3,4,5,6,7,0]$
假設第3個位元是1，再取元素個數為$ts-1=2$個的子集合$Y1$，共$C(Floor(ts*m/t)-1,ts-1)=C(5,2)=10$個
$Y1=[[3,4,0],[3,4,5],[3,4,6],[3,4,7],[3,5,0],[3,5,6],[3,5,7],[3,6,0],[3,6,7],[3,7,0]]$
$val(Y1)=Σ2^y=[25,56,88,152,41,104,168,73,200,137]$
計算$[2^{val(Y1)},val(Y1)]$數對
$ListY1=[[109,25],[3,56],[45,88],[170,152],[78,41],[87,104],[27,168],[84,73],[43,200],[76,137]]$
$Zm\backslash\;B3=[1,2]$
從$Zm\backslash\;B3$取元素個數為$t-ts=1$個的子集合$Y1$，共$C(m-floor(ts*m/t),t-ts)=C(2,1)=2$個
$Y2=[[1],[2]]$
$val(Y2)=Σ2^y=[2,4]$
計算$[79*2^{-val(Y2)},val(Y2)]$數對
$ListY2=[[65,2],[152,4]]$
由小到大排序
$ListY1=[[3,56],[27,168],[43,200],[45,88],[76,137],[78,41],[84,73],[87,104],[109,25],[170,152]]$
$ListY2=[[65,2],[152,4]]$
$ListY1$和$ListY2$互相比較沒找到相同值
－－－－－－－－
$B4=[4,5,6,7,0,1]$
假設第4個位元是1，再取元素個數為$ts-1=2$個的子集合$Y1$，共$C(Floor(ts*m/t)-1,ts-1)=C(5,2)=10$個
$Y1=[[4,0,1],[4,5,0],[4,5,1],[4,5,6],[4,5,7],[4,6,0],[4,6,1],[4,6,7],[4,7,0],[4,7,1]]$
$val(Y1)=Σ2^y=[19,49,50,112,176,81,82,208,145,146]$
計算$[2^{val(Y1)},val(Y1)]$數對
$ListY1=[[112,19],[58,49],[116,50],[9,112],[34,176],[146,81],[111,82],[148,208],[89,145],[178,146]]$
$Zm\backslash\;B4=[2,3]$
從$Zm\backslash\;B4$取元素個數為$t-ts=1$個的子集合$Y1$，共$C(m-floor(ts*m/t),t-ts)=C(2,1)=2$個
$Y2=[[2],[3]]$
$val(Y2)=Σ2^y=[4,8]$
計算$[79*2^{-val(Y2)},val(Y2)]$數對
$ListY2=[[152,4],[100,8]]$
由小到大排序
$ListY1=[[9,112],[34,176],[58,49],[89,145],[111,82],[112,19],[116,50],[146,81],[148,208],[178,146]]$
$ListY2=[[100,8],[152,4]]$
$ListY1$和$ListY2$互相比較沒找到相同值
－－－－－－－－
$B5=[5,6,7,0,1,2]$
假設第5個位元是1，再取元素個數為$ts-1=2$個的子集合$Y1$，共$C(Floor(ts*m/t)-1,ts-1)=C(5,2)=10$個
$Y1=[[5,0,1],[5,0,2],[5,1,2],[5,6,0],[5,6,1],[5,6,2],[5,6,7],[5,7,0],[5,7,1],[5,7,2]]$
$val(Y1)=Σ2^y=[35,37,38,97,98,100,224,161,162,164]$
計算$[2^{val(Y1)},val(Y1)]$數對
$ListY1=[[120,35],[118,37],[55,38],[53,97],[106,98],[62,100],[81,224],[160,161],[139,162],[13,164]]$
$Zm\backslash\;B5=[3,4]$
從$Zm\backslash\;B5$取元素個數為$t-ts=1$個的子集合$Y1$，共$C(m-floor(ts*m/t),t-ts)=C(2,1)=2$個
$Y2=[[3],[4]]$
$val(Y2)=Σ2^y=[8,16]$
計算$[79*2^{-val(Y2)},val(Y2)]$數對
$ListY2=[[100,8],[122,16]]$
由小到大排序
$ListY1=[[13,164],[53,97],[55,38],[62,100],[81,224],[106,98],[118,37],[120,35],[139,162],[160,161]]$
$ListY2=[[100,8],[122,16]]$
$ListY1$和$ListY2$互相比較沒找到相同值
－－－－－－－－
$B6=[6,7,0,1,2,3]$
假設第6個位元是1，再取元素個數為$ts-1=2$個的子集合$Y1$，共$C(Floor(ts*m/t)-1,ts-1)=C(5,2)=10$個
$Y1=[[6,0,1],[6,0,2],[6,0,3],[6,1,2],[6,1,3],[6,2,3],[6,7,0],[6,7,1],[6,7,2],[6,7,3]]$
$val(Y1)=Σ2^y=[67,69,73,70,74,76,193,194,196,200]$
計算$[2^{val(Y1)},val(Y1)]$數對
$ListY1=[[171,67],[141,69],[84,73],[101,70],[168,74],[129,76],[47,193],[94,194],[14,196],[43,200]]$
$Zm\backslash\;B6=[4,5]$
從$Zm\backslash\;B6$取元素個數為$t-ts=1$個的子集合$Y1$，共$C(m-floor(ts*m/t),t-ts)=C(2,1)=2$個
$Y2=[[4],[5]]$
$val(Y2)=Σ2^y=[16,32]$
計算$[79*2^{-val(Y2)},val(Y2)]$數對
$ListY2=[[122,16],[138,32]]$
由小到大排序
$ListY1=[[14,196],[43,200],[47,193],[84,73],[94,194],[101,70],[129,76],[141,69],[168,74],[171,67]]$
$ListY2=[[122,16],[138,32]]$
$ListY1$和$ListY2$互相比較沒找到相同值
－－－－－－－－
$B7=[7,0,1,2,3,4]$
假設第7個位元是1，再取元素個數為$ts-1=2$個的子集合$Y1$，共$C(Floor(ts*m/t)-1,ts-1)=C(5,2)=10$個
$Y1=[[7,0,1],[7,0,2],[7,0,3],[7,0,4],[7,1,2],[7,1,3],[7,1,4],[7,2,3],[7,2,4],[7,3,4]]$
$val(Y1)=Σ2^y=[131,133,137,145,134,138,146,140,148,152]$
計算$[2^{val(Y1)},val(Y1)]$數對
$ListY1=[[103,131],[50,133],[76,137],[89,145],[100,134],[152,138],[178,146],[65,140],[169,148],[170,152]]$
$Zm\backslash\;B7=[5,6]$
從$Zm\backslash\;B7$取元素個數為$t-ts=1$個的子集合$Y1$，共$C(m-floor(ts*m/t),t-ts)=C(2,1)=2$個
$Y2=[[5],[6]]$
$val(Y2)=Σ2^y=[32,64]$
計算$[79*2^{-val(Y2)},val(Y2)]$數對
$ListY2=[[138,32],[154,64]]$
由小到大排序
$ListY1=[[50,133],[65,140],[76,137],[89,145],[100,134],[103,131],[152,138],[169,148],[170,152],[178,146]]$
$ListY2=[[138,32],[154,64]]$
$ListY1$和$ListY2$互相比較沒找到相同值
－－－－－－－－
(x)　142

歡迎光臨 Math Pro 數學補給站 (https://math.pro/db/)

論壇程式使用 Discuz! 6.1.0

Coppersmith Splitting System	可變參數的Splitting System
定義假設\(m\)和\(t\)都是偶數且\(0<t<m\)，定義\((m,t)\)的splitting system是符合以下2點的數對\((X,\cal{B})\) 1.集合\(X\)有\(m\)個元素，集合\(\cal{B}\)有\(\displaystyle \frac{m}{2}\)個\(X\)的子集合，\(\cal{B}\)稱為區塊(blocks)。 2.對所有\(X\)的子集合\(Y\)，\(Y\)有\(t\)個元素，存在一個區塊\(B\)使得\(B\)和\(Y\)的交集個數為\(\displaystyle \frac{t}{2}\)。	定義假設\(m\)、\(t\)和\(t_s\)和都是整數且\(0<t<m\)、\(0\le t_s \le t\)，定義\((m,t,t_s)\)的可變參數splitting system是符合以下2點的數對\((X,\cal{B})\) 1.集合\(X\)有\(m\)個元素，集合\(\cal{B}\)有\(\displaystyle \Bigg\lfloor\; \frac{t_s m}{t}\Bigg\rfloor\;\)個\(X\)的子集合，\(\cal{B}\)稱為區塊(blocks)。 2.對所有\(X\)的子集合\(Y\)，\(Y\)有\(t\)個元素，存在一個區塊\(B\)使得\(B\)和\(Y\)的交集個數為\(\displaystyle t_s\)。
產生\(\displaystyle (\frac{m}{2};m,t)\)的Coppersmith splitting system方法令\(X=Z_m\)，定義\(B_i=\{\;i+j\pmod{m}:0\le j\le m/2-1\}\;\) \(\cal B\)\(=\{\;B_i:0\le i \le m/2-1\}\;\)	產生\(\displaystyle (m;m,t,t_s)\)的可變參數splitting system方法令\(X=Z_m\)，定義\(B_i=\{\;i+j\pmod{m}:0\le j\le \Bigg\lfloor\;\frac{t_sm}{t}\Bigg\rfloor\;-1\}\;\) \(\cal B\)\(=\{\;B_i:0\le i \le m-1\}\;\)
以\(m=8,t=4\)為例(解\(x\)有8位元，其中有4個1，分成2個1和2個1分別列舉) \(X=Z_m=\{\;0,1,2,3,4,5,6,7\}\;\)，\(B_0=\{\;0,1,2,3\}\;\)，\(B_1=\{\;1,2,3,4\}\;\)，\(B_2=\{\;2,3,4,5\}\;\)，\(B_3=\{\;3,4,5,6\}\;\)，\(\cal B\)\(=\{\;B_0,B_1,B_2,B_3\}\;\) 子集合\(Y=\{\;0,2,4,6\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_3\)和\(Y\)交集2個元素。子集合\(Y=\{\;1,3,5,7\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_3\)和\(Y\)交集2個元素。子集合\(Y=\{\;0,1,6,7\}\;\)有4個元素，存在\(B_0\)和\(Y\)交集2個元素。子集合\(Y=\{\;0,2,5,7\}\;\)有4個元素，存在\(B_0\)和\(Y\)交集2個元素。子集合\(Y=\{\;4,5,6,7\}\;\)有4個元素，存在\(B_2,B_3\)和\(Y\)交集2個元素。	以\(m=8,t=4,t_s=1\)為例(解\(x\)有8位元，其中有4個1，分成1個1和3個1分別列舉) \(X=Z_m=\{\;0,1,2,3,4,5,6,7\}\;\)，\(B_0=\{\;0,1\}\;\)，\(B_1=\{\;1,2\}\;\)，\(B_2=\{\;2,3\}\;\)，\(B_3=\{\;3,4\}\;\)，\(B_4=\{\;4,5\}\;\)，\(B_5=\{\;5,6\}\;\)，\(B_6=\{\;6,7\}\;\)，\(B_7=\{\;7,0\}\;\)，\(\cal B\)\(=\{\;B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\}\;\) 子集合\(Y=\{\;0,2,4,6\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\)和\(Y\)交集1個元素。子集合\(Y=\{\;1,3,5,7\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\)和\(Y\)交集1個元素。子集合\(Y=\{\;0,1,6,7\}\;\)有4個元素，存在\(B_0,B_1,B_5,B_6,B_7\)和\(Y\)交集1個元素。子集合\(Y=\{\;0,2,5,7\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_4,B_5,B_6,B_7\)和\(Y\)交集1個元素。子集合\(Y=\{\;4,5,6,7\}\;\)有4個元素，存在\(B_3,B_4,B_5,B_6,B_7\)和\(Y\)交集1個元素。
	以\(m=8,t=4,t_s=2\)為例 \(X=Z_m=\{\;0,1,2,3,4,5,6,7\}\;\)，\(B_0=\{\;0,1,2,3\}\;\)，\(B_1=\{\;1,2,3,4\}\;\)，\(B_2=\{\;2,3,4,5\}\;\)，\(B_3=\{\;3,4,5,6\}\;\)，\(B_4=\{\;4,5,6,7\}\;\)，\(B_5=\{\;5,6,7,0\}\;\)，\(B_6=\{\;6,7,0,1\}\;\)，\(B_7=\{\;7,0,1,2\}\;\)，\(\cal B\)\(=\{\;B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\}\;\) \(B_0,B_1,B_2,B_3\)和Coppersmith splitting system相同 \(B_4,B_5,B_6,B_7\)則是\(B_0,B_1,B_2,B_3\)的補集。

可變參數的Splitting System(2008版)	可變參數的Splitting System(2010版)
定義假設\(m\)、\(t\)和\(t_s\)和都是整數且\(0<t<m\)、\(0\le t_s \le t\)，定義\((m,t,t_s)\)的可變參數splitting system是符合以下2點的數對\((X,\cal{B})\) 1.集合\(X\)有\(m\)個元素，集合\(\cal{B}\)有\(\displaystyle \Bigg\lfloor\; \frac{t_s m}{t}\Bigg\rfloor\;\)個\(X\)的子集合，\(\cal{B}\)稱為區塊(blocks)。 2.對所有\(X\)的子集合\(Y\)，\(Y\)有\(t\)個元素，存在一個區塊\(B\)使得\(B\)和\(Y\)的交集個數為\(\displaystyle t_s\)。	定義相同
產生\(\displaystyle (m;m,t,t_s)\)的可變參數splitting system方法令\(X=Z_m\)，定義\(B_i=\{\;i+j\pmod{m}:0\le j\le \Bigg\lfloor\;\frac{t_sm}{t}\Bigg\rfloor\;-1\}\;\) \(\cal B\)\(=\{\;B_i:0\le i \le m-1\}\;\)	產生方法相同
以\(m=8,t=4,t_s=3\)為例(解\(x\)有8位元，其中有4個1，分成3個1和1個1分別列舉) \(X=Z_m=\{\;0,1,2,3,4,5,6,7\}\;\)，\(B_0=\{\;0,1,2,3,4,5\}\;\)，\(B_1=\{\;1,2,3,4,5,6\}\;\)，\(B_2=\{\;2,3,4,5,6,7\}\;\)，\(B_3=\{\;3,4,5,6,7,0\}\;\)，\(B_4=\{\;4,5,6,7,0,1\}\;\)，\(B_5=\{\;5,6,7,0,1,2\}\;\)，\(B_6=\{\;6,7,0,1,2,3\}\;\)，\(B_7=\{\;7,0,1,2,3,4\}\;\)，\(\cal B\)\(=\{\;B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\}\;\) 子集合\(Y=\{\;0,2,4,6\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\)和\(Y\)交集3個元素。子集合\(Y=\{\;1,3,5,7\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\)和\(Y\)交集3個元素。子集合\(Y=\{\;0,1,6,7\}\;\)有4個元素，存在\(B_3,B_7\)和\(Y\)交集3個元素。子集合\(Y=\{\;0,2,5,7\}\;\)有4個元素，存在\(B_0,B_2,B_3,B_4,B_6,B_7\)和\(Y\)交集3個元素。子集合\(Y=\{\;4,5,6,7\}\;\)有4個元素，存在\(B_1,B_5\)和\(Y\)交集3個元素。	集合\(X\)相同，集合\(B_0,B_1,\ldots,B_7\)相同，集合\(\cal{B}\)相同
差異處集合\(B_i\)有6個元素，列舉3個元素是1的位置，共\(C_3^6=20\)種	差異處集合\(B_i\)有6個元素，假設第i個位元是1，再列舉2個元素是1的位置，共\(C_2^5=10\)種

原本的小步大步	小步和倍增步長的大步	小步和線性增加步長的大步
將答案改寫成\(x=im+j\) 其中\(m=\lceil\;\sqrt{p}\rceil\;\)，\(0\le i<m\)，\(0\le j<m\) \(\alpha^x \equiv \beta \pmod{p}\) \(\alpha^{im+j}\equiv \beta \pmod{p}\) \(\alpha^j \equiv \beta(\alpha^{-m})^i \pmod{p}\) 計算\(\alpha^j\)稱為Baby step 計算\(\beta(\alpha^{-m})^i\)稱為Giant step 每次步長都是\(\alpha^{-m}\)	將答案改寫成\(x=2^kvq+r\)　(\(x\)除以\(2^kv\)，商數\(q\)，餘數\(r\)) 其中\(v\)為偶數，\(k\ge 0\)，\(1\le r \le 2^kv\) \(\alpha^x \equiv \beta \pmod{p}\) \(\displaystyle \alpha^{2^kvq+r}\equiv \beta \pmod{p}\) \(\displaystyle \beta \alpha^{-r}\equiv (\alpha^{2^kv})^q \pmod{p}\) 計算\( \beta\alpha^{-r}\)稱為Baby step 計算\((\alpha^{2^kv})^q\)稱為Giant step 每次步長\(\alpha^{2^kv}\)隨著\(k\)值倍增	將答案改寫成\(x=t_j-i\) 其中\(t_0=2v\)，\(t_{j+1}=t_j+j+v+1\) \(\alpha^x \equiv \beta \pmod{p}\) \(\alpha^{t_j-i}\equiv \beta \pmod{p}\) \(\alpha^{t_j} \equiv \beta \alpha^i \pmod{p}\) 計算\(\beta \alpha^i\)稱為Baby Step 計算\(\alpha^{t_j}\)稱為Giant Step 每次步長\(\alpha^{t_j}\)隨著\(j\)值線性增加(\(t_{j+1}=t_j+j+v+1\))