Math Pro 數學補給站's Archiver

除非太陽不再升起,
否則不能不達到目標。

bugmens 發表於 2017-11-8 22:30

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

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

[color=green]要先載入lll.lisp才能使用latticereduce指令[/color]
[color=red](%i1)[/color] [color=blue]load("lll.lisp");[/color]
[color=red](%o1)[/color] [i]C:\maxima-5.41.0\share\maxima\5.41.0\share\contrib\lll.lisp[/i]

[color=green][url]https://math.pro/db/viewthread.php?tid=1876&page=1#pid10232[/url]的範例
執行結果正確[/color]
[color=red](%i2)[/color] [color=blue]latticereduce([[31,59],[37,70]]);[/color]
[color=red](%o2)[/color] \( [[1,4],[3,-1]] \)

[color=green][url]https://math.pro/db/viewthread.php?tid=1876&page=1#pid10232[/url]的範例
執行結果正確[/color]
[color=red](%i3)[/color] [color=blue]latticereduce([[47,9],[26,4]]);[/color]
[color=red](%o3)[/color] \( [[5,-1],[-1,-9]] \)

[color=green][url]https://math.pro/db/viewthread.php?tid=1876&page=1#pid10892[/url]的範例
執行結果錯誤,應該是\([[0,1,0],[1,0,1],[-1,0,2]]\)[/color]
[color=red](%i4)[/color] [color=blue]latticereduce([[1,1,1],[-1,0,2],[3,5,6]]);[/color]
[color=red](%o4)[/color] \( [[0,1,0],[1,0,1],[-2,0,1]] \)

[color=green][url]https://math.pro/db/viewthread.php?tid=1876&page=1#pid10831[/url]的範例
執行結果正確[/color]
[color=red](%i5)[/color] [color=blue]latticereduce([[1,1,7,2],[9,8,4,6],[1,8,5,7],[2,3,1,1]]);[/color]
[color=red](%o5)[/color] \( [[2,3,1,1],[3,-1,1,3],[-2,2,6,-1],[-4,1,-4,3]] \)

[color=green][url]https://math.pro/db/viewthread.php?tid=1876&page=1#pid10831[/url]的範例
latticereduce只能處理方陣,行數與列數不同會出現錯誤[/color]
[color=red](%i6)[/color]
[color=blue]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]]);[/color]
[color=red]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.[/color]



放棄使用maxima內建的LLL,改用自己寫的LLL()副程式
請下載[url=https://math.pro/db/attachment.php?aid=4282&k=9cf4654f63fb7d81b995fe3c87ae424a&t=1510060241]LLL.zip[/url],解壓縮後將LLL.mac放到[i]C:\maxima-5.41.0\share\maxima\5.41.0\share[/i]目錄下


[color=green]要先載入LLL.mac才能使用LLL指令[/color]
[color=red](%i1)[/color] [color=blue]load("LLL.mac");[/color]
[color=red](%o1)[/color] [i]C:\maxima-5.41.0\share\maxima\5.41.0\LLL.mac[/i]

[color=red](%i2)[/color]
[color=blue]LLL(matrix([31,59],
                [37,70]));[/color]
0 errors, 0 warnings
[color=red](%o2)[/color] \( \left[ \matrix{3&-1 \cr 1&4}\right] \)

[color=red](%i3)[/color]
[color=blue]LLL(matrix([47,9],
                [26,4]));[/color]
[color=red](%o3)[/color] \( \left[ \matrix{5&-1 \cr -1&-9}\right] \)

[color=red](%i4)[/color]
[color=blue]LLL(matrix([1,1,1],
                [-1,0,2],
                [3,5,6]));[/color]
[color=red](%o4)[/color] \( \left[ \matrix{0&1&0 \cr 1&0&1 \cr -1&0&2} \right] \)

[color=red](%i5)[/color]
[color=blue]LLL(matrix([1,1,7,2],
                [9,8,4,6],
                [1,8,5,7],
                [2,3,1,1]));[/color]
[color=red](%o5)[/color] \( \left[ \matrix{2&3&1&1 \cr 3&-1&1&3 \cr -2&2&6&-1 \cr -4&1&-4&3} \right] \)

[color=red](%i6)[/color]
[color=blue]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]));[/color]
[color=red](%o6)[/color] \( \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] \)

