發新話題
打印

用maxima學密碼學-Lattice Reduction應用1

推到噗浪
推到臉書

用maxima學密碼學-Lattice Reduction應用1

maxima內建LLL指令但執行結果會出現錯誤。

要先載入lll.lisp才能使用latticereduce指令
(%i1) load("lll.lisp");
(%o1) C:\maxima-5.41.0\share\maxima\5.41.0\share\contrib\lll.lisp

https://math.pro/db/viewthread.php?tid=1876&page=1#pid10232的範例
執行結果正確

(%i2) latticereduce([[31,59],[37,70]]);
(%o2) \( [[1,4],[3,-1]] \)

https://math.pro/db/viewthread.php?tid=1876&page=1#pid10232的範例
執行結果正確

(%i3) latticereduce([[47,9],[26,4]]);
(%o3) \( [[5,-1],[-1,-9]] \)

https://math.pro/db/viewthread.php?tid=1876&page=1#pid10892的範例
執行結果錯誤,應該是\([[0,1,0],[1,0,1],[-1,0,2]]\)

(%i4) latticereduce([[1,1,1],[-1,0,2],[3,5,6]]);
(%o4) \( [[0,1,0],[1,0,1],[-2,0,1]] \)

https://math.pro/db/viewthread.php?tid=1876&page=1#pid10831的範例
執行結果正確

(%i5) latticereduce([[1,1,7,2],[9,8,4,6],[1,8,5,7],[2,3,1,1]]);
(%o5) \( [[2,3,1,1],[3,-1,1,3],[-2,2,6,-1],[-4,1,-4,3]] \)

https://math.pro/db/viewthread.php?tid=1876&page=1#pid10831的範例
latticereduce只能處理方陣,行數與列數不同會出現錯誤

(%i6)
latticereduce([[4,9,3,-5,-5,-1,7,-1,-5],
                   [-2,-8,-7,-1,-3,6,-3,9,8],
                   [1,-3,-2,3,9,7,2,7,-2],
                   [-5,6,4,-2,-2,-7,-2,-9,1],
                   [1,-2,-2,7,7,-3,-9,-5,-4],
                   [7,1,-4,3,-2,9,9,7,6]]);

Maxima encountered a Lisp error:
MAKE-ARRAY: (4 9 3 -5 -5 -1 7 -1 -5) is of incorrect length
Automatically continuing.
To enable the Lisp debugger set *debugger-hook* to nil.




放棄使用maxima內建的LLL,改用自己寫的LLL()副程式
請下載LLL.zip,解壓縮後將LLL.mac放到C:\maxima-5.41.0\share\maxima\5.41.0\share目錄下


要先載入LLL.mac才能使用LLL指令
(%i1) load("LLL.mac");
(%o1) C:\maxima-5.41.0\share\maxima\5.41.0\LLL.mac

(%i2)
LLL(matrix([31,59],
                [37,70]));

0 errors, 0 warnings
(%o2) \( \left[ \matrix{3&-1 \cr 1&4}\right] \)

(%i3)
LLL(matrix([47,9],
                [26,4]));

(%o3) \( \left[ \matrix{5&-1 \cr -1&-9}\right] \)

(%i4)
LLL(matrix([1,1,1],
                [-1,0,2],
                [3,5,6]));

(%o4) \( \left[ \matrix{0&1&0 \cr 1&0&1 \cr -1&0&2} \right] \)

(%i5)
LLL(matrix([1,1,7,2],
                [9,8,4,6],
                [1,8,5,7],
                [2,3,1,1]));

(%o5) \( \left[ \matrix{2&3&1&1 \cr 3&-1&1&3 \cr -2&2&6&-1 \cr -4&1&-4&3} \right] \)

(%i6)
LLL(matrix([4,9,3,-5,-5,-1,7,-1,-5],
                [-2,-8,-7,-1,-3,6,-3,9,8],
                [1,-3,-2,3,9,7,2,7,-2],
                [-5,6,4,-2,-2,-7,-2,-9,1],
                [1,-2,-2,7,7,-3,-9,-5,-4],
                [7,1,-4,3,-2,9,9,7,6]));

