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

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

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

(%o1)　C:\maxima-5.41.0\share\maxima\5.41.0\share\contrib\lll.lisp

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

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

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

(%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]]$$

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.

(%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背包問題：

 產生公鑰 範例 選擇一組數列$$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

(%i1)　w:[2,7,11,21,42,89,180,354];
(%o1)　$$\left[ 2,7,11,21,42,89,180,354 \right]$$

(%i2)　n:length(w);
(%o2)　8

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

(%i4)　q:881;
(%o4)　$$881$$

(%i5)　r:588;
(%o5)　$$588$$

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

(%i7)　ASCII:cint("a");
(%o7)　$$97$$

(%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]$$

(%i10)　c:alpha.beta;
(%o10)　$$1129$$

(%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]$$

(%i15)　ASCII:apply("+",create_list(bits[k]*2^(n-k),k,1,n));
(%o15)　$$97$$

(%i16)　ascii(ASCII);
(%o16)　a

TOP

 bugmens 發短消息 加為好友 當前離線 3# 大 中 小 發表於 2019-2-10 21:54  只看該作者 2.破解Merkle–Hellman背包加密-Shimar方法 Shimar在1984年提出破解背包加密的方案。 詳細內容之後再補上 UID210 帖子883 閱讀權限200 在線時間4786 小時 註冊時間2008-12-16 最後登錄2019-9-16  查看詳細資料 TOP
 bugmens 發短消息 加為好友 當前離線 4# 大 中 小 發表於 2019-2-10 21:55  只看該作者 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$$ UID210 帖子883 閱讀權限200 在線時間4786 小時 註冊時間2008-12-16 最後登錄2019-9-16  查看詳細資料 TOP
 bugmens 發短消息 加為好友 當前離線 5# 大 中 小 發表於 2019-2-17 12:51  只看該作者 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:[48,181,278,361,506,639]; (%o2)　$$\left[48,181,278,361,506,639 \right]$$ 物品個數 (%i3)　n:length(a); (%o3)　$$6$$ 總和 (%i4)　s:1146; (%o4)　$$1146$$ 解答48+181+278+639=1146 (%i5)　x:[1,1,1,0,0,1]; (%o5)　$$\left[1,1,1,0,0,1 \right]$$ 將-a和s放在一起 (%i6)　column:transpose(matrix(append(-a,[s]))); (%o6)　$$\left[ \matrix{-48\cr -181\cr -278\cr -361\cr -506\cr -639\cr 1146} \right]$$ 產生左半邊矩陣 (%i7)　B:genmatrix(lambda([i,j],if i=j then 1 else 0),n+1,n); (%o7)　$$\left[\matrix{1&0&0&0&0&0\cr 0&1&0&0&0&0\cr 0&0&1&0&0&0\cr 0&0&0&1&0&0\cr 0&0&0&0&1&0\cr 0&0&0&0&0&1\cr 0&0&0&0&0&0} \right]$$ 將兩個矩陣合併 (%i8)　B:addcol(B,column); (%o8)　$$\left[\matrix{1&0&0&0&0&0&-48\cr 0&1&0&0&0&0&-181\cr 0&0&1&0&0&0&-278\cr 0&0&0&1&0&0&-361\cr 0&0&0&0&1&0&-506\cr 0&0&0&0&0&1&-639\cr 0&0&0&0&0&0&1146} \right]$$ 經LLL化簡後的矩陣B找不到向量[1,1,1,0,0,1,0] (%i9)　B: LLL(B); (%o9)　$$\left[ \matrix{-2&-1&1&0&0&0&-1\cr 0&-2&0&1&0&0&1\cr -1&-1&-1&0&1&0&1\cr 0&0&-1&-1&0&1&0\cr 0&0&0&0&1&1&1\cr -3&2&-1&4&-3&2&2\cr 0&1&-3&5&2&2&-4} \right]$$ a的最大值 (%i10)　MAX:apply('max,a); (%o10)　$$639$$ 此時密度小於0.645 (%i11)　float(n/(log(MAX)/log(2))); (%o11)　$$0.6437994730001645$$ 若正面找不到答案，改從反面找答案 (%i12)　sprime:apply("+",a)-s; (%o12)　$$867$$ 反面解答361+506=867 (%i13)　xprime:[0,0,0,1,1,0]; (%o13)　$$\left[0,0,0,1,1,0\right]$$ 再還原成正確解答 (%i14)　x:1-xprime; (%o14)　$$\left[1,1,1,0,0,1 \right]$$ 利用a和s'構造出矩陣B' (%i17) Bprime:B$Bprime[n+1,n+1]:sprime$ Bprime; (%o17)　$$\left[ \matrix{1&0&0&0&0&0&-48\cr 0&1&0&0&0&0&-181\cr 0&0&1&0&0&0&-278\cr 0&0&0&1&0&0&-361\cr 0&0&0&0&1&0&-506\cr 0&0&0&0&0&1&-639\cr 0&0&0&0&0&0&867} \right]$$ 經LLL化簡後的矩陣B'找不到[0,0,0,1,1,0,0]向量 (%i18)　LLL(Bprime); (%o18)　$$\left[ \matrix{-2&-1&1&0&0&0&-1\cr 0&-2&0&1&0&0&1\cr -1&-1&-1&0&1&0&1\cr 0&0&-1&-1&0&1&0\cr 1&1&0&0&0&1&-1\cr -3&2&-1&4&-4&1&1\cr 0&0&-5&2&-3&-2&-4}\right]$$ UID210 帖子883 閱讀權限200 在線時間4786 小時 註冊時間2008-12-16 最後登錄2019-9-16  查看詳細資料 TOP
5.解決子集合加總問題－Coster等人方法

$$B=\left[ \matrix{\displaystyle 1&0&0&\ldots&0&-Na_1 \cr 0&1&0&\ldots&0&-Na_2 \cr 0&0&1&\ldots&0&-Na_3 \cr \vdots&\vdots&\vdots&\vdots&\vdots&\vdots \cr 0&0&0&\ldots&1&-Na_n \cr \frac{1}{2}&\frac{1}{2}&\frac{1}{2}&\ldots&\frac{1}{2}&Ns} \right]$$(註1)

$$\displaystyle 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,-Na_1 \right]+ \cr x_2 \left[0,1,0,\ldots,0,-Na_2 \right]+ \cr \ldots \cr x_n \left[0,0,0,\ldots,1,-Na_n \right]+ \cr 1 \left[\frac{1}{2},\frac{1}{2},\frac{1}{2},\ldots \ldots,\frac{1}{2},Ns \right]}= \left[x_1+\frac{1}{2},x_2+\frac{1}{2},\ldots,x_n+\frac{1}{2},N(-x_1a_1-x_2a_2-\ldots-x_na_n+s) \right]$$