bugmens 發表於 2019-2-5 22:16

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加解密流程介紹如下:[table=98%]
[tr][td][align=Center]產生公鑰[/align][/td][td][align=Center]範例[/align][/td][/tr]
[tr][td]選擇一組數列\(w=\{\; w_1,w_2,\ldots,w_n \}\;\)[/td][td]\(w=\{\;2,7,11,21,42,89,180,354 \}\;\)[/td][/tr]
[tr][td]驗證是否為超遞增數列
\(\displaystyle w_i>\sum_{j=1}^{i-1}w_j \),\(i=2,3,\ldots,n\)[/td][td]\(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\)的確是超遞增數列[/td][/tr]
[tr][td]選一個比全部\(w\)總和還大的數字\(q\)[/td][td]\(q=881\),\(\displaystyle q>\sum_{i=1}^n w_i=706\)[/td][/tr]
[tr][td]選一個和\(q\)互質的隨機整數\(r\)[/td][td]\(r=588\),\(gcd(588,881)=1\)[/td][/tr]
[tr][td]計算\(\beta_i=rw_i \pmod{q}\)[/td][td]\((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\)[/td][/tr]
[tr][td]\(\beta=\{\;\beta_1,\beta_2,\ldots,\beta_n \}\;\)為公鑰
\( (w,q,r) \)為密鑰[/td][td]\(\beta=\{\;295, 592, 301, 14, 28, 353, 120, 236\}\;\)為公鑰
\((w,881,588)\)為密鑰[/td][/tr][/table]
[table=98%]
[tr][td][align=Center]加密[/align][/td][td][align=Center]範例[/align][/td][/tr]
[tr][td]加密\(n\)位元長度的訊息
\(\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_n)\),\(\alpha_i \in \{\;0,1 \}\;\)
其中\(\alpha_i\)是訊息的第\(i\)個位元[/td][td]加密8位元長度的訊息"a"
"a"的ASCII碼為97,轉成二進位01100001
\(\alpha=\{\;0,1,1,0,0,0,0,1 \}\;\)[/td][/tr]
[tr][td]計算\( \displaystyle c=\sum_{i=1}^{n}\alpha_i \beta_i \)
得到密文\(c\)[/td][td]計算\(c=\)
\(0 * 295\)
\(+ 1 * 592\)
\(+ 1 * 301\)
\(+ 0 * 14\)
\(+ 0 * 28\)
\(+ 0 * 353\)
\(+ 0 * 120\)
\(+ 1 * 236\)
\(= 1129\)
得到密文\(c=1129\)[/td][/tr][/table]
[table=98%]
[tr][td][align=Center]解密[/align][/td][td][align=Center]範例[/align][/td][/tr]
[tr][td]計算\(s\equiv r^{-1}\pmod{q}\)
 