(%o6) \( \left[ \matrix{-4 & 3 & 2 & 1 & 7 & 0 & 0 & -2 & -1 \cr 3 & -1 & -6 & 1 & -1 & 2 & -5 & 3 & -1 \cr -2 & 4 & -2 & -5 & -1 & 5 & 4 & 6 & 2 \cr 3 & 11 & -1 & -3 & 1 & 1 & 2 & 0 & -7 \cr 2 & -5 & 2 & 1 & 3 & 5 & 7 & 6 & 0 \cr 1 & 9 & -4 & 3 & 2 & 4 & 2 & -1 & 5} \right] \)

TOP

1.破解Merkle–Hellman背包加密

Merkle和Hellman在1978年基於0-1背包問題設計出第一個非對稱的公鑰系統,以下先介紹0-1背包問題。

0-1背包問題:
已知\(n\)個物品重量分別為\(A=\{\; a_1,a_2,\ldots,a_n \}\;\),任選其中若干件物品放入背包內,使其總重量恰好等於預先給定的\(s\)值。
設所選的結果用\(X=\{\; x_1,x_2,\ldots,x_n \}\;\)表示,其中\(x_i=0\) or \(1(i=1,2,\ldots,n)\),分別表示該物品沒有選取或有選取,則\(\displaystyle AX=\sum_{i=1}^n a_ix_i=s\)。

例子:
已知7個物品重量分別為\(A=\{\;1,2,5,8,11,16,21\}\;\),總重量\(s=47\)
所選的結果為\(X=\{\;0,1,1,1,1,0,1 \}\;\),\(2+5+8+11+21=47\)。

當物品非常多時背包問題就很難解決,Merkle和Hellman利用超遞增(superincreasing)數列讓自己能輕易解決的背包問題。
但隨機選擇一個整數乘上超遞增數列後和另一個數字同餘後,讓別人變成困難的背包問題當公鑰。
完整的Merkle和Hellman加解密流程介紹如下:





產生公鑰

範例

選擇一組數列\(w=\{\; w_1,w_2,\ldots,w_n \}\;\)\(w=\{\;2,7,11,21,42,89,180,354 \}\;\)
驗證是否為超遞增數列
\(\displaystyle w_i>\sum_{j=1}^{i-1}w_j \),\(i=2,3,\ldots,n\)
\(7>2\)
\(11>7+2=9\)
\(21>11+7+2=20\)
\(42>21+11+7+2=41\)
\(89>42+21+11+7+2=83\)
\(354>89+42+21+11+7+2=172\)
\(w\)的確是超遞增數列
選一個比全部\(w\)總和還大的數字\(q\)\(q=881\),\(\displaystyle q>\sum_{i=1}^n w_i=706\)
選一個和\(q\)互質的隨機整數\(r\)\(r=588\),\(gcd(588,881)=1\)
計算\(\beta_i=rw_i \pmod{q}\)\((2 * 588)\pmod{881} = 295\)
\((7 * 588)\pmod{881} = 592\)
\((11 * 588)\pmod{881} = 301\)
\((21 * 588)\pmod{881} = 14\)
\((42 * 588)\pmod{881} = 28\)
\((89 * 588)\pmod{881} = 353\)
\((180 * 588)\pmod{881} = 120\)
\((354 * 588)\pmod{881} = 236\)
\(\beta=\{\;\beta_1,\beta_2,\ldots,\beta_n \}\;\)為公鑰
\( (w,q,r) \)為密鑰
\(\beta=\{\;295, 592, 301, 14, 28, 353, 120, 236\}\;\)為公鑰
\((w,881,588)\)為密鑰



加密

範例