Matthijs J. Coster, Antoine Joux, Brian A. LaMacchia, Andrew M. Odlyzko, Claus-Peter Schnorr, and Jacques Stern. 1992. Improved low-density subset sum algorithms. Comput. Complex. 2, 2 (December 1992), 111-128.
https://d-nb.info/1156214629/34

 B: LLL(matrix([1,0,0,0,0,0,480],                     [0,1,0,0,0,0,1810],                     [0,0,1,0,0,0,2780],                     [0,0,0,1,0,0,3610],                     [0,0,0,0,1,0,5060],                     [0,0,0,0,0,1,6390],                     [0,0,0,0,0,0,11460])); $$\left[ \matrix{0&0&-1&-1&0&1&0 \cr -1&1&0&0&1&-1&0 \cr \color{red}{-1}& \color{red}{-1}& \color{red}{-1}& \color{red}{0}& \color{red}{0}& \color{red}{-1}& \color{red}{0} \cr -2&-1&1&0&1&1&0 \cr -3&4&-1&3&-4&1&0 \cr 0&0&0&0&-1&-1&10 \cr -2&0&3&-7&-4&-3&0}\right]$$ B[3]; $$\left[\matrix{-1&-1&-1&0&0&-1&0} \right]$$ B: LLL(matrix([1,0,0,0,0,0,-480],                     [0,1,0,0,0,0,-1810],                     [0,0,1,0,0,0,-2780],                     [0,0,0,1,0,0,-3610],                     [0,0,0,0,1,0,-5060],                     [0,0,0,0,0,1,-6390],                     [0,0,0,0,0,0,-11460])); $$\left[ \matrix{0&0&-1&-1&0&1&0 \cr -1&1&0&0&1&-1&0 \cr \color{red}{1}&\color{red}{1}&\color{red}{1}&\color{red}{0}&\color{red}{0}&\color{red}{1}&\color{red}{0} \cr -2&-1&1&0&1&1&0 \cr -3&4&-1&3&-4&1&0 \cr 0&0&0&0&-1&-1&10 \cr -2&0&3&-7&-4&-3&0}\right]$$ B[3]; $$\left[\matrix{1&1&1&0&0&1&0} \right]$$