因為\(r\)和\(q\)互質,\( sr\equiv 1\pmod{q} \)
存在整數\(k\)使得\( sr=kq+1 \),\(1=-kq+sr\)
利用輾轉相除法求出符合上式的\(s\)和\(k\)[/td][td]設\(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}\)[/td][/tr]
[tr][td]計算\(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}\)[/td][td]\(c'\equiv 1129*442 \equiv 372 \pmod{881}\)[/td][/tr]
[tr][td]從\(w\)選出最大元素\(w_k\)
若\( w_k>c' \)則\(\alpha_k=0\)
若\( w_k \le c' \)則\( \alpha_k=1 \),將\(c'\)減掉\( w_k \times \alpha_k \)
重複相同步驟直到\(c'=0\)為止([/td][td]\(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"[/td][/tr][/table]

參考資料
[url]https://en.wikipedia.org/wiki/Merkle–Hellman_knapsack_cryptosystem[/url]


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

[color=green]可加密n-bit的訊息[/color]
[color=red](%i2)[/color] [color=blue]n:length(w);[/color]
[color=red](%o2)[/color] 8

[color=green]w總和[/color]
[color=red](%i3)[/color] [color=blue]apply("+",w);[/color]
[color=red](%o3)[/color] 706

[color=green]選比w總和還大的數字q[/color]
[color=red](%i4)[/color] [color=blue]q:881;[/color]
[color=red](%o4)[/color] \(881\)

[color=green]選一個隨機整數r[/color]
[color=red](%i5)[/color] [color=blue]r:588;[/color]
[color=red](%o5)[/color] \(588\)

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

[color=green]明文的ASCII值[/color]
[color=red](%i7)[/color] [color=blue]ASCII:cint("a");[/color]
[color=red](%o7)[/color] \(97\)

[color=green]要先載入bitwise才能使用bit_and[/color]
[color=red](%i8)[/color] [color=blue]load("bitwise");[/color]
[color=red](%o8)[/color] C:\maxima-5.41.0a\share\maxima\5.41.0a_dirty\share\contrib\bitwise\bitwise.lisp

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

[color=green]和公鑰β相乘得到密文c[/color]
[color=red](%i10)[/color] [color=blue]c:alpha.beta;[/color]
[color=red](%o10)[/color] \(1129\)

[color=green]計算cr^(-1)mod q得到c'[/color]
[color=red](%i11)[/color]  [color=blue]cprime:mod(c*inv_mod(r,q),q);[/color]
[color=red](%o11)[/color] \(372\)

[color=green]解密[/color]
[color=red](%i14)[/color]
[color=blue]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;[/color]
[color=red](%o14)[/color] \( \left[ 0,1,1,0,0,0,0,1 \right] \)

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

[color=green]得到明文[/color]
[color=red](%i16)[/color] [color=blue]ascii(ASCII);[/color]
[color=red](%o16)[/color] a

bugmens 發表於 2019-2-10 21:54

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

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

bugmens 發表於 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.
[url]https://web.stevens.edu/algebraic/Files/SubsetSum/p229-lagarias.pdf[/url]



[color=green]請下載[url=https://math.pro/db/attachment.php?aid=4282&k=9cf4654f63fb7d81b995fe3c87ae424a&t=1510060241]LLL.zip[/url],解壓縮後將LLL.mac放到[i]C:\maxima-5.42.2\share\maxima\5.42.2\share[/i]目錄下
要先載入LLL.mac才能使用LLL指令[/color]
[color=red](%i1)[/color] [color=blue]load("LLL.mac");[/color]
[color=red](%o1)[/color] C:\maxima-5.42.2\share\maxima\5.42.2\share\LLL.mac

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

[color=green]總和[/color]
[color=red](%i3)[/color] [color=blue]s:1129;[/color]
[color=red](%o4)[/color] \(1129\)

[color=green]形成lattice[/color]
[color=red](%i4)[/color]
[color=blue]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]);[/color]
[color=red](%o4)[/color] \( \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] \)

[color=green]經LLL化簡[/color]
[color=red](%i5)[/color] [color=blue]B: LLL(B);[/color]
0 errors, 0 warnings
[color=red](%o5)[/color] \( \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] \)

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

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

[color=green]驗證a乘上x是否等於s[/color]
[color=red](%i8)[/color] [color=blue]is(a.x=s);[/color]
[color=red](%o8)[/color] \(true\)

-----------
另一個範例取自Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications的第7章範例7.6
[url]https://books.google.com.tw/books?id=XGjMBQAAQBAJ&lpg=PP1&hl=zh-TW&pg=PA118#v=onepage&q&f=false[/url]
物品重量\(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\)



[color=green]要先載入LLL.mac才能使用LLL指令[/color]
[color=red](%i1)[/color] [color=blue]load(LLL);[/color]
[color=red](%o1)[/color] C:\maxima-5.42.2\share\maxima\5.42.2\share\LLL.mac

[color=green]物品重量[/color]
[color=red](%i2)[/color]
[color=blue]a:[929737936,970987227,787514290,322163533,926801380,662236970,572718201,499197496,270712809,142942483,
994479591,143064843,724883274,285884973,71532418];[/color]
[color=red](%o2)[/color] \([929737936,970987227,787514290,322163533,926801380,662236970,572718201,499197496,270712809,142942483,\)
\(994479591,143064843,724883274,285884973,71532418 ]\)

[color=green]a個數n[/color]
[color=red](%i3)[/color] [color=blue]n:length(a);[/color]
[color=red](%o3)[/color] \(15\)

[color=green]總和s[/color]
[color=red](%i4)[/color] [color=blue]s:4740166124;[/color]
[color=red](%o4)[/color] \(4740166124\)

[color=green]將-a和s放在一起[/color]
[color=red](%i5)[/color] [color=blue]column:transpose(matrix(append(-a,[s])));[/color]
[color=red](%o5)[/color] \( \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] \)

[color=green]產生左半邊矩陣[/color]
[color=red](%i6)[/color] [color=blue]B:genmatrix(lambda([i,j],if i=j then 1 else 0),n+1,n);[/color]
[color=red](%o6)[/color] \(\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] \)