加密\(n\)位元長度的訊息
\(\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_n)\),\(\alpha_i \in \{\;0,1 \}\;\)
其中\(\alpha_i\)是訊息的第\(i\)個位元
加密8位元長度的訊息"a"
"a"的ASCII碼為97,轉成二進位01100001
\(\alpha=\{\;0,1,1,0,0,0,0,1 \}\;\)
計算\( \displaystyle c=\sum_{i=1}^{n}\alpha_i \beta_i \)
得到密文\(c\)
計算\(c=\)
\(0 * 295\)
\(+ 1 * 592\)
\(+ 1 * 301\)
\(+ 0 * 14\)
\(+ 0 * 28\)
\(+ 0 * 353\)
\(+ 0 * 120\)
\(+ 1 * 236\)
\(= 1129\)
得到密文\(c=1129\)




解密

範例

計算\(s\equiv r^{-1}\pmod{q}\)
 
因為\(r\)和\(q\)互質,\( sr\equiv 1\pmod{q} \)
存在整數\(k\)使得\( sr=kq+1 \),\(1=-kq+sr\)
利用輾轉相除法求出符合上式的\(s\)和\(k\)
設\(q=881\),\(r=588\)
輾轉相除法
\(881=588\times 1+293\)
\(293=881-588\)
\(293=q-r\)
 
\(588=293\times 2+2\)
\(2=588-293\times 2\)
\(2=r-(q-r)\cdot 2=-2q+3r\)
 