(%o1)　C:\maxima-5.42.2\share\maxima\5.42.2\share\LLL.mac

(%i2)　a:[48,181,278,361,506,639];
(%o2)　$$\left[48,181,278,361,506,639\right]$$

(%i3)　n:length(a);
(%o3)　$$6$$

(%i4)　s:1146;
(%o4)　$$1146$$

(%i5)　N:ceiling(sqrt(n)/2);
(%o5)　$$2$$

(%i6)　column:transpose(matrix(append(-N*a,[N*s])));
(%o6)　$$\left[\matrix{-96\cr -362\cr -556\cr -722\cr -1012\cr -1278\cr 2292} \right]$$

(%i7)　B:genmatrix(lambda([i,j],if i=n+1 then 1/2 else if i=j then 1 else 0),n+1,n);
(%o7)　$$\left[ \matrix{\displaystyle 1&0&0&0&0&0\cr 0&1&0&0&0&0\cr 0&0&1&0&0&0\cr 0&0&0&1&0&0\cr 0&0&0&0&1&0\cr 0&0&0&0&0&1\cr \frac{1}{2}&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}} \right]$$

(%o8)　$$\left[\matrix{\displaystyle 1&0&0&0&0&0&-96\cr 0&1&0&0&0&0&-362\cr 0&0&1&0&0&0&-556\cr 0&0&0&1&0&0&-722\cr 0&0&0&0&1&0&-1012\cr 0&0&0&0&0&1&-1278\cr \frac{1}{2}&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&2292} \right]$$

(%i9)　B: LLL(B);
(%o9)　$$\left[ \matrix{\displaystyle 0&0&-1&-1&0&1&0\cr -1&1&0&0&1&-1&0\cr -1&-1&-1&0&1&0&2\cr -2&-1&1&0&0&0&-2\cr \frac{3}{2}&\frac{3}{2}&\frac{3}{2}&\frac{1}{2}&\frac{1}{2}&\frac{3}{2}&0\cr -3&2&-2&3&-4&2&2\cr -\frac{1}{2}&\frac{3}{2}&\frac{11}{2}&-\frac{13}{2}&-\frac{5}{2}&-\frac{1}{2}&4} \right]$$

(%i10)　B[5];
(%o10)　$$\displaystyle \left[ \displaystyle \frac{3}{2},\frac{3}{2},\frac{3}{2},\frac{1}{2},\frac{1}{2},\frac{3}{2},0 \right]$$

(%i11)　x:rest(B[5]-1/2,-1);
(%o11)　$$\left[1,1,1,0,0,1 \right]$$

(%i12)　is(a.x=s);
(%o12)　$$true$$