[color=green]將兩個矩陣合併[/color]
[color=red](%i7)[/color] [color=blue]B:addcol(B,column);[/color]
[color=red](%o7)[/color] \( \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] \)

[color=green]經LLL化簡[/color]
[color=red](%i8)[/color] [color=blue]B: LLL(B);[/color]
0 errors, 0 warnings
[color=red](%o8)[/color] \( \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] \)

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

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

[color=green]驗證a乘上x是否等於s[/color]
[color=red](%i11)[/color] [color=blue]is(a.x=s);[/color]
[color=red](%o11)[/color] \(true\)

bugmens 發表於 2019-2-17 12:51

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

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



[color=green]請下載[url=https://math.pro/db/attachment.php?aid=4282&k=9cf4654f63fb7d81b995fe3c87ae424a&t=1510060241]LLL.zip[/url],解壓縮後將LLL.mac放到[i]C:\maxima-5.42.2\share\maxima\5.42.2\share[/i]目錄下
要先載入LLL.mac才能使用LLL指令[/color]
[color=red](%i1)[/color] [color=blue]load("LLL.mac");[/color]
[color=red](%o1)[/color] C:\maxima-5.42.2\share\maxima\5.42.2\share\LLL.mac

[color=green]物品重量[/color]
[color=red](%i2)[/color] [color=blue]a:[48,181,278,361,506,639];[/color]
[color=red](%o2)[/color] \(\left[48,181,278,361,506,639 \right]\)

[color=green]物品個數[/color]
[color=red](%i3)[/color] [color=blue]n:length(a);[/color]
[color=red](%o3)[/color] \(6\)

[color=green]總和[/color]
[color=red](%i4)[/color] [color=blue]s:1146;[/color]
[color=red](%o4)[/color] \(1146\)

[color=green]解答48+181+278+639=1146[/color]
[color=red](%i5)[/color] [color=blue]x:[1,1,1,0,0,1];[/color]
[color=red](%o5)[/color] \( \left[1,1,1,0,0,1 \right] \)

[color=green]將-a和s放在一起[/color]
[color=red](%i6)[/color] [color=blue]column:transpose(matrix(append(-a,[s])));[/color]
[color=red](%o6)[/color] \( \left[ \matrix{-48\cr -181\cr -278\cr -361\cr -506\cr -639\cr 1146} \right] \)

[color=green]產生左半邊矩陣[/color]
[color=red](%i7)[/color] [color=blue]B:genmatrix(lambda([i,j],if i=j then 1 else 0),n+1,n);[/color]
[color=red](%o7)[/color] \( \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]\)

[color=green]將兩個矩陣合併[/color]
[color=red](%i8)[/color] [color=blue]B:addcol(B,column);[/color]
[color=red](%o8)[/color] \( \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] \)

[color=green]經LLL化簡後的矩陣B找不到向量[1,1,1,0,0,1,0][/color]
[color=red](%i9)[/color] [color=blue]B: LLL(B);[/color]
[color=red](%o9)[/color] \( \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] \)

[color=green]a的最大值[/color]
[color=red](%i10)[/color] [color=blue]MAX:apply('max,a);[/color]
[color=red](%o10)[/color] \(639\)

[color=green]此時密度小於0.645[/color]
[color=red](%i11)[/color] [color=blue]float(n/(log(MAX)/log(2)));[/color]
[color=red](%o11)[/color] \(0.6437994730001645\)

[color=green]若正面找不到答案,改從反面找答案[/color]
[color=red](%i12)[/color] [color=blue]sprime:apply("+",a)-s;[/color]
[color=red](%o12)[/color] \(867\)

[color=green]反面解答361+506=867[/color]
[color=red](%i13)[/color] [color=blue]xprime:[0,0,0,1,1,0];[/color]
[color=red](%o13)[/color] \( \left[0,0,0,1,1,0\right] \)

[color=green]再還原成正確解答[/color]
[color=red](%i14)[/color] [color=blue]x:1-xprime;[/color]
[color=red](%o14)[/color] \( \left[1,1,1,0,0,1 \right] \)

[color=green]利用a和s'構造出矩陣B'[/color]
[color=red](%i17)[/color]
[color=blue]Bprime:B$
Bprime[n+1,n+1]:sprime$
Bprime;[/color]
[color=red](%o17)[/color] \( \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] \)