\(293=2 \times 146+1\)
\(1=293-2\times 146=(q-r)-(-2q+3r)\cdot 146=293q-439r\)
\(1=-kq+sr=293q-439r\)
\(s \equiv -439 \equiv 442 \pmod{881}\)
計算\(c' \equiv cs \pmod{q}\)
 
\(\displaystyle c'\equiv cs \equiv \sum_{i=1}^n \alpha_i \beta_i s\pmod{q}\)
因為\(rs\pmod{q}\equiv 1\)和\(\beta_i\equiv rw_i\pmod{q}\)
得到\(\beta_is \equiv w_i rs\equiv w_i \pmod{q}\)
\(\displaystyle c'\equiv \sum_{i=1}^n \alpha_i w_i \pmod{q}\)
\(c'\equiv 1129*442 \equiv 372 \pmod{881}\)
從\(w\)選出最大元素\(w_k\)
若\( w_k>c' \)則\(\alpha_k=0\)
若\( w_k \le c' \)則\( \alpha_k=1 \),將\(c'\)減掉\( w_k \times \alpha_k \)
重複相同步驟直到\(c'=0\)為止(
\(354 \le 372\),\(\alpha_8=1\),\(c'=372-354=18\)
\(180>18\),\(\alpha_7=0\)
\(89>18\),\(\alpha_6=0\)
\(42>18\),\(\alpha_5=0\)
\(21>18\),\(\alpha_4=0\)
\(11\le 18\),\(\alpha_3=1\),\(c'=18-11=7\)
\(7\le 7\),\(\alpha_2=1\),\(c'=7-7=0\)
\(2>0\),\(\alpha_1=0\)
\(\alpha=\{\;0,1,1,0,0,0,0,1 \}\;\),轉成十進位97,ASCII碼為"a"


參考資料
https://en.wikipedia.org/wiki/Me ... apsack_cryptosystem


超遞增數列w
(%i1) w:[2,7,11,21,42,89,180,354];
(%o1) \( \left[ 2,7,11,21,42,89,180,354 \right] \)

可加密n-bit的訊息
(%i2) n:length(w);
(%o2) 8

w總和
(%i3) apply("+",w);
(%o3) 706

選比w總和還大的數字q
(%i4) q:881;
(%o4) \(881\)

選一個隨機整數r
(%i5) r:588;
(%o5) \(588\)

公鑰β
(%i6) beta:mod(w*r,q);
(%o6) \( \left[ 295,592,301,14,28,353,120,236 \right] \)

明文的ASCII值
(%i7) ASCII:cint("a");
(%o7) \(97\)

要先載入bitwise才能使用bit_and
(%i8) load("bitwise");
(%o8) C:\maxima-5.41.0a\share\maxima\5.41.0a_dirty\share\contrib\bitwise\bitwise.lisp

轉成二進位
(%i9) alpha:create_list(bit_and(ASCII,2^(n-k))/2^(n-k),k,1,n);
(%o9) \( \left[ 0,1,1,0,0,0,0,1 \right] \)

和公鑰β相乘得到密文c
(%i10) c:alpha.beta;
(%o10) \(1129\)

計算cr^(-1)mod q得到c'
(%i11)  cprime:mod(c*inv_mod(r,q),q);
(%o11) \(372\)

解密
(%i14)
bits:[]$
for i:n thru 1 step -1 do
  (if cprime>=w[ i ] then
     (cprime:cprime-w[ i ],
      bits:append([1],bits)
     )
   else
     (bits:append([0],bits)
     )
  )$
bits;

(%o14) \( \left[ 0,1,1,0,0,0,0,1 \right] \)

轉換成10進位
(%i15) ASCII:apply("+",create_list(bits[k]*2^(n-k),k,1,n));
(%o15) \(97\)

得到明文
(%i16) ascii(ASCII);
(%o16) a

TOP

2.破解Merkle–Hellman背包加密-Shimar方法

Shimar在1984年提出破解背包加密的方案。
詳細內容之後再補上

TOP

3.解決子集合加總問題-Lagarias和Odlyzko方法

雖然背包加密已經被\(Shamir\)破解了,但後續有更多學者針對子集合加總問題(\(subset\) \(sum\) \(problem\))進行研究。像\(Lagarias\)和\(Odlyzko\)在1985年提出基於\(LLL\)演算法解決子集合加總問題。

子集合加總問題為找出\( x_1,x_2,\ldots,x_n \)的值讓\(x_1a_1+x_2a_2+\ldots+x_na_n=s\),其中\(x_1,x_2,\ldots x_n \in \{\;0,1 \}\;\)。

\(Lagarias\)和\(Odlyzko\)的解決辦法如下,利用\( a_1,a_2,\ldots,a_n \)和\(s\)(註1),建構\( (n+1)\times (n+1) \)的矩陣\(B\)
\( B=\left[ \matrix{1&0&0&\ldots&0&-a_1 \cr
0&1&0&\ldots&0&-a_2 \cr
0&0&1&\ldots&0&-a_3 \cr
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots \cr
0&0&0&\ldots&1&-a_n \cr
0&0&0&\ldots&0&s} \right] \)
其中\(B\)矩陣的每一列向量\(b_1,b_2,\ldots,b_{n+1}\)都是線性獨立,形成\(lattice\)的基底(\(basis\))。
註1:
雖然前面wiki文章採用公鑰\(\beta\)和密文\(c\),但一般介紹子集合加總問題卻採用\(a_i\)和\(s\),這裡也用相同符號。

設\(b_1,b_2,\ldots,b_{n+1}\)的線性組合為
\(x_1 b_1+x_2 b_2+\ldots+x_n b_n+1\cdot b_{n+1}=
\matrix{x_1 \left[1,0,0,\ldots,0,-a_1 \right]+ \cr
x_2 \left[0,1,0,\ldots,0,-a_2 \right]+ \cr
\ldots \cr
x_n \left[0,0,0,\ldots,1,-a_n \right]+ \cr
1 \left[0,0,0,\ldots \ldots,0,s \right]}=
\left[x_1,x_2,\ldots,x_n,-x_1a_1-x_2a_2-\ldots-x_na_n+s  \right] \)
經\(LLL\)演算法化簡後,第一行向量是整個\(lattice\)中長度較短的向量,若最後一元為0,則\(-x_1a_1-x_2a_2-\ldots-x_na_n+s=0\),符合子集合加總問題的\(x_1a_1+x_2a_2+\ldots+x_na_n=s\),而答案就是前面\(x_1,x_2,\ldots,x_n\)。

論文中還定義了\(a=(a_1,a_2,\ldots,a_n)\)的密度\( \displaystyle d(a)=\frac{n}{log_2 max_i(a_i)} \),\(d(a)\)用來測量明文和密文轉換時的資訊比率(information rate)
\( \displaystyle d(a)\approx \frac{明文的bits數}{密文平均的bits數} \)
利用本論文所定義的\(lattice\)和使用\(LLL\)演算法化簡可以破解低密度子集合加總問題,在密度\(d(a)<0.645\)的子集合加總問題幾乎可以(almost all)解出來。以維基百科為範例計算密度\( \displaystyle d(a)=\frac{8}{log_2 592}=0.869 \),雖然沒符合\(d(a)<0.645\),但還是得到解答,代表高密度背包問題不一定解不出來只是成功率會下降。

參考資料
J. C. Lagarias and A. M. Odlyzko. 1985. Solving low-density subset sum problems. J. ACM 32, 1 (January 1985), 229-246.
https://web.stevens.edu/algebrai ... m/p229-lagarias.pdf



請下載LLL.zip,解壓縮後將LLL.mac放到C:\maxima-5.42.2\share\maxima\5.42.2\share目錄下
要先載入LLL.mac才能使用LLL指令

(%i1) load("LLL.mac");
(%o1) C:\maxima-5.42.2\share\maxima\5.42.2\share\LLL.mac

物品重量
(%i2) a:[295,592,301,14,28,353,120,236];
(%o2) \( \left[295,592,301,14,28,353,120,236 \right] \)

總和
(%i3) s:1129;
(%o4) \(1129\)

形成lattice
(%i4)
B:matrix([1,0,0,0,0,0,0,0,-295],
             [0,1,0,0,0,0,0,0,-592],
             [0,0,1,0,0,0,0,0,-301],
             [0,0,0,1,0,0,0,0,-14],
             [0,0,0,0,1,0,0,0,-28],
             [0,0,0,0,0,1,0,0,-353],
             [0,0,0,0,0,0,1,0,-120],
             [0,0,0,0,0,0,0,1,-236],
             [0,0,0,0,0,0,0,0,1129]);

(%o4) \( \left[ \matrix{1&0&0&0&0&0&0&0&-295\cr
0&1&0&0&0&0&0&0&-592\cr
0&0&1&0&0&0&0&0&-301\cr
0&0&0&1&0&0&0&0&-14\cr
0&0&0&0&1&0&0&0&-28\cr
0&0&0&0&0&1&0&0&-353\cr
0&0&0&0&0&0&1&0&-120\cr
0&0&0&0&0&0&0&1&-236\cr
0&0&0&0&0&0&0&0&1129} \right] \)

經LLL化簡
(%i5) B: LLL(B);
0 errors, 0 warnings
(%o5) \( \left[ \matrix{0&1&1&0&0&0&0&1&0\cr
0&0&0&-2&1&0&0&0&0\cr
1&-1&0&0&-2&1&0&0&0\cr
-2&1&0&0&0&0&0&0&-2\cr
0&-1&1&0&2&0&0&1&-1\cr
0&-1&0&0&0&0&1&2&0\cr
0&1&0&0&0&-1&-2&0&1\cr
1&1&-1&0&0&-2&1&0&0\cr
0&2&-1&1&0&1&-1&0&-1}\right] \)

第1列向量最後一元為0,且\(x_i\)數字為0或1
(%i6) B[1];
(%o6) \( \left[0,1,1,0,0,0,0,1,0 \right] \)

去掉最後一元,得到解答
(%i7) x:rest(B[1],-1);
(%o7) \( \left[0,1,1,0,0,0,0,1 \right] \)

驗證a乘上x是否等於s
(%i8) is(a.x=s);
(%o8) \(true\)

-----------
另一個範例取自Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications的第7章範例7.6
https://books.google.com.tw/book ... e&q&f=false
物品重量\(a=\left[a_1,a_2,\ldots,a_{15} \right]\)
\(a_1 = 929737936, a_2 = 970987227, a_3 = 787514290,\)
\(a_4 = 322163533, a_5 = 926801380, a_6 = 662236970,\)
\(a_7 = 572718201, a_8 = 499197496, a_9 = 270712809,\)
\(a_{10} = 142942483, a_{11} = 994479591, a_{12} = 143064843,\)
\(a_{13} = 724883274, a_{14} = 285884973, a_{15} = 71532418.\)
總和\(s=4740166124\)
試找出\(x_1,x_2,\ldots,x_n\),\(x_i \in \{\;0,1 \}\;\)使得\(\displaystyle \sum_{i=1}^n x_i\cdot a_i=s\)



要先載入LLL.mac才能使用LLL指令
(%i1) load(LLL);
(%o1) C:\maxima-5.42.2\share\maxima\5.42.2\share\LLL.mac

物品重量
(%i2)
a:[929737936,970987227,787514290,322163533,926801380,662236970,572718201,499197496,270712809,142942483,
994479591,143064843,724883274,285884973,71532418];

(%o2) \([929737936,970987227,787514290,322163533,926801380,662236970,572718201,499197496,270712809,142942483,\)
\(994479591,143064843,724883274,285884973,71532418 ]\)

a個數n
(%i3) n:length(a);
(%o3) \(15\)

總和s
(%i4) s:4740166124;
(%o4) \(4740166124\)

將a和s放在一起
(%i5) column:transpose(matrix(append(-a,[s])));
(%o5) \( \left[ \matrix{-929737936\cr -970987227\cr -787514290\cr -322163533\cr -926801380\cr -662236970\cr -572718201\cr -499197496\cr -270712809\cr -142942483\cr -994479591\cr -143064843\cr -724883274\cr -285884973\cr -71532418\cr 4740166124}\right] \)

產生左半邊矩陣
(%i6) B:genmatrix(lambda([i,j],if i=j then 1 else 0),n+1,n);
(%o6) \(\left[ \matrix{1&0&0&0&0&0&0&0&0&0&0&0&0&0&0\cr
0&1&0&0&0&0&0&0&0&0&0&0&0&0&0\cr
0&0&1&0&0&0&0&0&0&0&0&0&0&0&0\cr
0&0&0&1&0&0&0&0&0&0&0&0&0&0&0\cr
0&0&0&0&1&0&0&0&0&0&0&0&0&0&0\cr
0&0&0&0&0&1&0&0&0&0&0&0&0&0&0\cr
0&0&0&0&0&0&1&0&0&0&0&0&0&0&0\cr
0&0&0&0&0&0&0&1&0&0&0&0&0&0&0\cr
0&0&0&0&0&0&0&0&1&0&0&0&0&0&0\cr
0&0&0&0&0&0&0&0&0&1&0&0&0&0&0\cr
0&0&0&0&0&0&0&0&0&0&1&0&0&0&0\cr
0&0&0&0&0&0&0&0&0&0&0&1&0&0&0\cr
0&0&0&0&0&0&0&0&0&0&0&0&1&0&0\cr
0&0&0&0&0&0&0&0&0&0&0&0&0&1&0\cr
0&0&0&0&0&0&0&0&0&0&0&0&0&0&1\cr
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0}\right] \)

將兩個矩陣合併
(%i7) B:addcol(B,column);
(%o7) \( \left[ \matrix{1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&-929737936\cr
0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&-970987227\cr
0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&-787514290\cr
0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&-322163533\cr
0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&-926801380\cr
0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&-662236970\cr
0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&-572718201\cr
0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&-499197496\cr
0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&-270712809\cr
0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&-142942483\cr
0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&-994479591\cr
0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&-143064843\cr
0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&-724883274\cr
0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&-285884973\cr
0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&-71532418\cr
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&4740166124}\right] \)

經LLL化簡
(%i8) B: LLL(B);
0 errors, 0 warnings
(%o8) \( \left[ \matrix{2&-1&-2&0&-1&0&1&1&2&0&0&0&0&0&0&0\cr
1&0&0&-1&0&-2&1&0&1&0&-1&1&1&0&0&1\cr
-1&0&-1&0&1&-1&0&2&-1&-1&0&1&1&0&0&-1\cr
0&1&2&1&-2&-1&0&1&0&1&-1&0&0&0&0&2\cr
-2&0&3&-1&-1&-1&0&0&1&1&1&0&0&0&0&2\cr
0&1&1&-1&-1&-2&0&2&2&0&0&0&-1&0&0&0\cr
0&0&1&-1&1&-1&0&-2&-1&0&2&0&-2&0&0&0\cr
1&0&-2&0&0&0&1&-1&0&2&0&0&0&1&0&0\cr
1&0&1&0&0&0&1&-1&0&-1&-1&0&-1&0&1&-1\cr
0&0&1&0&1&1&1&0&0&0&1&0&1&0&1&0\cr
1&0&0&-1&1&-1&1&2&1&1&-2&-1&-1&0&0&1\cr
0&-2&1&0&1&0&-1&1&-1&1&0&1&0&1&0&-1\cr
1&0&1&0&0&1&-2&0&1&0&-1&1&-1&0&1&1\cr
1&0&1&0&0&0&1&-1&0&1&-1&1&-1&-1&-1&-1\cr
-1&1&1&0&-1&0&0&-1&-1&2&0&0&1&-1&2&1\cr
-133&-99&-15&528&272&-278&-63&-129&302&78&0&-78&-17&-122&102&-40} \right] \)

第10列向量各個數字為0或1且最後一元為0
(%i9) B[10];
(%o9) \( \left[ 0,0,1,0,1,1,1,0,0,0,1,0,1,0,1,0 \right] \)

去掉最後一元得到解答
(%i10) x:rest(B[10],-1);
(%o10) \( \left[ 0,0,1,0,1,1,1,0,0,0,1,0,1,0,1 \right] \)

驗證a乘上x是否等於s
(%i11) is(a.x=s);
(%o11) \(true\)

TOP

4.Lagarias和Odlyzko無法解決的子集合加總問題

上一篇文章提到"在密度\(d(a)<0.645\)的子集合加總問題幾乎可以(almost all)解出來",這裡舉一個無法解決的例子。



請下載LLL.zip,解壓縮後將LLL.mac放到C:\maxima-5.42.2\share\maxima\5.42.2\share目錄下
要先載入LLL.mac才能使用LLL指令

(%i1) load("LLL.mac");
(%o1) C:\maxima-5.42.2\share\maxima\5.42.2\share\LLL.mac

物品重量
(%i2) a:[20,44,68,87];
(%o2) \(\left[20,44,68,87 \right]\)

物品個數
(%i3) n:length(a);
(%o3) \(4\)

總和
(%i4) s:132;
(%o4) \(132\)

解答20+44+68=132
(%i5) x:[1,1,1,0];
(%o5) \( \left[1,1,1,0 \right] \)

利用a和s構造出矩陣B
(%i6)
B:matrix([1,0,0,0,-20],
               [0,1,0,0,-44],
               [0,0,1,0,-68],
               [0,0,0,1,-87],
               [0,0,0,0,132]);

(%o6) \( \left[ \matrix{1&0&0&0&-20\cr
0&1&0&0&-44\cr
0&0&1&0&-68\cr
0&0&0&1&-87\cr
0&0&0&0&132}\right] \)

經LLL化簡後的矩陣B找不到[1,1,1,0,0]向量
(%i7) B: LLL(B);
(%o7) \( \left[ \matrix{-1&0&-1&1&1\cr
0&1&0&1&1\cr
1&-2&1&0&0\cr
-1&1&1&2&-2\cr
5&0&-4&2&-2} \right] \)

a的最大值
(%i8) MAX:apply('max,a);
(%o8) \(87\)

此時密度小於0.645
(%i9) float(n/(log(MAX)/log(2)));
(%o9) \(0.6208342510806205\)

當向量維度小的時候,\(LLL\)可以找到最短向量,但化簡後的\(lattice\)已有向量\(\left[0,1,0,1,1 \right]\),最短向量長度是\(\sqrt{3}\),但卻不是我們要找的正確答案\( \left[1,1,1,0,0 \right] \)。

TOP

發新話題