TOP

 bugmens 發短消息 加為好友 當前離線 7# 大 中 小 發表於 2019-3-3 00:09  只看該作者 6.解決子集合加總問題－Coster等人方法 B: LLL(matrix([1,0,0,0,0,0,-480],                     [0,1,0,0,0,0,-1810],                     [0,0,1,0,0,0,-2780],                     [0,0,0,1,0,0,-3610],                     [0,0,0,0,1,0,-5060],                     [0,0,0,0,0,1,-6390],                     [0,0,0,0,0,0,-11460])); $$\left[ \matrix{0&0&-1&-1&0&1&0 \cr -1&1&0&0&1&-1&0 \cr \color{red}{1}&\color{red}{1}&\color{red}{1}&\color{red}{0}&\color{red}{0}&\color{red}{1}&\color{red}{0} \cr -2&-1&1&0&1&1&0 \cr -3&4&-1&3&-4&1&0 \cr 0&0&0&0&-1&-1&10 \cr -2&0&3&-7&-4&-3&0}\right]$$ 從之前的例子可以發現$$-a$$和$$s$$乘上大數字$$N$$經$$LLL$$化簡後，除了倒數第2個列向量，其餘列向量最後一元數字皆為0，有效解決$$506+639=1145$$和$$1146$$只相差1但不是正確答案的問題。 正確答案$$x_i$$只能是$$0$$或$$1$$，但從第4個列向量開始出現比$$2$$大或比$$-2$$小的數字，$$x_i$$可以乘上稍大的數字($$n+1$$)變成長向量，讓$$LLL$$再化簡成短向量，但也不能乘太大的數字($$N$$)，因為符合的$$x_i$$只能是0。 第$$1,2$$個列向量$$x_i$$還有$$-1$$，也不是我們想要找的正確答案，可以乘上$$-1$$倍讓向量數字增加，變成長向量，若$$x_i$$為$$0$$或$$1$$則向量數字維持不變或甚至減少。 $$B=\left[ \matrix{n+1&-1&-1&\ldots&-1&Na_1 \cr -1&n+1&-1&\ldots&-1&Na_2 \cr \vdots&\vdots&\vdots&\vdots&\vdots&\vdots \cr -1&\ldots&-1&n+1&-1&Na_n \cr -1&\ldots&-1&-1&n+1&-Ns } \right]$$，$$N\ge n^2$$ 設$$b_1,b_2,\ldots,b_{n+1}$$的線性組合為 $$\displaystyle x_1 b_1+x_2 b_2+\ldots+x_n b_n+1\cdot b_{n+1}= \matrix{ x_1 \left[n+1,-1,-1,\ldots,-1,Na_1 \right]+ \cr x_2 \left[-1,n+1,-1,\ldots,-1,Na_2 \right]+ \cr \ldots \cr x_n \left[-1,\ldots,-1,n+1,-1,Na_n \right]+ \cr 1 \left[-1,\ldots,-1,-1,n+1,-Ns \right] }=$$ $$\left[ ((n+1)x_1-x_2-\ldots -x_n-1),(-x_1+(n+1)x_2-\ldots -x_n-1),\ldots,(-x_1-x_2-\ldots -x_n+(n+1)),N(x_1a_1+x_2a_2+\ldots +x_na_n-s) \right]$$ 化簡後向量還要再解聯立方程式才是正確答案 $$\left[ \matrix{n+1&-1&-1&\ldots&-1 \cr -1&n+1&-1&\ldots&-1 \cr \vdots&\vdots&\vdots&\vdots&\vdots \cr -1&\ldots&-1&n+1&-1 \cr -1&\ldots&-1&-1&n+1 } \right] \left[ \matrix{x_1 \cr x_2 \cr \vdots \cr x_n \cr 1} \right]= \left[ \matrix{B[i,1]\cr B[i,2]\cr \vdots \cr B[i,n]\cr B[i,n+1]}\right]$$ 參考資料 Matthijs J. Coster, Antoine Joux, Brian A. LaMacchia, Andrew M. Odlyzko, Claus-Peter Schnorr, and Jacques Stern. 1992. Improved low-density subset sum algorithms. Comput. Complex. 2, 2 (December 1992), 111-128. https://d-nb.info/1156214629/34 請下載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:[48,181,278,361,506,639]; (%o2)　$$\left[48,181,278,361,506,639\right]$$ 物品個數 (%i3)　n:length(a); (%o3)　$$6$$ 總和 (%i4)　s:1146; (%o4)　$$1146$$ 大數字N($$N\ge n^2$$) (%i5)　N:n^2; (%o5)　$$36$$ 將N*a和-N*s放在一起 (%i6)　column:transpose(matrix(append(N*a,[-N*s]))); (%o6)　$$\left[ \matrix{1728\cr 6516\cr 10008\cr 12996\cr 18216\cr 23004\cr -41256} \right]$$ 產生左半邊矩陣 (%i7)　B:genmatrix(lambda([i,j],if i=j then n+1 else -1),n+1,n+1); (%o7)　$$\left[ \matrix{7&-1&-1&-1&-1&-1&-1\cr -1&7&-1&-1&-1&-1&-1\cr -1&-1&7&-1&-1&-1&-1\cr -1&-1&-1&7&-1&-1&-1\cr -1&-1&-1&-1&7&-1&-1\cr -1&-1&-1&-1&-1&7&-1\cr -1&-1&-1&-1&-1&-1&7} \right]$$ 先計算反矩陣，後面解聯立方程式會用到 (%i8)　invertB:invert(B); (%o8)　$$\left[ \matrix{\displaystyle \frac{1}{4}&\frac{1}{8}&\frac{1}{8}&\frac{1}{8}&\frac{1}{8}&\frac{1}{8}&\frac{1}{8}\cr \frac{1}{8}&\frac{1}{4}&\frac{1}{8}&\frac{1}{8}&\frac{1}{8}&\frac{1}{8}&\frac{1}{8}\cr \frac{1}{8}&\frac{1}{8}&\frac{1}{4}&\frac{1}{8}&\frac{1}{8}&\frac{1}{8}&\frac{1}{8}\cr \frac{1}{8}&\frac{1}{8}&\frac{1}{8}&\frac{1}{4}&\frac{1}{8}&\frac{1}{8}&\frac{1}{8}\cr \frac{1}{8}&\frac{1}{8}&\frac{1}{8}&\frac{1}{8}&\frac{1}{4}&\frac{1}{8}&\frac{1}{8}\cr \frac{1}{8}&\frac{1}{8}&\frac{1}{8}&\frac{1}{8}&\frac{1}{8}&\frac{1}{4}&\frac{1}{8}\cr \frac{1}{8}&\frac{1}{8}&\frac{1}{8}&\frac{1}{8}&\frac{1}{8}&\frac{1}{8}&\frac{1}{4}} \right]$$ 將兩個矩陣合併 (%i9)　B:addcol(B,column); (%o9)　$$\left[ \matrix{7&-1&-1&-1&-1&-1&-1&1728\cr -1&7&-1&-1&-1&-1&-1&6516\cr -1&-1&7&-1&-1&-1&-1&10008\cr -1&-1&-1&7&-1&-1&-1&12996\cr -1&-1&-1&-1&7&-1&-1&18216\cr -1&-1&-1&-1&-1&7&-1&23004\cr -1&-1&-1&-1&-1&-1&7&-41256} \right]$$ 經LLL化簡 (%i10)　B: LLL(B); (%o10)　$$\left[ \matrix{3&3&3&-5&-5&3&3&0\cr 1&1&-7&-7&1&9&1&0\cr -5&11&3&-5&3&-5&3&0\cr -17&-9&7&-1&7&7&7&0\cr 1&1&-7&1&1&1&-7&36\cr -4&-4&20&-20&4&-4&-36&0\cr -19&21&-11&29&-35&13&-3&0} \right]$$ 以B第一列向量解聯立方程式，求得x (%i11)　x:invertB.rest(B[1],-1); (%o11)　$$\left[ \matrix{1\cr 1\cr 1\cr 0\cr 0\cr 1\cr 1} \right]$$ 去掉最後一元，將矩陣轉成list，得到解答 (%i12)　x:args(transpose(rest(x,-1)))[1]; (%o12)　$$\left[1,1,1,0,0,1 \right]$$ 驗證a乘上x是否等於s (%i13)　is(x.a=s); (%o13)　$$true$$ UID210 帖子883 閱讀權限200 在線時間4786 小時 註冊時間2008-12-16 最後登錄2019-9-16  查看詳細資料 TOP
 bugmens 發短消息 加為好友 當前離線 8# 大 中 小 發表於 2019-3-10 23:32  只看該作者 7.解決子集合加總問題－Schnorr和Euchner方法 子集合加總問題為$$x_1a_1+x_2a_2+\ldots+x_na_n+x_{n+1}s=0$$，希望$$x_{n+1}$$為$$-1$$，但不同的$$a$$值可能讓$$x_{n+1}$$大於1或小於$$-1$$。故Schnorr和Euchner提出的$$lattice$$比Coster等人多加一行$$\left[ \matrix{0 \cr 0 \cr \vdots \cr 1} \right]$$，讓$$x_{n+1}$$也列入求向量長度的一元，若$$x_{n+1}$$大於1或小於$$-1$$會促使$$LLL$$化簡$$x_{n+1}$$為更小的數字以求得更短的向量。 $$B=\left[ \matrix{2&0&\ldots&0&na_1&0 \cr 0&2&\ldots&0&na_2&0 \cr \vdots&\vdots&\vdots&\vdots&\vdots&\vdots \cr 0&0&\ldots&2&na_n&0 \cr 1&1&\ldots&1&ns&1} \right]$$ 設$$b_1,b_2,\ldots,b_{n+1}$$的線性組合為 $$x_1b_1+x_2b_2+\ldots+x_nb_n+x_{n+1}\cdot b_{n+1}= \matrix{x_1 \left[2,0,\ldots,0,na_1,0 \right]+ \cr x_2 \left[0,2,\ldots,0,na_2,0 \right]+ \cr \ldots \cr x_n \left[0,0,\ldots,2,na_n,0 \right]+ \cr x_{n+1} \left[1,1,\ldots,1,ns,1 \right]}=$$ $$\left[ \matrix{2x_1+x_{n+1}\cr z_1},\matrix{2x_2+x_{n+1}\cr z_2},\ldots,\matrix{2x_n+x_{n+1}\cr z_n},\matrix{n(x_1a_1+x_2a_2+\ldots+x_na_n+x_{n+1}s)\cr z_{n+1}},\matrix{x_{n+1}\cr z_{n+2}} \right]$$ 化簡後找符合最後一元$$|\;z_{n+2}|\;=|\;x_{n+1}|\;=1$$，倒數第二元$$z_{n+1}=n(x_1a_1+x_2a_2+\ldots+x_na_n+x_{n+1}s)=0$$，其餘各元$$z_1,z_2,\ldots,z_n \in \lbrace\pm 1\rbrace$$的向量，計算$$x_i=|\;z_i-z_{n+2}|\;/2$$，$$i=1,2,\ldots,n$$得到正確答案。 參考資料 C. P. Schnorr and M. Euchner, “Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems,” Mathematical Programming, Vol. 66, No. 1-3, 1994, pp. 181-199. https://pdfs.semanticscholar.org ... a5330b46635eb5a.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:[48,181,278,361,506,639]; (%o2)　$$\left[48,181,278,361,506,639 \right]$$ 物品個數 (%i3)　n:length(a); (%o3)　$$6$$ 總和 (%i4)　s:1146; (%o4)　$$1146$$ 將n*a和n*s放在一起 (%i5)　column1:transpose(matrix(append(n*a,[n*s]))); (%o5)　$$\left[ \matrix{288\cr 1086\cr 1668\cr 2166\cr 3036\cr 3834\cr 6876} \right]$$ 最後一元為1其餘為0的矩陣 (%i6)　column2:genmatrix(lambda([i,j],if i=n+1 then 1 else 0),n+1,1); (%o6)　$$\left[\matrix{0\cr 0\cr 0\cr 0\cr 0\cr 0\cr 1}\right]$$ 產生左半邊矩陣 (%i7)　B:genmatrix(lambda([i,j],if i=j then 2 else if i=n+1 then 1 else 0),n+1,n); (%o7)　$$\left[\matrix{2&0&0&0&0&0\cr 0&2&0&0&0&0\cr 0&0&2&0&0&0\cr 0&0&0&2&0&0\cr 0&0&0&0&2&0\cr 0&0&0&0&0&2\cr 1&1&1&1&1&1} \right]$$ 將三個矩陣合併 (%i8)　B:addcol(B,column1,column2); (%o8)　$$\left[ \matrix{2&0&0&0&0&0&288&0\cr 0&2&0&0&0&0&1086&0\cr 0&0&2&0&0&0&1668&0\cr 0&0&0&2&0&0&2166&0\cr 0&0&0&0&2&0&3036&0\cr 0&0&0&0&0&2&3834&0\cr 1&1&1&1&1&1&6876&1} \right]$$ 經LLL化簡 (%i9)　B: LLL(B); (%o9)　$$\left[ \matrix{-1&-1&-1&1&1&-1&0&1\cr 0&0&-2&-2&0&2&0&0\cr -1&3&1&-1&1&-1&0&-1\cr -4&-2&2&-2&0&2&0&-2\cr 1&1&-1&-1&-1&1&6&1\cr -5&5&-3&7&-9&3&0&1\cr -1&-1&5&-7&-1&-1&0&9} \right]$$ 化簡後第一列向量符合(1)最後一元絕對值為1，(2)倒數第二元為0，(3)其餘的元為$$-1$$或$$+1$$ (%i10)　z:B[1]; (%o10)　$$\left[-1,-1,-1,1,1,-1,0,1 \right]$$ 計算xi=abs(z[ i ]-z[n+2])/2 (%i11)　x:abs(z-z[n+2])/2; (%o11)　$$\left[ \displaystyle 1,1,1,0,0,1,\frac{1}{2},0 \right]$$ 取前$$n$$元得到正確答案 (%i12)　x:rest(x,-2); (%o12)　$$\left[1,1,1,0,0,1 \right]$$ 驗證a乘上x是否等於s (%i13)　is(a.x=s); (%o13)　$$true$$ UID210 帖子883 閱讀權限200 在線時間4786 小時 註冊時間2008-12-16 最後登錄2019-9-16  查看詳細資料 TOP
 bugmens 發短消息 加為好友 當前離線 9# 大 中 小 發表於 2019-3-17 15:56  只看該作者 8.解決子集合加總問題－Schnorr和Shevchenko方法 Schnorr和Shevchenko假設正確答案有偶數個1且1的個數有$$\displaystyle \frac{n}{2}$$個$$\displaystyle \left(\sum_{i=1}^n x_i=\frac{n}{2}\right)$$，在$$lattice$$多加一行$$\left[ \matrix{N\cr N \cr \vdots \cr \frac{n}{2}N} \right]$$，當$$LLL$$計算$$lattice$$向量的線性組合時試圖找出讓$$N(x_1+x_2+\ldots+x_n+x_{n+1}\frac{n}{2})=0$$的解。 $$B=\left[ \matrix{2&0&\ldots&0&Na_1&0&N \cr 0&2&\ldots&0&Na_2&0&N \cr \vdots&\vdots&&\vdots&\vdots&\vdots&\vdots\cr 0&0&\ldots&2&Na_n&0&N \cr 1&1&\ldots&1&Ns&1&\frac{n}{2}N} \right]$$，$$N>\sqrt{n}$$ 設$$b_1,b_2,\ldots,b_{n+1}$$的線性組合為 $$x_1b_1+x_2b_2+\ldots+x_nb_n+x_{n+1}b_{n+1}= \matrix{x_1 \left[2,0,\ldots,0,Na_1,0,N \right]+\cr x_2 \left[0,2,\ldots,0,Na_2,0,N \right]+\cr \ldots \cr x_n \left[0,0,\ldots,2,Na_n,0,N \right]+\cr x_{n+1} \left[1,1,\ldots,1,Ns,1,\frac{n}{2}N \right]}$$ $$\left[2x_1+x_{n+1},2x_2+x_{n+1},\ldots,2x_n+x_{n+1},N(x_1a_1+x_2a_2+\ldots+x_na_n+x_{n+1}s),x_{n+1},N(x_1+x_2+\ldots+x_n+x_{n+1}\frac{n}{2}) \right]$$ 化簡後找符合最後一元為0，倒數第二元絕對值為1，倒數第三元為0，其餘的元為$$-1$$或$$+1$$的向量，計算$$x_i=|\;z_i−z_{n+2}|\;/2$$，$$i=1,2,\ldots,n$$得到正確答案。 參考資料 C.P.Schnorr and T.Shevchenko,"Solving Subset Sum Problems of Densioty close to 1 by "randomized" BKZ-reduction", IACR Cryptology ePrint Archive 2012: 620 (2012). https://eprint.iacr.org/2012/620.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:[48,181,278,361,506,639]; (%o2)　$$\left[48,181,278,361,506,639\right]$$ 物品個數 (%i3)　n:length(a); (%o3)　$$6$$ 大數字N($$N>\sqrt{n}$$) (%i4)　N:ceiling(sqrt(n)); (%o4)　$$3$$ 總和改為1193，$$48+506+639=1193$$，正確答案$$x=\left[1,0,0,0,1,1 \right]$$有3個1且1的個數有$$\frac{6}{2}=3$$個 (%i5)　s:1193; (%o5)　$$1193$$ 將N*a和N*s放在一起 (%i6)　column1:transpose(matrix(append(N*a,[N*s]))); (%o6)　$$\left[ \matrix{144\cr 543\cr 834\cr 1083\cr 1518\cr 1917\cr 3579} \right]$$ 最後一元為1其餘為0的矩陣 (%i7)　column2:genmatrix(lambda([i,j],if i=n+1 then 1 else 0),n+1,1); (%o7)　$$\left[ \matrix{0\cr 0\cr 0\cr 0\cr 0\cr 0\cr 1} \right]$$ 最後一元為n/2*N其餘為N的矩陣 (%i8)　column3:genmatrix(lambda([i,j],if i=n+1 then n/2*N else N),n+1,1); (%o8)　$$\left[ \matrix{3\cr 3\cr 3\cr 3\cr 3\cr 3\cr 9} \right]$$ 產生左半邊矩陣 (%i9)　B:genmatrix(lambda([i,j],if i=j then 2 else if i=n+1 then 1 else 0),n+1,n); (%o9)　$$\left[ \matrix{2&0&0&0&0&0\cr 0&2&0&0&0&0\cr 0&0&2&0&0&0\cr 0&0&0&2&0&0\cr 0&0&0&0&2&0\cr 0&0&0&0&0&2\cr 1&1&1&1&1&1} \right]$$ 將四個矩陣合併 (%i10)　B:addcol(B,column1,column2,column3); (%o10)　$$\left[ \matrix{2&0&0&0&0&0&144&0&3\cr 0&2&0&0&0&0&543&0&3\cr 0&0&2&0&0&0&834&0&3\cr 0&0&0&2&0&0&1083&0&3\cr 0&0&0&0&2&0&1518&0&3\cr 0&0&0&0&0&2&1917&0&3\cr 1&1&1&1&1&1&3579&1&9} \right]$$ 經LLL化簡 (%i11)　B: LLL(B); 0 errors, 0 warnings (%o11)　$$\left[ \matrix{-1&1&1&1&-1&-1&0&1&0\cr 1&-1&1&1&-3&1&0&1&0\cr -1&1&-1&-1&-1&1&0&1&-3\cr 0&-4&0&2&0&0&-3&0&-3\cr -3&-3&3&1&1&-1&3&-1&-3\cr -3&1&-5&5&-1&3&-3&-5&0\cr -5&1&9&-7&-1&5&-9&-7&3} \right]$$ 化簡後第一列向量符合(1)最後一元為0，(2)倒數第二元絕對值為1，(3)倒數第三元為0，(4)其餘的元為-1或+1 (%i12)　z:B[1]; (%o12)　$$\left[-1,1,1,1,-1,-1,0,1,0 \right]$$ 計算xi=abs(z[ i ]-z[n+2])/2 (%i13)　x:abs(z-z[n+2])/2; (%o13)　$$\displaystyle \left[1,0,0,0,1,1,\frac{1}{2},0,\frac{1}{2} \right]$$ 取前n元得到正確答案 (%i14)　x:rest(x,-3); (%o14)　$$\left[1,0,0,0,1,1 \right]$$ 驗證a乘上x是否等於s (%i15)　is(a.x=s); (%o15)　$$true$$ UID210 帖子883 閱讀權限200 在線時間4786 小時 註冊時間2008-12-16 最後登錄2019-9-16  查看詳細資料 TOP
﻿