[color=green]經LLL化簡後的矩陣B'找不到[0,0,0,1,1,0,0]向量[/color]
[color=red](%i18)[/color] [color=blue]LLL(Bprime);[/color]
[color=red](%o18)[/color] \( \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] \)

bugmens 發表於 2019-2-24 22:03

5.解決子集合加總問題-Coster等人方法

研究上一篇無法解決的範例,正確答案是\(48+181+278+639=1146\),對應的向量為\(\left[1,1,1,0,0,1,0\right]\),但其中暗藏\( 506+639=1145 \)和1146只相差1,對應的向量為\(\left[0,0,0,0,1,1,1 \right]\),向量長度\(\sqrt{3}\)還比正確答案的向量長度還短,讓\(LLL\)無法找到正確答案。
改善的方法是將\(lattice\)中的\(a\)和\(s\)同乘上大數字\(N\)後變成長向量,促使\(LLL\)再化簡成短向量直到\( N(-x_1a_1-x_2a_2-\ldots-x_na_n+s)=0 \)為止。最後一列向量改為\(\displaystyle \left[\frac{1}{2},\frac{1}{2},\frac{1}{2},\ldots,\frac{1}{2},Ns \right]\),讓原本大數字\(N\)從門檻\(N>\sqrt{n}\)降到\(\displaystyle N>\frac{1}{2}\sqrt{n}\),這樣的\(lattice\)可以在密度\(d(a)<0.9408\)以多項式時間內解出答案。
\( 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)

設\(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[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] \)
化簡後向量還要再減\(\displaystyle \frac{1}{2}\)才是正確答案。


參考資料
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.
[url]https://d-nb.info/1156214629/34[/url]

註1:
論文上用的是\( B=\left[ \matrix{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
0&0&0&\ldots&0&Ns} \right] \),\(N>\sqrt{n}\),但\(LLL\)化簡後的向量還要加上絕對值才是答案,所以本文章的\(lattice\) \(B\)仍加上負號
[table][tr][td][color=blue]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]));[/color]
\(\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]\)
[color=blue]B[3];[/color]
\( \left[\matrix{-1&-1&-1&0&0&-1&0} \right]\)
[/td][td][color=blue]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]));[/color]
\(\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]\)
[color=blue]B[3];[/color]
\( \left[\matrix{1&1&1&0&0&1&0} \right]\)[/td][/tr][/table]



[color=green]請下載[url=https://math.pro/db/attachment.php?aid=4282&k=9cf4654f63fb7d81b995fe3c87ae424a&t=1510060241]LLL.zip[/url],解壓縮後將LLL.mac放到[i]C:\maxima-5.42.2\share\maxima\5.42.2\share[/i]目錄下
要先載入LLL.mac才能使用LLL指令[/color]
[color=red](%i1)[/color] [color=blue]load("LLL.mac");[/color]
[color=red](%o1)[/color] C:\maxima-5.42.2\share\maxima\5.42.2\share\LLL.mac

[color=green]物品重量[/color]
[color=red](%i2)[/color] [color=blue]a:[48,181,278,361,506,639];[/color]
[color=red](%o2)[/color] \(\left[48,181,278,361,506,639\right]\)

[color=green]物品個數[/color]
[color=red](%i3)[/color] [color=blue]n:length(a);[/color]
[color=red](%o3)[/color] \(6\)

[color=green]總和[/color]
[color=red](%i4)[/color] [color=blue]s:1146;[/color]
[color=red](%o4)[/color] \(1146\)

[color=green]大數字N\(\displaystyle (N>\frac{1}{2}\sqrt{n})\)[/color]
[color=red](%i5)[/color] [color=blue]N:ceiling(sqrt(n)/2);[/color]
[color=red](%o5)[/color] \(2\)

[color=green]將-N*a和N*s放在一起[/color]
[color=red](%i6)[/color] [color=blue]column:transpose(matrix(append(-N*a,[N*s])));[/color]
[color=red](%o6)[/color] \( \left[\matrix{-96\cr
-362\cr
-556\cr
-722\cr
-1012\cr
-1278\cr
2292} \right] \)

[color=green]產生左半邊矩陣[/color]
[color=red](%i7)[/color] [color=blue]B:genmatrix(lambda([i,j],if i=n+1 then 1/2 else if i=j then 1 else 0),n+1,n);[/color]
[color=red](%o7)[/color] \(\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]\)

[color=green]將兩個矩陣合併[/color]
[color=red](%i8)[/color] [color=blue]B:addcol(B,column);[/color]
[color=red](%o8)[/color] \(\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]\)

[color=green]經LLL化簡[/color]
[color=red](%i9)[/color] [color=blue]B: LLL(B);[/color]
[color=red](%o9)[/color] \( \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] \)

[color=green]第5列向量各個數字為1/2或3/2且最後一元為0[/color]
[color=red](%i10)[/color] [color=blue]B[5];[/color]
[color=red](%o10)[/color] \(\displaystyle \left[ \displaystyle \frac{3}{2},\frac{3}{2},\frac{3}{2},\frac{1}{2},\frac{1}{2},\frac{3}{2},0 \right] \)

[color=green]同減1/2,去掉最後一元得到解答[/color]
[color=red](%i11)[/color] [color=blue]x:rest(B[5]-1/2,-1);[/color]
[color=red](%o11)[/color] \( \left[1,1,1,0,0,1 \right] \)

[color=green]驗證a乘上x是否等於s[/color]
[color=red](%i12)[/color] [color=blue]is(a.x=s);[/color]
[color=red](%o12)[/color] \(true\)

bugmens 發表於 2019-3-3 00:09

6.解決子集合加總問題-Coster等人方法

[color=blue]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]));[/color]
\(\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.
[url]https://d-nb.info/1156214629/34[/url]



[color=green]請下載[url=https://math.pro/db/attachment.php?aid=4282&k=9cf4654f63fb7d81b995fe3c87ae424a&t=1510060241]LLL.zip[/url],解壓縮後將LLL.mac放到[i]C:\maxima-5.42.2\share\maxima\5.42.2\share[/i]目錄下
要先載入LLL.mac才能使用LLL指令[/color]
[color=red](%i1)[/color] [color=blue]load("LLL.mac");[/color]
[color=red](%o1)[/color] C:\maxima-5.42.2\share\maxima\5.42.2\share\LLL.mac

[color=green]物品重量[/color]
[color=red](%i2)[/color] [color=blue]a:[48,181,278,361,506,639];[/color]
[color=red](%o2)[/color] \(\left[48,181,278,361,506,639\right]\)

[color=green]物品個數[/color]
[color=red](%i3)[/color] [color=blue]n:length(a);[/color]
[color=red](%o3)[/color] \(6\)

[color=green]總和[/color]
[color=red](%i4)[/color] [color=blue]s:1146;[/color]
[color=red](%o4)[/color] \(1146\)

[color=green]大數字N(\(N\ge n^2\))[/color]
[color=red](%i5)[/color] [color=blue]N:n^2;[/color]
[color=red](%o5)[/color] \(36\)

[color=green]將N*a和-N*s放在一起[/color]
[color=red](%i6)[/color] [color=blue]column:transpose(matrix(append(N*a,[-N*s])));[/color]
[color=red](%o6)[/color] \( \left[ \matrix{1728\cr 6516\cr 10008\cr 12996\cr 18216\cr 23004\cr -41256} \right] \)

[color=green]產生左半邊矩陣[/color]
[color=red](%i7)[/color] [color=blue]B:genmatrix(lambda([i,j],if i=j then n+1 else -1),n+1,n+1);[/color]
[color=red](%o7)[/color] \( \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] \)

[color=green]先計算反矩陣,後面解聯立方程式會用到[/color]
[color=red](%i8)[/color] [color=blue]invertB:invert(B);[/color]
[color=red](%o8)[/color] \( \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] \)

[color=green]將兩個矩陣合併[/color]
[color=red](%i9)[/color] [color=blue]B:addcol(B,column);[/color]
[color=red](%o9)[/color] \( \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] \)

[color=green]經LLL化簡[/color]
[color=red](%i10)[/color] [color=blue]B: LLL(B);[/color]
[color=red](%o10)[/color] \( \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] \)

[color=green]以B第一列向量解聯立方程式,求得x[/color]
[color=red](%i11)[/color] [color=blue]x:invertB.rest(B[1],-1);[/color]
[color=red](%o11)[/color] \( \left[ \matrix{1\cr 1\cr 1\cr 0\cr 0\cr 1\cr 1} \right] \)

[color=green]去掉最後一元,將矩陣轉成list,得到解答[/color]
[color=red](%i12)[/color] [color=blue]x:args(transpose(rest(x,-1)))[1];[/color]
[color=red](%o12)[/color] \( \left[1,1,1,0,0,1 \right] \)

[color=green]驗證a乘上x是否等於s[/color]
[color=red](%i13)[/color] [color=blue]is(x.a=s);[/color]
[color=red](%o13)[/color] \(true\)

bugmens 發表於 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.
[url]https://pdfs.semanticscholar.org/25fa/305b451395a517440f77fa5330b46635eb5a.pdf[/url]



[color=green]請下載[url=https://math.pro/db/attachment.php?aid=4282&k=9cf4654f63fb7d81b995fe3c87ae424a&t=1510060241]LLL.zip[/url],解壓縮後將LLL.mac放到[i]C:\maxima-5.42.2\share\maxima\5.42.2\share[/i]目錄下
要先載入LLL.mac才能使用LLL指令[/color]
[color=red](%i1)[/color] [color=blue]load("LLL.mac");[/color]
[color=red](%o1)[/color] C:\maxima-5.42.2\share\maxima\5.42.2\share\LLL.mac

[color=green]物品重量[/color]
[color=red](%i2)[/color] [color=blue]a:[48,181,278,361,506,639];[/color]
[color=red](%o2)[/color] \(\left[48,181,278,361,506,639 \right]\)

[color=green]物品個數[/color]
[color=red](%i3)[/color] [color=blue]n:length(a);[/color]
[color=red](%o3)[/color] \(6\)

[color=green]總和[/color]
[color=red](%i4)[/color] [color=blue]s:1146;[/color]
[color=red](%o4)[/color] \(1146\)

[color=green]將n*a和n*s放在一起[/color]
[color=red](%i5)[/color] [color=blue]column1:transpose(matrix(append(n*a,[n*s])));[/color]
[color=red](%o5)[/color] \( \left[ \matrix{288\cr 1086\cr 1668\cr 2166\cr 3036\cr 3834\cr 6876} \right] \)

[color=green]最後一元為1其餘為0的矩陣[/color]
[color=red](%i6)[/color] [color=blue]column2:genmatrix(lambda([i,j],if i=n+1 then 1 else 0),n+1,1);[/color]
[color=red](%o6)[/color] \( \left[\matrix{0\cr 0\cr 0\cr 0\cr 0\cr 0\cr 1}\right] \)

[color=green]產生左半邊矩陣[/color]
[color=red](%i7)[/color] [color=blue]B:genmatrix(lambda([i,j],if i=j then 2 else if i=n+1 then 1 else 0),n+1,n);[/color]
[color=red](%o7)[/color] \( \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] \)

[color=green]將三個矩陣合併[/color]
[color=red](%i8)[/color] [color=blue]B:addcol(B,column1,column2);[/color]
[color=red](%o8)[/color] \( \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] \)

[color=green]經LLL化簡[/color]
[color=red](%i9)[/color] [color=blue]B: LLL(B);[/color]
[color=red](%o9)[/color] \(\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]\)

[color=green]化簡後第一列向量符合(1)最後一元絕對值為1,(2)倒數第二元為0,(3)其餘的元為\(-1\)或\(+1\)[/color]
[color=red](%i10)[/color] [color=blue]z:B[1];[/color]
[color=red](%o10)[/color] \( \left[-1,-1,-1,1,1,-1,0,1 \right] \)

[color=green]計算xi=abs(z[ i ]-z[n+2])/2[/color]
[color=red](%i11)[/color] [color=blue]x:abs(z-z[n+2])/2;[/color]
[color=red](%o11)[/color] \(\left[ \displaystyle 1,1,1,0,0,1,\frac{1}{2},0 \right]\)

[color=green]取前\(n\)元得到正確答案[/color]
[color=red](%i12)[/color] [color=blue]x:rest(x,-2);[/color]
[color=red](%o12)[/color] \( \left[1,1,1,0,0,1 \right] \)

[color=green]驗證a乘上x是否等於s[/color]
[color=red](%i13)[/color] [color=blue]is(a.x=s);[/color]
[color=red](%o13)[/color] \(true\)

bugmens 發表於 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).
[url]https://eprint.iacr.org/2012/620.pdf[/url]



[color=green]請下載[url=https://math.pro/db/attachment.php?aid=4282&k=9cf4654f63fb7d81b995fe3c87ae424a&t=1510060241]LLL.zip[/url],解壓縮後將LLL.mac放到[i]C:\maxima-5.42.2\share\maxima\5.42.2\share[/i]目錄下
要先載入LLL.mac才能使用LLL指令[/color]
[color=red](%i1)[/color] [color=blue]load("LLL.mac");[/color]
[color=red](%o1)[/color] C:\maxima-5.42.2\share\maxima\5.42.2\share\LLL.mac

[color=green]物品重量[/color]
[color=red](%i2)[/color] [color=blue]a:[48,181,278,361,506,639];[/color]
[color=red](%o2)[/color] \(\left[48,181,278,361,506,639\right]\)

[color=green]物品個數[/color]
[color=red](%i3)[/color] [color=blue]n:length(a);[/color]
[color=red](%o3)[/color] \(6\)

[color=green]大數字N(\(N>\sqrt{n}\))[/color]
[color=red](%i4)[/color] [color=blue]N:ceiling(sqrt(n));[/color]
[color=red](%o4)[/color] \(3\)

[color=green]總和改為1193,\(48+506+639=1193\),正確答案\(x=\left[1,0,0,0,1,1 \right]\)有3個1且1的個數有\(\frac{6}{2}=3\)個[/color]
[color=red](%i5)[/color] [color=blue]s:1193;[/color]
[color=red](%o5)[/color] \(1193\)

[color=green]將N*a和N*s放在一起[/color]
[color=red](%i6)[/color] [color=blue]column1:transpose(matrix(append(N*a,[N*s])));[/color]
[color=red](%o6)[/color] \( \left[ \matrix{144\cr 543\cr 834\cr 1083\cr 1518\cr 1917\cr 3579} \right] \)

[color=green]最後一元為1其餘為0的矩陣[/color]
[color=red](%i7)[/color] [color=blue]column2:genmatrix(lambda([i,j],if i=n+1 then 1 else 0),n+1,1);[/color]
[color=red](%o7)[/color] \( \left[ \matrix{0\cr 0\cr 0\cr 0\cr 0\cr 0\cr 1} \right] \)

[color=green]最後一元為n/2*N其餘為N的矩陣[/color]
[color=red](%i8)[/color] [color=blue]column3:genmatrix(lambda([i,j],if i=n+1 then n/2*N else N),n+1,1);[/color]
[color=red](%o8)[/color] \( \left[ \matrix{3\cr 3\cr 3\cr 3\cr 3\cr 3\cr 9} \right] \)

[color=green]產生左半邊矩陣[/color]
[color=red](%i9)[/color] [color=blue]B:genmatrix(lambda([i,j],if i=j then 2 else if i=n+1 then 1 else 0),n+1,n);[/color]
[color=red](%o9)[/color] \(\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]\)

[color=green]將四個矩陣合併[/color]
[color=red](%i10)[/color] [color=blue]B:addcol(B,column1,column2,column3);[/color]
[color=red](%o10)[/color] \(\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]\)

[color=green]經LLL化簡[/color]
[color=red](%i11)[/color] [color=blue]B: LLL(B);[/color]
0 errors, 0 warnings
[color=red](%o11)[/color] \( \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] \)

[color=green]化簡後第一列向量符合(1)最後一元為0,(2)倒數第二元絕對值為1,(3)倒數第三元為0,(4)其餘的元為-1或+1[/color]
[color=red](%i12)[/color] [color=blue]z:B[1];[/color]
[color=red](%o12)[/color] \( \left[-1,1,1,1,-1,-1,0,1,0 \right] \)

[color=green]計算xi=abs(z[ i ]-z[n+2])/2[/color]
[color=red](%i13)[/color] [color=blue]x:abs(z-z[n+2])/2;[/color]
[color=red](%o13)[/color] \( \displaystyle \left[1,0,0,0,1,1,\frac{1}{2},0,\frac{1}{2} \right] \)

[color=green]取前n元得到正確答案[/color]
[color=red](%i14)[/color] [color=blue]x:rest(x,-3);[/color]
[color=red](%o14)[/color] \( \left[1,0,0,0,1,1 \right] \)

[color=green]驗證a乘上x是否等於s[/color]
[color=red](%i15)[/color] [color=blue]is(a.x=s);[/color]
[color=red](%o15)[/color] \(true\)

頁: [1]

論壇程式使用 Discuz! Archiver 6.1.0  © 2001-2007 Comsenz Inc.