Math Pro 數學補給站 » 數學軟體 » 用maxima學密碼學－Lattice Reduction

bugmens 發表於 2014-5-2 04:20

用maxima學密碼學－Lattice Reduction

令\( v_1,v_2,\ldots,v_n \in R^n \)是n個線性獨立的向量，由這些向量所組成的lattice定義為\( L=\{\; a_1 v_1+a_2

v_2+\ldots+a_nv_n |\; a_1,a_2,\ldots,a_n \in Z \}\; \)。

這些線性獨立的向量又稱為lattice L的基底(basis)，而生成lattice L的基底不只一個。例如：
\( v_1=(47,9),v_2=(26,4) \)，\( L_1=\{\;a_1 (47,9)+a_2 (26,4) |\; a_1,a_2 \in Z \}\; \)
由\( v_1,v_2 \)這兩個基底所生成的\( lattice L_1 \)為圖中的格子點。
也可以取\( u_1=(-5,1),u_2=(1,9) \)，\( L_2=\{\; a_1(-5,1)+a_2(1,9) |\; a_1,a_2 \in Z \}\; \)
由\( u_1,u_2 \)這兩個基底所生成的\( lattice L_2 \)就和\( lattice L_1 \)一模一樣
因為每一個向量都是另一組基底的線性組合。
\( \displaystyle \cases{(47,9)=-9(-5,1)+2(1,9) \cr (26,4)=-5(-5,1)+1(1,9)} \)　，　\( \displaystyle \cases{(-

5,1)=1(47,9)-2(26,4) \cr (1,9)=5(47,9)-9(26,4)} \)
[img]http://upload.wikimedia.org/wikipedia/commons/2/27/Lattice-reduction.svg[/img]
圖出自[url]https://en.wikipedia.org/wiki/Lattice_reduction[/url]

這兩組基底我們比較偏好\( u_1,u_2 \)，因為這組基底相較於\( v_1,v_2 \)長度比較短，夾角也幾乎正交(垂直)。
所以將\( v_1,v_2 \)化簡為\( u_1,u_2 \)的過程就稱為Lattice Reduction。

bugmens 發表於 2014-5-5 09:20

二維Lattice Reduction演算法－Gaussian/Lagrange方法

上一篇提到\( u_1,u_2 \)是比較好的基底，因為向量長度較短且夾角幾乎正交(垂直)。這一篇就來介紹如何計算出\( u_1,u_2 \)，這個方法是由Gauss和Lagrange分別提出來的，所以有些書是寫Gaussian algorithm，但我也看過用Lagrange algorithm的。


do{
　if(\( v_1 \)的長度>\( v_2 \)的長度)
　　{\( v_1 \)和\( v_2 \)兩個向量交換}
　\( \displaystyle t=\Bigg\lceil\; \frac{v_1 . v_2}{v_1 . v_1} \Bigg\rfloor\; \);
　if(t!=0)
　　{\( v_2=v_2-t*v_1; \)}
　}
while(t!=0);[/i]

註：\( \lceil\; x \rfloor\; \)代表離x最接近的整數，例如\( \lceil\; 0.3 \rfloor\;=0 \)，\( \lceil\; 0.8 \rfloor\;=1 \)，\( \lceil\; 0.5 \rfloor\;=0 \)，maxima的指令為round()。


以前面的例子計算\( v_1=(47,9) \)，\( v_2=(26,4) \)
第1輪
\( |\; v_1 |\;=\sqrt{47^2+9^2}=\sqrt{2290} \)，\( |\; v_2 |\;=\sqrt{26^2+4^2}=\sqrt{692} \)
\( v_1 \)的長度大於\( v_2 \)的長度，將兩個向量交換，\( v_1=(26,4) \)，\( v_2=(47,9) \)
計算\( \displaystyle \frac{(26,4)\cdot(47,9)}{(26,4)\cdot(26,4)}=\frac{26*47+4*9}{26*26+4*4}=\frac{1258}{692}≈1.81 \)
\( \displaystyle t=\lceil\; 1.81 \rfloor\;=2 \)
t不等於0，\( v_2=(47,9)-2*(26,4)=(-5,1) \)

第2輪
\( |\; v_1 |\;=\sqrt{26^2+4^2}=\sqrt{692} \)，\( |\; v_2 |\;=\sqrt{(-5)^2+1^2}=\sqrt{26} \)
\( v_1 \)的長度大於\( v_2 \)的長度，將兩個向量交換，\( v_1=(-5,1) \)，\( v_2=(26,4) \)
計算\( \displaystyle \frac{(-5,1)\cdot(26,4)}{(-5,1)\cdot(-5,1)}=\frac{-5*26+1*4}{(-5)*(-5)+1*1}=\frac{-126}{26}≈-4.84 \)
\( \displaystyle t=\lceil\; -4.84 \rfloor\;=-5 \)
t不等於0，\( v_2=(26,4)-(-5)*(-5,1)=(1,9) \)

第3輪
\( |\; v_1 |\;=\sqrt{(-5)^2+1^2}=\sqrt{26} \)，\( |\; v_2 |\;=\sqrt{1^2+9^2}=\sqrt{82} \)
\( v_1 \)的長度小於\( v_2 \)的長度，兩個向量不交換。
計算\( \displaystyle \frac{(-5,1)\cdot(1,9)}{(-5,1)\cdot(-5,1)}=\frac{(-5)*1+1*9}{(-5)*(-5)+1*1}=\frac{4}{26}≈0.15 \)
\( \displaystyle t=\lceil\; 0.15 \rfloor\;=0 \)
t等於0程式結束，化簡後的向量為\( u_1=(-5,1) \)，\( u_2=(1,9) \)。



[color=green]要化簡的向量[/color]
[color=red](%i1)[/color]
[color=blue]v1:[47,9];
v2:[26,4];[/color]
[color=red](%o1)[/color]　[47,9]
[color=red](%o2)[/color]　[26,4]

[color=red](%i3)[/color]
[color=blue]GaussianReduction(v1,v2):=block
  ([End,temp,t],
   do(End:true,
      if v1.v1>v2.v2 then
        (temp:v1,
         v1:v2,
         v2:temp,
         End:false
        ),
      t:round(v1.v2/v1.v1),
      if t#0 then
        (v2:v2-t*v1,
         End:false
        ),
      if End=true then
        (return([v1,v2])
        )
     )
  )$[/color]
[color=red](%i4)[/color]　[color=blue][u1,u2]:GaussianReduction(v1,v2);[/color]
[color=red](%o4)[/color]　[ [-5,1],[1,9] ]

[color=green]化簡後的向量[/color]
[color=red](%i5)[/color]
[color=blue]u1;
u2;[/color]
[color=red](%o5)[/color]　[-5,1]
[color=red](%o6)[/color]　[1,9]



補充書上的例子，這個例子取自Introduction to Cryptography with Coding Theory第17章，作者Wade Trappe and Lawrence C. Washington
\( v_1=(31,59) \)，\( v_2=(37,70) \)
第1輪
\( |\; v_1 |\;=\sqrt{31^2+59^2}=\sqrt{4442} \)，\( |\; v_2 |\;=\sqrt{37^2+70^2}=\sqrt{6269} \)
\( v_1 \)的長度小於\( v_2 \)的長度，兩個向量不交換
計算\( \displaystyle \frac{(31,59)\cdot(37,70)}{(31,59)\cdot(31,59)}=\frac{31*37+59*70}{31*31+59*59}=\frac{5277}{4442}≈1.18 \)
\( \displaystyle t=\lceil\; 1.18 \rfloor\;=1 \)
t不等於0，\( v_2=(37,70)-1*(31,59)=(6,11) \)

第2輪
\( |\; v_1 |\;=\sqrt{31^2+59^2}=\sqrt{4442} \)，\( |\; v_2 |\;=\sqrt{6^2+11^2}=\sqrt{157} \)
\( v_1 \)的長度大於\( v_2 \)的長度，將兩個向量交換，\( v_1=(6,11) \)，\( v_2=(31,59) \)
計算\( \displaystyle \frac{(6,11)\cdot(31,59)}{(6,11)\cdot(6,11)}=\frac{6*31+11*59}{6*6+11*11}=\frac{835}{157}≈5.31 \)
\( \displaystyle t=\lceil\; 5.31 \rfloor\;=5 \)
t不等於0，\( v_2=(31,59)-5*(6,11)=(1,4) \)

第3輪
\( |\; v_1 |\;=\sqrt{6^2+11^2}=\sqrt{157} \)，\( |\; v_2 |\;=\sqrt{1^2+4^2}=\sqrt{17} \)
\( v_1 \)的長度大於\( v_2 \)的長度，將兩個向量交換，\( v_1=(1,4) \)，\( v_2=(6,11) \)
計算\( \displaystyle \frac{(1,4)\cdot(6,11)}{(1,4)\cdot(1,4)}=\frac{1*6+4*11}{1*1+4*4}=\frac{50}{17}≈2.94 \)
\( \displaystyle t=\lceil\; 2.94 \rfloor\;=3 \)
t不等於0，\( v_2=(6,11)-3*(1,4)=(3,-1) \)

第4輪
\( |\; v_1 |\;=\sqrt{1^2+4^2}=\sqrt{17} \)，\( |\; v_2 |\;=\sqrt{3^2+(-1)^2}=\sqrt{10} \)
\( v_1 \)的長度大於\( v_2 \)的長度，將兩個向量交換，\( v_1=(3,-1) \)，\( v_2=(1,4) \)
計算\( \displaystyle \frac{(3,-1)\cdot(1,4)}{(3,-1)\cdot(3,-1)}=\frac{3*1+(-1)*4}{3*3+(-1)*(-1)}=\frac{-1}{10}=-0.1 \)
\( \displaystyle t=\lceil\; -0.1 \rfloor\;=0 \)
t等於0程式結束，化簡後的向量為\( u_1=(3,-1) \)，\( u_2=(1,4) \)。



這個例子取自Lattice Basis Reduction：An Introduction to the LLL Algorithm and Its Applications第2章，作者Murray R. Bremner
\( v_1=(-56,43) \)，\( v_2=(95,-73) \)
第1輪
\( |\; v_1 |\;=\sqrt{(-56)^2+43^2}=\sqrt{4985} \)，\( |\; v_2 |\;=\sqrt{95^2+(-43)^2}=\sqrt{10874} \)
\( v_1 \)的長度小於\( v_2 \)的長度，兩個向量不交換
計算\( \displaystyle \frac{(-56,43)\cdot(95,-73)}{(-56,43)\cdot(-56,43)}=\frac{-56*95+43*(-73)}{(-56)*(-56)+43*43}=\frac{-8459}{4985}≈-1.69 \)
\( \displaystyle t=\lceil\; -1.69 \rfloor\;=-2 \)
t不等於0，\( v_2=(95,-73)-(-2)*(-56,43)=(-17,13) \)

第2輪
\( |\; v_1 |\;=\sqrt{(-56)^2+43^2}=\sqrt{4985} \)，\( |\; v_2 |\;=\sqrt{(-17)^2+13^2}=\sqrt{458} \)
\( v_1 \)的長度大於\( v_2 \)的長度，將兩個向量交換，\( v_1=(-17,13) \)，\( v_2=(-56,43) \)
計算\( \displaystyle \frac{(-17,13)\cdot(-56,43)}{(-17,13)\cdot(-17,13)}=\frac{(-17)*(-56)+13*43}{(-17)*(-17)+13*13}=\frac{1511}{458}≈3.29 \)
\( \displaystyle t=\lceil\; 3.29 \rfloor\;=3 \)
t不等於0，\( v_2=(-56,43)-3*(-17,13)=(-5,4) \)

第3輪
\( |\; v_1 |\;=\sqrt{(-17)^2+13^2}=\sqrt{458} \)，\( |\; v_2 |\;=\sqrt{(-5)^2+4^2}=\sqrt{41} \)
\( v_1 \)的長度大於\( v_2 \)的長度，將兩個向量交換，\( v_1=(-5,4) \)，\( v_2=(-17,13) \)
計算\( \displaystyle \frac{(-5,4)\cdot(-17,13)}{(-5,4)\cdot(-5,4)}=\frac{(-5)*(-17)+4*13}{(-5)*(-5)+4*4}=\frac{137}{41}≈3.34 \)
\( \displaystyle t=\lceil\; 3.34 \rfloor\;=3 \)
t不等於0，\( v_2=(-17,13)-3*(-5,4)=(-2,1) \)

第4輪
\( |\; v_1 |\;=\sqrt{(-5)^2+4^2}=\sqrt{41} \)，\( |\; v_2 |\;=\sqrt{(-2)^2+1^2}=\sqrt{5} \)
\( v_1 \)的長度大於\( v_2 \)的長度，將兩個向量交換，\( v_1=(-2,1) \)，\( v_2=(-5,4) \)
計算\( \displaystyle \frac{(-2,1)\cdot(-5,4)}{(-2,1)\cdot(-2,1)}=\frac{(-2)*(-5)+1*4}{(-2)*(-2)+1*1}=\frac{14}{5}=2.8 \)
\( \displaystyle t=\lceil\; 2.8 \rfloor\;=3 \)
t不等於0，\( v_2=(-5,4)-3*(-2,1)=(1,1) \)

第5輪
\( |\; v_1 |\;=\sqrt{(-2)^2+1^2}=\sqrt{5} \)，\( |\; v_2 |\;=\sqrt{1^2+1^2}=\sqrt{2} \)
\( v_1 \)的長度大於\( v_2 \)的長度，將兩個向量交換，\( v_1=(1,1) \)，\( v_2=(-2,1) \)
計算\( \displaystyle \frac{(1,1)\cdot(-2,1)}{(1,1)\cdot(1,1)}=\frac{1*(-2)+1*1}{1*1+1*1}=\frac{-1}{2}=-0.5 \)
\( \displaystyle t=\lceil\; -0.5 \rfloor\;=-1 \)　　　　　[color=blue]註：這本書採用\( \lceil\; -0.5 \rfloor\;=-1 \)的定義[/color]
t不等於0，\( v_2=(-2,1)-(-1)*(1,1)=(-1,2) \)

第6輪
\( |\; v_1 |\;=\sqrt{1^2+1^2}=\sqrt{2} \)，\( |\; v_2 |\;=\sqrt{(-1)^2+2^2}=\sqrt{5} \)
\( v_1 \)的長度小於\( v_2 \)的長度，兩個向量不交換。
作者說到這裡就結束了，得到\( u_1=(1,1) \)，\( u_2=(-1,2) \)

但繼續計算的話\( \displaystyle \frac{(1,1)\cdot(-1,2)}{(1,1)\cdot(1,1)}=\frac{1*(-1)+1*2}{1*1+1*1}=\frac{1}{2}=0.5 \)
\( \displaystyle t=\lceil\; 0.5 \rfloor\;=1 \)
t不等於0，\( v_2=(-1,2)-1*(1,1)=(-2,1) \)
又回到之前的向量，導致程式無法結束，所以\( \lceil\; -0.5 \rfloor\; \)還是要定義為0才對。

[[i] 本帖最後由 bugmens 於 2014-5-6 06:18 AM 編輯 [/i]]

bugmens 發表於 2014-5-7 21:03

這次我改用GeoGebra實作二維Lattice Reduction。你可以隨意指定\( v_1,v_2 \)向量，按下"Lattice Reduction"按鈕後產生化簡後的\( u_1,u_2 \)。可以發現\( u_1 \)是全部的Lattice中長度最短的向量。

[img]https://www.geogebra.org/forum/download/file.php?id=24491[/img]

附加檔案：[url=http://tube.geogebra.org/material/download/format/file/id/566693]2DimensionLatticeReduction.ggb[/url]

[[i] 本帖最後由 bugmens 於 2015-3-27 09:09 PM 編輯 [/i]]

bugmens 發表於 2014-5-11 17:54

do{
　if(\( v_1 \)的長度>\( v_2 \)的長度)
　　{\( v_1 \)和\( v_2 \)兩個向量交換}
　\( \displaystyle t=\Bigg\lceil\; \frac{v_1 . v_2}{v_1 . v_1} \Bigg\rfloor\; \);
　if(t!=0)
　　{\( v_2=v_2-t*v_1; \)}
　}
while(t!=0);[/i]

以下兩個證明取自Introduction to Cryptography with Coding Theory第17章，作者Wade Trappe and Lawrence C. Washington
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
證明演算法會在有限的步驟內結束。
[證明]
若\( v_1 \)的長度大於\( v_2 \)的長度，則將兩個向量交換，故假設\( \Vert\; v_1 \Vert\;<\Vert\; v_2 \Vert\; \)。
仿照線性代數的Gram–Schmidt正交化
[url]http://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process[/url]
設\( \displaystyle v_2^*=v_2-\frac{v_1 \cdot v_2}{v_1 \cdot v_1}v_1 \)　⇒　\( \displaystyle v_2^* \cdot v_1=(v_2-\frac{v_1 \cdot v_2}{v_1 \cdot v_1}v_1)\cdot v_1=0 \)　⇒　\( v_2^* \)和\( v_1 \)正交(垂直)

令\( \displaystyle u=\frac{v_1 \cdot v_2}{v_1 \cdot v_1} \)　⇒　\( v_2^*=v_2-uv_1 \)　⇒　\( v_2=v_2^*+uv_1 \)
計算\( v_2 \)向量長度的平方
\( \displaystyle \Vert\; v_2 \Vert\;^2=(v_2^*+uv_1)^2=\Vert\; v_2^* \Vert\;^2+2uv_2^* \cdot v_1+u^2 \Vert\; v_1 \Vert\;^2=\Vert\; v_2^* \Vert\;^2+u^2 \Vert\; v_1 \Vert\;^2 \)

令\( \displaystyle t=\Bigg\lceil\; \frac{v_1 . v_2}{v_1 . v_1} \Bigg\rfloor\; \)　⇒　\( v_2-tv_1=(v_2^*+uv_1)-tv_1=v_2^*+(u-t)v_1 \)
計算\( v_2-tv_1 \)向量長度的平方
\( \displaystyle \Vert\; v_2-tv_1 \Vert\;^2=(v_2^*+(u-t)v_1)^2=\Vert\; v_2^* \Vert\;^2+2(u-t)v_2^* \cdot v_1+(u-t)^2 \Vert\; v_1 \Vert\;^2=\Vert\; v_2^* \Vert\;^2+(u-t)^2 \Vert\; v_1 \Vert\;^2 \)

當\( \displaystyle |\; u |\;>\frac{1}{2} \)時，t是個不為0的整數，故\( \displaystyle \frac{1}{2}>|\; u-t |\; \)得到\( |\; u |\;>|\; u-t |\; \)
\( \Vert\; v_2^* \Vert\;^2+u^2\Vert\; v_1 \Vert\;^2>\Vert\; v_2^* \Vert\;^2+(u-t)^2 \Vert\; v_1 \Vert\;^2 \)
\(  \Vert\; v_2 \Vert\;^2> \Vert\; v_2-tv_1 \Vert\;^2 \)
代表化簡後的向量(\( v_2-tv_1 \))長度會比原來的向量(\( v_2 \))長度來得短，然而在整個lattice中只有有限個向量長度會比\( v_2 \)短，所以演算法一定會在有限個步驟內結束。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
證明演算法執行完的\( v_1 \)和\( v_2 \)向量，其中\( v_1 \)是整個lattice中長度最短的向量。
[證明]
演算法執行完的\( v_1 \)和\( v_2 \)符合兩個條件
(1)\( \Vert\; v_2 \Vert\;>\Vert\; v_1 \Vert\; \)　⇒　\( \Vert\; v_2 \Vert\;^2>\Vert\; v_1 \Vert\;^2 \)
(2)\( \displaystyle -\frac{1}{2}\le \frac{v_1 \cdot v_2}{v_1 \cdot v_1}\le +\frac{1}{2} \)　⇒　\( -v_1 \cdot v_1 \le 2v_1 \cdot v_2 \)　⇒　\( 2v_1 \cdot v_2 \ge -\Vert\; v_1 \Vert\;^2 \)
令整個lattice中任意的非零向量\( av_1+bv_2 \)，\( a,b \in Z \)，\( a,b \)不會同時為0
計算\( av_1+bv_2 \)向量長度的平方
\( \matrix{\Vert\; av_1+bv_2 \Vert\;^2 & =a^2\Vert\; v_1 \Vert\;^2+2ab v_1 \cdot v_2+b^2 \Vert\; v_2 \Vert\;^2 \cr
　& \ge a^2\Vert\; v_1 \Vert\;^2-|\; ab |\; \Vert\; v_1 \Vert\;^2+b^2 \Vert\; v_2 \Vert\;^2 \cr
　& \ge a^2\Vert\; v_1 \Vert\;^2-|\; ab |\; \Vert\; v_1 \Vert\;^2+b^2 \Vert\; v_1 \Vert\;^2 \cr
　& =(a^2-|\; ab |\;+b^2)\Vert\; v_1 \Vert\;^2　　　　　} \)
因為\( a,b \)是不會同時為0的整數，由算幾不等式可知\( \displaystyle \frac{a^2+b^2}{2}\ge \sqrt{a^2 \cdot b^2}=|\; ab |\; \)　⇒　\( a^2-|\; ab |\;+b^2 \ge |\; ab |\;\ge 1 \)
得到\( \Vert\; av_1+bv_2 \Vert\;^2 \ge \Vert\; v_1 \Vert\;^2 \)，故\( v_1 \)是整個lattice中長度最短的向量。

bugmens 發表於 2014-5-30 20:53

高維度的Lattice Reduction演算法－LLL方法

A. K. Lenstra、H. W. Lenstra和L. Lovász在1982年提出LLL演算法，這方法可於多項式時間內，從給定的lattice中找到較短的向量。前面的Gaussian/Lagrange方法和LLL方法都會將較長的向量去減掉某個倍數的較短向量，減完的結果會比原來的短向量還要更短，這很像是輾轉相除法求最大公因數的過程。
例如求11和25的最大公因數，計算過程為\( (11,25)=(11,3)=(2,3)=(2,1)=1 \)。都是拿大數字去減掉某個倍數的小數字，減完的結果會比原本的小數字還小。

[img]http://i.imgur.com/159eU6r.jpg[/img]
從左邊第二位開始依序為László Lovász、Hendrik Lenstra和 Arjen Lenstra，因為三個人的開頭字母都有L，所以他們所發明的演算法被稱為LLL演算法。
這裡有更多關於LLL的歷史。
[url]http://infoscience.epfl.ch/record/164563/files/NPDF-53.pdf[/url]


令\( v_1,v_2,\ldots,v_n \in R^n \)是線性獨立的向量，先來回顧在線性代數中的Gram-Schmidt正交化
\( v_i^*=\cases{\matrix{v_1 & ,if　i=1 \cr v_i-\displaystyle \sum_{j=1}^{i-1}\mu_{ij}v_j^* &,if　i>1}} \)，其中\( \displaystyle u_{ij}=\frac{v_i \cdot v_j^*}{\Vert\; v_j^* \Vert\;^2} \)　，　\( \cdot \)符號為兩向量內積。
經Gram-Schmidt正交化所產生的\( v_1^*,v_2^*,\ldots,v_n^* \)向量會彼此互相垂直。
[url]http://en.wikipedia.org/wiki/Gram-Schmidt[/url]


若\( v_1,v_2, \ldots, v_n \)向量符合以下兩個條件就代表這是個reduced lattice
(1)Size condition：\( \displaystyle \vert\; \mu_{ij} \vert\; \le \frac{1}{2} \)　　\( 1 \le j < i \le n \)
(2)Lovász condition：\( \displaystyle \Vert\; v_i^*+u_{i,i-1}v_{i-1}^* \Vert\;^2 \ge \frac{3}{4} \Vert\; v_{i-1}^* \Vert\;^2 \)　　\( 1<i \le n \)


\( \displaystyle \frac{3}{4} \)可以換成\( \displaystyle \frac{1}{4}<y \le 1 \)的實數y，實務上常取\( y=0.99 \)。
可到[url]http://perso.ens-lyon.fr/damien.stehle/fplll/fplll-doc.html[/url]　搜尋delta = 0.99
Lovász condition在原本的論文是用\( \displaystyle \Vert\; v_i^*+u_{i,i-1}v_{i-1}^* \Vert\;^2 \ge \frac{3}{4} \Vert\; v_{i-1}^* \Vert\;^2 \)，但有些書採用\( \displaystyle \Vert\; v_i^* \Vert\;^2 \ge (\frac{3}{4}-\mu_{i,i-1}^2)\Vert\; v_{i-1}^* \Vert\;^2 \)的寫法，這兩種寫法其實是等價的。
[證明]
\( \displaystyle \Vert\; v_i^*+\mu_{i,i-1}v_{i-1}^* \Vert\;^2 \ge \frac{3}{4} \Vert\; v_{i-1}^* \Vert\;^2 \)
\( \displaystyle \Vert\; v_i^* \Vert\;^2+2 \mu_{i,i-1}v_i^* v_{i-1}^*+\mu_{i,i-1}^2 \Vert\; v_{i-1} \Vert\;^2 \ge \frac{3}{4} \Vert\; v_{i-1}^* \Vert\;^2 \)
∵\( v_{i-1}^* \)和\( v_{i}^* \)彼此正交，∴\( v_{i-1}^* \cdot v_i^*=0 \)
\( \displaystyle \Vert\; v_i^* \Vert\;^2+\mu_{i,i-1}^2 \Vert\; v_{i-1} \Vert\;^2 \ge \frac{3}{4} \Vert\; v_{i-1}^* \Vert\;^2 \)
\( \displaystyle \Vert\; v_i^* \Vert\;^2 \ge (\frac{3}{4}-\mu_{i,i-1}^2)\Vert\; v_{i-1}^* \Vert\;^2 \)


先來看LLL方法的簡略介紹，先掌握演算法的重點。
1.
Apply Gram-Schmidt orthogonalization to \( v_1,v_2,\ldots,v_m \).
Compute \( v_1^* , v_2^*, \ldots,v_m^* \), and the coefficients \( \mu_{i,j} \).
計算Gram-Schmidt正交化後的\( v_i^* \)和\( \mu_{i,j} \)。
2.
(Size-reduction) Apply \( v_i←v_i-round(\mu_{i,j})v_j \) to all pairs of distinct \( v_i \) and \( v_j \).
Update the Gram-Schmidt coefficients \( \mu_{i,j} \) appropriately.
將較長向量(\( v_i \))減掉某個倍數(\( round(\mu_{i,j}) \))的較短向量(\( v_j \))，減完後的(\( v_i \))長度會比(\( v_j \))來得更短。
因為\( v_i \)向量有更動，所以和i有關的\( \mu_{i,j} \)也要一併更新。
3.
(Lovász condition) If \( \displaystyle \Vert\; v_k^* \Vert\;^2 \ge (\delta-\mu_{k,k-1}^2 )\Vert\; v_{k-1}^* \Vert\;^2 \) fails for some pair \( v_k^* \) and \( v_{k-1}^* \),
swap \( v_k \) and \( v_{k-1} \), update the Gram-Schmidt coefficients and go back to step 2.
相鄰\( v_k^* \)和\( v_{k-1}^* \)若不符合Lovász condition，則將\( v_k \)和\( v_{k-1} \)互換位置
因為\( v_k \)和\( v_{k-1} \)向量有更動，所以和\( k,k-1 \)有關的\( \mu \)值也要一併更新。
再回到步驟2重新計算Size-reduction
[url]http://home.ie.cuhk.edu.hk/~wkshum/wordpress/?p=442[/url]


我再將matlab的程式碼改成maxima，但要注意的是matlab程式是以行向量來處理
\( \left[ \matrix{1 & 9 & 1 & 2 \cr 1 & 8 & 8 & 3 \cr 7 & 4 & 5 & 1 \cr 2 & 6 & 7 & 1} \right] \)，四個行向量為\( \left[ \matrix{1 \cr 1 \cr 7 \cr 2} \right] \)、\( \left[ \matrix{9 \cr 8 \cr 4 \cr 6} \right] \)、\( \left[ \matrix{1 \cr 8 \cr 5 \cr 7} \right] \)、\( \left[ \matrix{2 \cr 3 \cr 1 \cr 1} \right] \)。
但我用maxima改寫時用列向量程式碼比較簡單，所以網友在使用時要特別注意。
\( \left[ \matrix{1 & 1 & 7 & 2 \cr 9 & 8 & 4 & 6 \cr 1 & 8 & 5 & 7 \cr 2 & 3 & 1 & 1} \right] \)，四個列向量為\( \left[ \matrix{1 & 1 & 7 & 2} \right] \)、\( \left[ \matrix{9 & 8 & 4 & 6} \right] \)、\( \left[ \matrix{1 & 8 & 5 & 7} \right] \)、\( \left[ \matrix{2 & 3 & 1 & 1} \right] \)


[color=red](%i1)[/color]
[color=blue]LLL(v):=block
  (vstar:copymatrix(v),
   m:length(v),
   mu:zeromatrix(m,m),
   for i:1 thru m do
     (for j:1 thru i do
        (mu[ i ][j]:v[ i ].vstar[j]/vstar[j].vstar[j],
         vstar[ i ]:v[ i ]-sum(mu[ i ][j]*vstar[j],j,1,i-1)
        )
     ),
   k:2,
   while k<=m do
     (for i:k-1 thru 1 step -1 do
        (q:round(mu[k][ i ]),
         if q#0 then
           (v:rowop(v,k,i,q),
            mu:rowop(mu,k,i,q)
           )
        ),
      if (vstar[k].vstar[k])>=(3/4-mu[k][k-1]^2)*(vstar[k-1].vstar[k-1]) then
        (k:k+1
        )
      else
        (v:rowswap(v,k,k-1),
         vstar[1]:v[1],
         for i:1 thru m do
           (for j:1 thru i do
             (mu[ i ][j]:v[ i ].vstar[j]/vstar[j].vstar[j],
              vstar[ i ]:v[ i ]-sum(mu[ i ][j]*vstar[j],j,1,i-1)
             )
           ),
         if k>2 then
           (k:k-1
           )
        )
     ),
  return(v)
)$[/color]

[color=red](%i2)[/color]
[color=blue]v:matrix([1,1,7,2],
         [9,8,4,6],
         [1,8,5,7],
         [2,3,1,1]);[/color]
[color=red](%o2)[/color]　\( \left[ \matrix{1 & 1 & 7 & 2 \cr 9 & 8 & 4 & 6 \cr 1 & 8 & 5 & 7 \cr 2 & 3 & 1 & 1} \right] \)

[color=red](%i3)[/color]　[color=blue]LLL(v);[/color]
[color=red](%o3)[/color]　\( \left[ \matrix{2 & 3 & 1 & 1 \cr 3 & -1 & 1 & 3 \cr -2 & 2 & 6 & -1 \cr -4 & 1 & -4 & 3} \right] \)


--------------------------------------------------------------------------
103.6.3補充
在Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications這本書中第77頁的例子
Example 4.25. Let L be the 6-dimensional lattice in \( R^9 \) whose original basis consists of the row \( x_1,x_2,\ldots,x_6 \) of the matrix X:
$$ X=\left[ \matrix{4 & 9 & 3 & -5 & -5 & -1 & 7 & -1 & -5 \cr -2 & -8 & -7 & -1 & -3 & 6 & -3 & 9 & 8 \cr 1 & -3 & -2 & 3 & 9 & 7 & 2 & 7 & -2 \cr -5 & 6 & 4 & -2 & -2 & -7 & -2 & -9 & 1 \cr 1 & -2 & -2 & 7 & 7 & -3 & -9 & -5 & -4 \cr 7 & 1 & -4 & 3 & -2 & 9 & 9 & 7 & 6} \right] $$
The squared lengths of thease original basis vectors are 232, 317, 210, 220, 238, 326.
The LLL algorithm with \( \alpha=1 \) performs the 25 reduce and exchange steps summarized in Figure 4.5. The final basis consists of the rows \( y_1,y_2,\ldots,y_6 \) of the matrix Y：
$$ Y=\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 1 & 9 & -4 & 3 & 2 & 4 & 2 & -1 & 5 \cr 2 & -5 & 2 & 1 & 3 & 5 & 7 & 6 & 0 \cr 3 & 11 & -1 & -3 & 1 & 1 & 2 & 0 & -7} \right] $$
The squared lengths of these reduced basis vectors are 84, 87, 131, 157, 153, 195.
This is an especially impressive example of the power of the LLL algorithm: the longest reduced vector is shorter than the shortest original vector.


請把上面程式碼的3/4改為1，再執行
[color=red](%i4)[/color]
[color=blue]v: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](%o4)[/color]　\( \left[ \matrix{4 & 9 & 3 & -5 & -5 & -1 & 7 & -1 & -5 \cr -2 & -8 & -7 & -1 & -3 & 6 & -3 & 9 & 8 \cr 1 & -3 & -2 & 3 & 9 & 7 & 2 & 7 & -2 \cr -5 & 6 & 4 & -2 & -2 & -7 & -2 & -9 & 1 \cr 1 & -2 & -2 & 7 & 7 & -3 & -9 & -5 & -4 \cr 7 & 1 & -4 & 3 & -2 & 9 & 9 & 7 & 6} \right] \)

[color=red](%i5)[/color]　[color=blue]LLL(v);[/color]
[color=red](%o5)[/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 1 & 9 & -4 & 3 & 2 & 4 & 2 & -1 & 5 \cr 2 & -5 & 2 & 1 & 3 & 5 & 7 & 6 & 0 \cr 3 & 11 & -1 & -3 & 1 & 1 & 2 & 0 & -7} \right] \)

[[i] 本帖最後由 bugmens 於 2014-10-14 10:42 PM 編輯 [/i]]

bugmens 發表於 2014-6-2 18:10

上一篇程式碼我再加入許多print指令，將中間運算的過程印出來，整個演算法簡單講就是檢查有沒有符合Size condition，沒有符合的就向量相減，讓向量長度更短一點，再檢查有沒有符合Lovász condition，沒有符合的就將較短的向量上移一列，就像氣泡排序法會將數字小的往上移，而LLL演算法執行結果第一列就是整個lattice中長度較短的向量。
此次三維lattice的範例我取自wiki，維度較小所需要的步驟比較少，另外四維lattice你可以執行看看，執行的步驟就多很多。
[url]http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm[/url]
\( \left[ \matrix{1 & 1 & 1 \cr -1 & 0 & 2 \cr 3 & 5 & 6} \right] \)，各列向量長度\( \matrix{\sqrt{1^2+1^2+1^2}=\sqrt{3} \cr \sqrt{(-1)^2+0^2+2^2}=\sqrt{5} \cr \sqrt{3^2+5^2+6^2}=\sqrt{70}} \)
LLL化簡後的向量長度的確變短了
\( \left[ \matrix{0 & 1 & 0 \cr 1 & 0 & 1 \cr -1 & 0 & 2} \right] \)，各列向量長度\( \matrix{\sqrt{0^2+1^2+0^2}=1 \cr \sqrt{1^2+0^2+1^2}=\sqrt{2} \cr \sqrt{(-1)^2+0^2+2^2}=\sqrt{5}} \)

\( \left[ \matrix{1 & 1 & 7 & 2 \cr 9 & 8 & 4 & 6 \cr 1 & 8 & 5 & 7 \cr 2 & 3 & 1 & 1} \right] \)，各列向量長度\( \matrix{\sqrt{1^2+1^2+7^2+2^2}=\sqrt{55} \cr \sqrt{9^2+8^2+4^2+6^2}=\sqrt{197} \cr \sqrt{1^2+8^2+5^2+7^2}=\sqrt{139} \cr \sqrt{2^2+3^2+1^2+1^2}=\sqrt{15}} \)
LLL化簡後的向量長度的確變短了
\( \left[ \matrix{2 & 3 & 1 &1 \cr 3 & -1 & 1 & 3 \cr -2 & 2 & 6 & -1 \cr -4 & 1 & -4 & 3} \right] \)，各列向量長度\( \matrix{\sqrt{2^2+3^2+1^2+1^2}=\sqrt{15} \cr \sqrt{3^2+(-1)^2+1^2+3^2}=\sqrt{20} \cr \sqrt{(-2)^2+2^2+6^2+(-1)^2}=\sqrt{45} \cr \sqrt{(-4)^2+1^2+(-4)^2+3^2}=\sqrt{42}} \)
Lovász condition還和\( \mu \)有關，相鄰的向量有可能比較長的排上面(\( \sqrt{45} \))，比較短的向量排下面(\( \sqrt{42} \))。



[color=red](%i1)[/color]
[color=blue]LLL(v):=block
  (vstar:copymatrix(v),
   m:length(v),
   mu:zeromatrix(m,m),
   for i:1 thru m do
     (for j:1 thru i do
        (mu[ i ][j]:v[ i ].vstar[j]/vstar[j].vstar[j],
         vstar[ i ]:v[ i ]-sum(mu[ i ][j]*vstar[j],j,1,i-1)
        )
     ),
   print("Gram-Schmidt正交化  μ=",mu,"    v*=",vstar),
   k:2,
   while k<=m do
     (for i:k-1 thru 1 step -1 do
        (q:round(mu[k][ i ]),
         if q#0 then
           (print("round(μ[",k,"][",i,"])=",round(mu[k][ i ]),"違反Size condition"),
            print("v=",v,"  第",k,"列-",q,"*第",i,"列  v=",rowop(v,k,i,q)),
            v:rowop(v,k,i,q),
            print("μ=",mu,"  第",k,"列-",q,"*第",i,"列  μ=",rowop(mu,k,i,q)),
            mu:rowop(mu,k,i,q)
           )
        ),
      if (vstar[k].vstar[k])>=(3/4-mu[k][k-1]^2)*(vstar[k-1].vstar[k-1]) then
        (print("Lovasz condition成立,換下一列  k值",k,"=>",k+1),
         k:k+1
        )
      else
        (print("第",k-1,"列和第",k,"列違反Lovasz condition"),
         print("v=",v,"  第",k,"列和",k-1,"列交換  v=",rowswap(v,k,k-1)),
         v:rowswap(v,k,k-1),
         vstar[1]:v[1],
         for i:1 thru m do
           (for j:1 thru i do
             (mu[ i ][j]:v[ i ].vstar[j]/vstar[j].vstar[j],
              vstar[ i ]:v[ i ]-sum(mu[ i ][j]*vstar[j],j,1,i-1)
             )
           ),
         print("更新μ=",mu,"    v*=",vstar),
         if k>2 then
           (print("退回上一列  k值",k,"=>",k-1),
            k:k-1
           )
        )
     ),
  print("結束,結果v=",v)
)$[/color]
[color=red](%i2)[/color]
[color=blue]LLL(matrix([1,1,1],
           [-1,0,2],
           [3,5,6]));[/color]
Gram-Schmidt正交化  \( \mu=\left[ \matrix{1 & 0 & 0 \cr \frac{1}{3} & 1 & 0 \cr \frac{14}{3} & \frac{13}{14} & 1} \right] \)  \( v^{*}=\left[ \matrix{1 & 1 & 1 \cr -\frac{4}{3} & -\frac{1}{3} & \frac{5}{3} \cr -\frac{3}{7} & \frac{9}{14} & -\frac{3}{14}} \right] \)

Lovasz condition成立,換下一列  k值2=>3
round(μ[3][2])=1違反Size condition
\( v=\left[ \matrix{1 & 1 & 1 \cr -1 & 0 & 2 \cr 3 & 5 & 6} \right] \)  第3列-1*第2列  \( v=\left[ \matrix{1 & 1 & 1 \cr -1 & 0 & 2 \cr 4 & 5 & 4} \right] \)
\( \mu=\left[ \matrix{1 & 0 & 0 \cr \frac{1}{3} & 1 & 0 \cr \frac{14}{3} & \frac{13}{14} & 1} \right] \)  第3列-1*第2列  \( \mu=\left[ \matrix{1 & 0 & 0 \cr \frac{1}{3} & 1 & 0 \cr \frac{13}{3} & -\frac{1}{14} & 1} \right] \)

round(μ[3][1])=4違反Size condition
\( v=\left[ \matrix{1 & 1 & 1 \cr -1 & 0 & 2 \cr 4 & 5 & 4} \right] \)  第3列-4*第1列  \( v=\left[ \matrix{1 & 1 & 1 \cr -1 & 0 & 2 \cr 0 & 1 & 0} \right] \)
\( \displaystyle \mu=\left[ \matrix{1 & 0 & 0 \cr \frac{1}{3} & 1 & 0 \cr \frac{13}{3} & -\frac{1}{14} & 1} \right] \)  第3列-4*第1列  \( \displaystyle \mu=\left[ \matrix{1 & 0 & 0 \cr \frac{1}{3} & 1 & 0 \cr \frac{1}{3} & -\frac{1}{14} & 1} \right] \)

第2列和第3列違反Lovasz condition
\( v=\left[ \matrix{1 & 1 & 1 \cr -1 & 0 & 2 \cr 0 & 1 & 0} \right] \)  第3列和第2列交換  \( v=\left[ \matrix{1 & 1 & 1 \cr 0 & 1 & 0 \cr -1 & 0 & 2} \right] \)
更新\( \displaystyle \mu=\left[ \matrix{1 & 0 & 0 \cr \frac{1}{3} & 1 & 0 \cr \frac{1}{3} & -\frac{1}{2} & 1} \right] \)  \( \displaystyle v^{*}=\left[ \matrix{1 & 1 & 1 \cr -\frac{1}{3} & \frac{2}{3} & -\frac{1}{3} \cr -\frac{3}{2} & 0 & \frac{3}{2}} \right] \)
退回上一列  k值3=>2

第1列和第2列違反Lovasz condition
\( v=\left[ \matrix{1 & 1 & 1 \cr 0 & 1 & 0 \cr -1 & 0 & 2} \right] \)  第2列和第1列交換  \( v=\left[ \matrix{0 & 1 & 0 \cr 1 & 1 & 1 \cr -1 & 0 & 2} \right] \)
更新\( \displaystyle \mu=\left[ \matrix{1 & 0 & 0 \cr 1 & 1 & 0 \cr 0 & \frac{1}{2} & 1} \right] \)  \( v^{*}=\left[ \matrix{0 & 1 & 0 \cr 1 & 0 & 1 \cr -\frac{3}{2} & 0 & \frac{3}{2}} \right] \)

round(μ[2][1])=1違反Size condition
\( v=\left[ \matrix{0 & 1 & 0 \cr 1 & 1 & 1 \cr -1 & 0 & 2} \right] \)  第2列-1*第1列  \( v=\left[ \matrix{0 & 1 & 0 \cr 1 & 0 & 1 \cr -1 & 0 & 2} \right] \)
\( \displaystyle \mu=\left[ \matrix{1 & 0 & 0 \cr 1 & 1 & 0 \cr 0 & \frac{1}{2} & 1} \right] \)  第2列-1*第1列  \(  \displaystyle \mu=\left[ \matrix{1 & 0 & 0 \cr 0 & 1 & 0 \cr 0 & \frac{1}{2} & 1} \right] \)

Lovasz condition成立,換下一列  k值2=>3
Lovasz condition成立,換下一列  k值3=>4
結束,結果\( v=\left[ \matrix{0 & 1 & 0 \cr 1 & 0 & 1 \cr -1 & 0 & 2} \right] \)
[color=red](%o2)[/color]　\( \left[ \matrix{0 & 1 & 0 \cr 1 & 0 & 1 \cr -1 & 0 & 2} \right] \)

[color=green]四維的例子結果太長，就不列出來了[/color]
[color=red](%i3)[/color]
[color=blue]LLL(matrix([1,1,7,2],
           [9,8,4,6],
           [1,8,5,7],
           [2,3,1,1]));[/color]

[[i] 本帖最後由 bugmens 於 2014-10-14 10:52 PM 編輯 [/i]]

bugmens 發表於 2014-6-14 08:14

LLL演算法除了可以讓向量長度變得更短之外，任兩個向量也會變得更加垂直( \( \displaystyle \mu_{ij}<\frac{1}{2} \) )。
實務上常用Hadamard ratio來計算整個lattice的正交程度，定義如下

lattice的基底\( B=\{ v_1,v_2,\ldots,v_n \} \)，\( |\; det(B) |\; \)為\( v_1,v_2,\ldots,v_n \)的行列式值再加絕對值，\( \Vert v_i \Vert \)為向量\( v_i \)的歐幾里德長度。
\( \displaystyle H(B)=\left( \frac{|\; det(B) |\;}{\Vert v_1 \Vert \Vert v_2 \Vert \ldots \Vert v_n \Vert} \right)^{1/n} \)

\( 0<H(B) \le 1 \)，\( H(B) \)值越接近1代表基底B的正交程度越高，當\( H(B)=1 \)時，基底B的\( v_1,v_2,\ldots,v_n \)彼此正交。
(內容出自An Introduction to Mathematical Cryptography第373頁)


\( B= \left[ \matrix{1 & 1 & 1 \cr -1 & 0 & 2 \cr 3 & 5 & 6} \right] \)，行列式值\( \left| \matrix{1 & 1 & 1 \cr -1 & 0 & 2 \cr 3 & 5 & 6} \right| =-3 \)，\( \displaystyle H(B)=\left( \frac{\left| -3 \right|}{\sqrt{3}\cdot \sqrt{5}\cdot \sqrt{70}} \right)^{1/3}=0.45238570005998 \)
LLL化簡後的向量Hadamard ratio提高了
\( B= \left[ \matrix{0 & 1 & 0 \cr 1 & 0 & 1 \cr -1 & 0 & 2} \right] \)，行列式值\( \left| \matrix{0 & 1 & 0 \cr 1 & 0 & 1 \cr -1 & 0 & 2} \right| =-3 \)，\( \displaystyle H(B)=\left( \frac{\left| -3 \right|}{1 \cdot \sqrt{2} \cdot \sqrt{5}} \right)^{1/3}=0.98259319385269 \)

\( B= \left[ \matrix{1 & 1 & 7 & 2 \cr 9 & 8 & 4 & 6 \cr 1 & 8 & 5 & 7 \cr 2 & 3 & 1 & 1} \right] \)，行列式值\( \left| \matrix{1 & 1 & 7 & 2 \cr 9 & 8 & 4 & 6 \cr 1 & 8 & 5 & 7 \cr 2 & 3 & 1 & 1} \right| =-537 \)，\( \displaystyle H(B)=\left( \frac{\left| -537 \right|}{\sqrt{55} \cdot \sqrt{197} \cdot \sqrt{139} \cdot \sqrt{15}} \right)^{1/4}=0.57976460724516 \)
LLL化簡後的向量Hadamard ratio提高了
\( B= \left[ \matrix{2 & 3 & 1 & 1 \cr 3 & -1 & 1 & 3 \cr -2 & 2 & 6 & -1 \cr -4 & 1 & -4 & 3} \right] \)，行列式值\(  \left| \matrix{2 & 3 & 1 & 1 \cr 3 & -1 & 1 & 3 \cr -2 & 2 & 6 & -1 \cr -4 & 1 & -4 & 3} \right| =-537 \)，\( \displaystyle H(B)=\left( \frac{\left| -537 \right|}{\sqrt{15} \cdot \sqrt{20} \cdot \sqrt{45} \cdot \sqrt{42}} \right)^{1/4}=0.91895805542156 \)


[color=red](%i1)[/color]
[color=blue]HadamardRatio(B):=block
  (n:length(B),
   detB:abs(determinant(B)),
   norm:prod(sqrt(B[ i ].B[ i ]),i,1,n),
   float((detB/norm)^(1/n))
  )$[/color]

[color=red](%i2)[/color]
[color=blue]B:matrix([1,1,1],
         [-1,0,2],
         [3,5,6]);[/color]
[color=red](%o2)[/color]　\( \left[ \matrix{1 & 1 & 1 \cr -1 & 0 & 2 \cr 3 & 5 & 6} \right] \)

[color=red](%i3)[/color]　[color=blue]HadamardRatio(B);[/color]
[color=red](%o3)[/color]　0.45238570005998

[color=red](%i4)[/color]
[color=blue]B:matrix([0,1,0],
         [1,0,1],
         [-1,0,2]);[/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]HadamardRatio(B);[/color]
[color=red](%o5)[/color]　0.98259319385269

[color=red](%i6)[/color]
[color=blue]B:matrix([1,1,7,2],
         [9,8,4,6],
         [1,8,5,7],
         [2,3,1,1]);[/color]
[color=red](%o6)[/color]　\( \left[ \matrix{1 & 1 & 7 & 2 \cr 9 & 8 & 4 & 6 \cr 1 & 8 & 5 & 7 \cr 2 & 3 & 1 & 1} \right] \)

[color=red](%i7)[/color]　[color=blue]HadamardRatio(B);[/color]
[color=red](%o7)[/color]　0.57976460724516

[color=red](%i8)[/color]
[color=blue]B:matrix([2,3,1,1],
         [3,-1,1,3],
         [-2,2,6,-1],
         [-4,1,-4,3]);[/color]
[color=red](%o8)[/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](%i9)[/color]　[color=blue]HadamardRatio(B);[/color]
[color=red](%o9)[/color]　0.91895805542156




103.7.24補充
另一個常見的是Orthogonality defect，也是用來計算整個lattice的正交程度，定義如下

lattice的基底\( B=\{ v_1,v_2,\ldots,v_n \} \)，\( |\; det(B) |\; \)為\( v_1,v_2,\ldots,v_n \)的行列式值再加絕對值，\( \Vert v_i \Vert \)為向量\( v_i \)的歐幾里德長度。
\( \displaystyle O(B)=\frac{\Vert v_1 \Vert \Vert v_2 \Vert \ldots \Vert v_n \Vert}{|\; det(B) |\;} \)

\( O(B)\ge 1 \)，\( O(B) \)值越接近1代表基底B的正交程度越高，當\( O(B)=1 \)時，基底B的\( v_1,v_2,\ldots,v_n \)彼此正交。


\( B= \left[ \matrix{1 & 1 & 1 \cr -1 & 0 & 2 \cr 3 & 5 & 6} \right] \)，行列式值\( \left| \matrix{1 & 1 & 1 \cr -1 & 0 & 2 \cr 3 & 5 & 6} \right| =-3 \)，\( \displaystyle O(B)=\frac{\sqrt{3}\cdot \sqrt{5}\cdot \sqrt{70}}{\left| -3 \right|}=10.80123449734644 \)
LLL化簡後的向量Orthogonality defect降低了
\( B= \left[ \matrix{0 & 1 & 0 \cr 1 & 0 & 1 \cr -1 & 0 & 2} \right] \)，行列式值\( \left| \matrix{0 & 1 & 0 \cr 1 & 0 & 1 \cr -1 & 0 & 2} \right| =-3 \)，\( \displaystyle O(B)=\frac{1 \cdot \sqrt{2} \cdot \sqrt{5}}{\left| -3 \right|}=1.05409255338946 \)

\( B= \left[ \matrix{1 & 1 & 7 & 2 \cr 9 & 8 & 4 & 6 \cr 1 & 8 & 5 & 7 \cr 2 & 3 & 1 & 1} \right] \)，行列式值\( \left| \matrix{1 & 1 & 7 & 2 \cr 9 & 8 & 4 & 6 \cr 1 & 8 & 5 & 7 \cr 2 & 3 & 1 & 1} \right| =-537 \)，\( \displaystyle O(B)=\frac{\sqrt{55} \cdot \sqrt{197} \cdot \sqrt{139} \cdot \sqrt{15}}{\left| -537 \right|}=8.851017548063775 \)
LLL化簡後的向量Orthogonality defect降低了
\( B= \left[ \matrix{2 & 3 & 1 & 1 \cr 3 & -1 & 1 & 3 \cr -2 & 2 & 6 & -1 \cr -4 & 1 & -4 & 3} \right] \)，行列式值\(  \left| \matrix{2 & 3 & 1 & 1 \cr 3 & -1 & 1 & 3 \cr -2 & 2 & 6 & -1 \cr -4 & 1 & -4 & 3} \right| =-537 \)，\( \displaystyle O(B)=\frac{\sqrt{15} \cdot \sqrt{20} \cdot \sqrt{45} \cdot \sqrt{42}}{\left| -537 \right|}=1.402223508157669 \)


[color=red](%i1)[/color]
[color=blue]OrthogonalityDefect(B):=block
  (n:length(B),
   detB:abs(determinant(B)),
   norm:prod(sqrt(B[ i ].B[ i ]),i,1,n),
   float(norm/detB)
  )$[/color]

[color=red](%i2)[/color]
[color=blue]B:matrix([1,1,1],
         [-1,0,2],
         [3,5,6]);[/color]
[color=red](%o2)[/color]　\( \left[ \matrix{1 & 1 & 1 \cr -1 & 0 & 2 \cr 3 & 5 & 6} \right] \)

[color=red](%i3)[/color]　[color=blue]OrthogonalityDefect(B):[/color]
[color=red](%o3)[/color]　10.80123449734644

[color=red](%i4)[/color]
[color=blue]B:matrix([0,1,0],
         [1,0,1],
         [-1,0,2]);[/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]OrthogonalityDefect(B);[/color]
[color=red](%o5)[/color]　1.05409255338946

[color=red](%i6)[/color]
[color=blue]B:matrix([1,1,7,2],
         [9,8,4,6],
         [1,8,5,7],
         [2,3,1,1]);[/color]
[color=red](%o6)[/color]　\( \left[ \matrix{1 & 1 & 7 & 2 \cr 9 & 8 & 4 & 6 \cr 1 & 8 & 5 & 7 \cr 2 & 3 & 1 & 1} \right] \)

[color=red](%i7)[/color]　[color=blue]OrthogonalityDefect(B);[/color]
[color=red](%o7)[/color]　8.851017548063775

[color=red](%i8)[/color]
[color=blue]B:matrix([2,3,1,1],
         [3,-1,1,3],
         [-2,2,6,-1],
         [-4,1,-4,3]);[/color]
[color=red](%o8)[/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](%i9)[/color]　[color=blue]OrthogonalityDefect(B);[/color]
[color=red](%o9)[/color]　1.402223508157669



關於lattice和LLL的數學證明請自行查閱相關書籍，這裡只把重點放在maxima實作上。

LLL當初的論文
A.K. Lenstra, H.W. Lenstra, L. Lovasz :  Factoring polynomials with rational coefficients, Math. Ann. 261, 515–534 (1982).
[url]http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1982f/art.pdf[/url]
[url]http://www.math.elte.hu/~lovasz/scans/lll.pdf[/url]
[url]http://www.cs.cmu.edu/~avrim/451f11/lectures/lect1129_LLL.pdf[/url]

網路上下載得到的PDF檔
[url]http://www.math.brown.edu/~jhs/Presentations/WyomingLattices.pdf[/url]
[url]http://www.di.ens.fr/~pnguyen/SLIDES/SlidesLuminy2010.pdf[/url]
[url]http://www.di.ens.fr/~pnguyen/LCD/LCD_Opening.pdf[/url]

有介紹lattice和LLL的書
An Introduction to Mathematical Cryptography第6章
Lattice Basis Reduction第4章
LLL Algorithm Survey and Applications第2章

youtube影片
Winter School on Cryptography: Introduction to Lattices - Oded Regev
[url]https://www.youtube.com/watch?v=4ulHOV8iLls[/url]

[[i] 本帖最後由 bugmens 於 2014-7-24 10:29 PM 編輯 [/i]]

bugmens 發表於 2014-8-9 12:14

1.改進LLL方法－integral LLL

自從LLL被發表之後，許多學者就開始改進LLL方法，其中一個被稱為integral LLL。
以前面的例子來說，lattice　\( v=\left[ \matrix{1 & 1 & 1 \cr -1 & 0 & 2 \cr 3 & 5 & 6} \right] \)算出來的\( \mu \)和\( v* \)都有分數。
\( \mu=\left[ \matrix{1 & 0 & 0 \cr \frac{1}{3} & 1 & 0 \cr \frac{14}{3} & \frac{13}{14} & 1} \right] \)  \( v^{*}=\left[ \matrix{1 & 1 & 1 \cr -\frac{4}{3} & -\frac{1}{3} & \frac{5}{3} \cr -\frac{3}{7} & \frac{9}{14} & -\frac{3}{14}} \right] \)
一般實作時都是用浮點數表示分數，但經過許多次計算後可能會產生誤差。於是Weger在1986年提出integral LLL演算法，想法是將分母的值另外儲存起來\( \mu \)和\( v* \)只儲存分子。所以整體上和原本的LLL方法差不多，只有一些小地方略有修改。
[table=98%][tr][td]修改的部分[/td][td]原本的LLL[/td][td]integral LLL[/td][/tr]
[tr][td]Gram–Schmidt正交化[/td][td]for(i從1到m)
　{for(j從1到i)
　　{\( \displaystyle \mu_{ij}=\frac{v_i \cdot v_j^*}{v_j \cdot v_j} \)
　　 \( \displaystyle v_i=v_i-\sum_{j=1}^{i-1}\mu_{ij}\cdot v_j^* \)
　　}
　}


[/td]
[td]\( d_0=1 \)　//分母初始值是1
for(i從1到m)
　{for(j從1到i-1)
　　{\( \mu_{ij}=v_i \cdot v_j^* \)　//沒有除\( v_j \cdot v_j \)了
　　 \( \displaystyle v_{i}^*=\frac{d_j \cdot v_i^*-\mu_{ij}\cdot v_j^*}{d_{j-1}} \)
　　}
　 \( \mu_{ii}=v_{i}\cdot v_i^* \)
　 \( \displaystyle d_{i}=\frac{v_i^* \cdot v_i^*}{d_{i-1}} \)　//計算下一個分母
　}[/td][/tr]
[tr][td]Size condition[/td][td]\( \displaystyle |\; u_{ij} |\; \le \frac{1}{2} \)　\( 1 \le j<i \le n \)[/td][td]\( \displaystyle \Bigg\vert\; \frac{u_{ij}}{d_j} \Bigg\vert\; \le \frac{1}{2} \)　\( 1 \le j<i \le n \)[/td][/tr]
[tr][td]Lovász condition[/td][td]\( \displaystyle \Vert\; v_i^* \Vert\;^2 \ge (\frac{3}{4}-\mu_{i,i-1}^2)\Vert\; v_{i-1}^* \Vert\;^2 \)　\( 1<i \le n \)[/td][td]\( 4d_{i-2}\cdot d_{i} \ge 3d_{i-1}^2-4u_{i,i-1}^2 \)　\( 1<i \le n \)[/td][/tr]
[/table]


maxima程式碼有修改的地方我用紅色標示出來。
[color=red](%i1)[/color]
[color=blue]integralLLL(v):=block
  (vstar:copymatrix(v),
   m:length(v),
   mu:zeromatrix(m,m),[/color][color=red]
   array(d,m),
   d[0]:1,
   for i:1 thru m do
     (for j:1 thru i-1 do
        (mu[ i ][j]:v[ i ].vstar[j],
         vstar[ i ]: (d[j]*vstar[ i ]-mu[ i ][j]*vstar[j])/d[j-1]
        ),
      mu[ i ][ i ]:v[ i ].vstar[ i ],
      d[ i ]: (vstar[ i ].vstar[ i ])/d[i-1],
      print("v*第",i,"列分母為",d[i-1])
     ),[/color][color=blue]
   print("Gram-Schmidt正交化  μ=",mu,"    v*=",vstar),
   k:2,
   while k<=m do
     (for i:k-1 thru 1 step -1 do
        ([/color][color=red]q:round(mu[k][ i ]/d[ i ]),[/color][color=blue]
         if q#0 then
           (print("round(μ[",k,"][",i,"])=",mu[k][ i ],",分母=",d[ i ],"違反Size condition"),
            print("v=",v,"  第",k,"列-",q,"*第",i,"列  v=",rowop(v,k,i,q)),
            v:rowop(v,k,i,q),
            print("μ=",mu,"  第",k,"列-",q,"*第",i,"列  μ=",rowop(mu,k,i,q)),
            mu:rowop(mu,k,i,q)
           )
        ),[/color][color=red]
      if 4*d[k-2]*d[k]>=3*d[k-1]^2-4*mu[k][k-1]^2 then[/color][color=blue]
        (print("Lovasz condition成立,換下一列  k值",k,"=>",k+1),
         k:k+1
        )
      else
        (print("第",k-1,"列和第",k,"列違反Lovasz condition"),
         print("v=",v,"  第",k,"列和",k-1,"列交換  v=",rowswap(v,k,k-1)),
         v:rowswap(v,k,k-1),[/color][color=red]
         vstar[1]:v[1],
         for i:1 thru m do
           (for j:1 thru i-1 do
              (mu[ i ][j]:v[ i ].vstar[j],
               vstar[ i ]: (d[j]*vstar[ i ]-mu[ i ][j]*vstar[j])/d[j-1]
              ),
            mu[ i ][ i ]:v[ i ].vstar[ i ],
            d[ i ]: (vstar[ i ].vstar[ i ])/d[i-1],
            print("更新v*第",i,"列分母為",d[i-1])
           ),[/color][color=blue]
         print("更新μ=",mu,"    v*=",vstar),
         if k>2 then
           (print("退回上一列  k值",k,"=>",k-1),
            k:k-1
           )
        )
     ),
  print("結束,結果v=",v)
)$[/color]

[color=red](%i2)[/color]
[color=blue]integralLLL(matrix([1,1,1],
           [-1,0,2],
           [3,5,6]));[/color]
v*第1列分母為1
v*第2列分母為3
v*第3列分母為14
Gram-Schmidt正交化　\( \mu=\left[ \matrix{3 & 0 & 0\cr 1 & 14 & 0\cr 14 & 13 & 9} \right] \)　　\( v^*=\left[ \matrix{1 & 1 & 1\cr -4 & -1 & 5\cr -6 & 9 & -3} \right] \)

Lovasz condition成立,換下一列　k值2=>3
round(μ[3][2])=13,分母=14違反Size condition
\( v=\left[ \matrix{1 & 1 & 1\cr -1 & 0 & 2\cr 3 & 5 & 6} \right] \)　第3列-1*第2列　\( v=\left[ \matrix{1 & 1 & 1 \cr -1 & 0 & 2 \cr 4 & 5 & 4} \right] \)
\( \mu=\left[ \matrix{3 & 0 & 0 \cr 1 & 14 & 0 \cr 14 & 13 & 9} \right] \)　第3列-1*第2列　\( \mu=\left[ \matrix{3 & 0 & 0 \cr 1 & 14 & 0 \cr 13 & -1 & 9} \right] \)

round(μ[3][1])=13,分母=3違反Size condition
\( v=\left[ \matrix{1 & 1 & 1 \cr -1 & 0 & 2 \cr 4 & 5 & 4} \right] \)　第3列-4*第1列　\( v=\left[ \matrix{1 & 1 & 1\cr -1 & 0 & 2\cr 0 & 1 & 0} \right] \)
\( \mu=\left[ \matrix{3 & 0 & 0\cr 1 & 14 & 0 \cr 13 & -1 & 9} \right] \)　第3列-4*第1列　\( \mu=\left[ \matrix{3 & 0 & 0 \cr 1 & 14 & 0\cr 1 & -1 & 9} \right] \)

第2列和第3列違反Lovasz condition
\( v=\left[ \matrix{1 & 1 & 1 \cr -1 & 0 & 2 \cr 0 & 1 & 0} \right] \)　第3列和第2列交換　\( v=\left[ \matrix{1 & 1 & 1\cr 0 & 1 & 0\cr -1 & 0 & 2} \right] \)

更新v*第1列分母為1
更新v*第2列分母為3
更新v*第3列分母為2
更新\( \mu=\left[ \matrix{3 & 0 & 0\cr 1 & 2 & 0\cr 1 & -1 & 9} \right] \)　　\( v*=\left[ \matrix{1 & 1 & 1\cr -1 & 2 & -1\cr -3 & 0 & 3} \right] \)
退回上一列　k值3=>2

第1列和第2列違反Lovasz condition
\( v=\left[ \matrix{1 & 1 & 1\cr 0 & 1 & 0\cr -1 & 0 & 2} \right] \)　第2列和第1列交換　\( v=\left[ \matrix{0 & 1 & 0\cr 1 & 1 & 1\cr -1 & 0 & 2} \right] \)
更新v*第1列分母為1
更新v*第2列分母為1
更新v*第3列分母為2
更新\( \mu=\left[ \matrix{1 & 0 & 0\cr 1 & 2 & 0\cr 0 & 1 & 9} \right] \)　　\( v^*=\left[ \matrix{0 & 1 & 0\cr 1 & 0 & 1\cr -3 & 0 & 3} \right] \)

round(μ[2][1])=1違反Size condition
\( v=\left[ \matrix{0 & 1 & 0\cr 1 & 1 & 1\cr -1 & 0 & 2} \right] \)　第2列-1*第1列　\( v=\left[ \matrix{0 & 1 & 0\cr 1 & 0 & 1\cr -1 & 0 & 2} \right] \)
\( \mu=\left[ \matrix{1 & 0 & 0\cr 1 & 2 & 0\cr 0 & 1 & 9} \right] \)　第2列-1*第1列　\( \mu=\left[ \matrix{1 & 0 & 0\cr 0 & 2 & 0\cr 0 & 1 & 9} \right] \)

Lovasz condition成立,換下一列  k值2=>3
Lovasz condition成立,換下一列  k值3=>4

結束,結果\( v=\left[ \matrix{0 & 1 & 0\cr 1 & 0 & 1\cr -1 & 0 & 2} \right] \)
[color=red](%o2)[/color]　\( \left[ \matrix{0 & 1 & 0\cr 1 & 0 & 1\cr -1 & 0 & 2} \right] \)

[color=green]四維的例子結果太長，就不列出來了[/color]
[color=red](%i3)[/color]
[color=blue]integralLLL(matrix([1,1,7,2],
           [9,8,4,6],
           [1,8,5,7],
           [2,3,1,1]));[/color]


參考資料：
Weger, B.M.M. de (1987). Solving exponential diophantine equations using lattice basis reduction algorithms. Journal of Number Theory, 26(3), 325-367.
[url]http://www.sciencedirect.com/science/article/pii/0022314X87900886[/url]

Number-theoretic Algorithms in Cryptography第140頁
7.4. The Schnorr-Euchner algorithm and an integral LLL algorithm
原論文有的證明，這裡也有。
[url]http://books.google.com.tw/books?id=9A8e4u4TQaAC&lpg=PA136&ots=sfH1d8B5L7&dq=%22LLL%20REDUCED%20BASES%20AND%20THEIR%20PROPERTIES%22&hl=zh-TW&pg=PA140#v=onepage&q&f=false[/url]

[[i] 本帖最後由 bugmens 於 2014-10-14 11:12 PM 編輯 [/i]]

bugmens 發表於 2014-10-7 07:31

2.改進LLL方法－Deep Insertion LLL

原本的LLL只考慮相鄰的兩列向量( \( v_i^*、v_{i-1}^* \) )是否滿足Lovász condition( \( \displaystyle \Vert\; v_i^* \Vert\;^2 \ge (\frac{3}{4}-\mu_{i,i-1}^2)\Vert\; v_{i-1}^* \Vert\;^2 \) )，違反的話則將\( v_{k-1},v_k \)交換。而Deep Insertion則考慮兩個向量( \( \hat v_i^*、v_i^* \) )是否滿足deep exchange condition( \( \displaystyle \Vert\; \hat v_i^* \Vert\;^2 < \frac{3}{4} \Vert\; v_i^* \Vert\;^2 \) )，成立的話則將\( v_k \)向量插入\( v_i \)向量的位置。

先解釋什麼是\( \hat v_i^*、v_i^* \)
設lattice的向量為\( v_1,\ldots,v_{i-1},\color{blue}{v_i},v_{i+1},\ldots,v_{k-1},\color{blue}{v_k},v_{k+1},\ldots,v_n \)
Gram Schmidt正交化後第\( i \)個向量為\( v_i^* \)，向量長度的平方為\( \Vert\; v_i^* \Vert\;^2 \)
經deep insertion後將\( v_k \)向量插入\( v_i \)向量的位置\( v_1,\ldots,v_{i-1},\color{blue}{v_k},v_i,v_{i+1},\ldots,v_{k-1},v_{k+1},\ldots,v_n \)
Gram Schmidt正交化第\( i \)個向量為\( \displaystyle \hat v_i^*=v_k-\sum_{j=1}^{i-1} \mu_{k,j} v_j^* \)
移項後得到\( \displaystyle v_k=\hat v_i^*+\sum_{j=1}^{i-1}\mu_{k,j}v_j^* \)
平方求向量長度\( \displaystyle \Vert\; v_k \Vert\;^2=\Vert\; \hat v_i^* \Vert\;^2+\sum_{j=1}^{i-1}\mu_{k,j}^2 \Vert\; v_j^* \Vert\;^2 \)
再移項後得到\( \displaystyle \Vert\; \hat v_i^* \Vert\;^2=\Vert\; v_k \Vert\;^2-\sum_{j=1}^{i-1} \mu_{k,j}^2 \Vert\; v_j^* \Vert\;^2 \)
所以deep exchange condition是在比較插入前和插入後的Gram Schmidt正交化的向量長度，比較條件可以改成\( \displaystyle \Vert\; v_k \Vert\;^2-\sum_{j=1}^{i-1} \mu_{k,j}^2 \Vert\; v_j^* \Vert\;^2 < \frac{3}{4} \Vert\; v_i^* \Vert\;^2 \)。

之前兩個lattice( \( \left[ \matrix{1 & 1 & 1 \cr -1 & 0 & 2 \cr 3 & 5 & 6} \right] \)，\( \left[ \matrix{1 & 1 & 7 & 2 \cr 9 & 8 & 4 & 6 \cr 1 & 8 & 5 & 7 \cr 2 & 3 & 1 & 1} \right] \) )執行Deep Insertion LLL後的結果和原來的LLL相同。
於是我採用Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications在91頁的例子
\( \left[ \matrix{9 & 2 & 7 \cr 8 & 6 & 1 \cr 3 & 2 & 6} \right] \)
我將有Deep  Insertion的步驟特別寫出來，讓各位可以了解要插入的哪個位置。

第1次Deep  Insertion：
目前的\( \mu=\left[ \matrix{\displaystyle 1 & 0 & \cr -\frac{43}{134} & 1 & 0 \cr \frac{73}{134} & -\frac{1015}{5253} & 1} \right] \)，\( v^*=\left[ \matrix{\displaystyle 9 & 2 & 7 \cr \frac{253}{134} & \frac{311}{67} & -\frac{503}{134} \cr -\frac{8080}{5253} & \frac{9494}{5253} & \frac{7676}{5253}} \right] \)
\( v_2 \)可不可以插入\( v_1 \)位置？檢查\( \displaystyle \Vert\; v_2 \Vert\;^2 < \frac{3}{4} \Vert\; v_1^* \Vert\;^2 \)是否成立？
\( \displaystyle ((-1)^2+4^2+(-6)^2) < \frac{3}{4}(9^2+2^2+7^2) \)，\( 53<100.5 \)成立
\( v=\left[ \matrix{9 & 2 & 7 \cr -1 & 4 & -6 \cr 3 & 2 & 6} \right] \)，將\( v_2 \)插入\( v_1 \)位置，\( v=\left[ \matrix{-1 & 4 & -6 \cr 9 & 2 & 7 \cr 3 & 2 & 6} \right] \)

第2次Deep  Insertion：
目前的\( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr -\frac{43}{53} & 1 & 0 \cr \frac{22}{53} & \frac{2536}{5253} & 1} \right] \)，\( v^*=\left[ \matrix{\displaystyle -1 & 4 & -6 \cr \frac{434}{53} & \frac{278}{53} & \frac{113}{53} \cr -\frac{8080}{5253} & \frac{9494}{5253} & \frac{7676}{5253}} \right] \)
\( v_3 \)可不可以插入\( v_1 \)位置？檢查\( \displaystyle \Vert\; v_3 \Vert\;^2 < \frac{3}{4} \Vert\; v_1^* \Vert\;^2 \)是否成立？
\( \displaystyle (2^2+6^2+0^2) < \frac{3}{4}((-1)^2+4^2+(-6)^2) \)，\( 40<39.75 \)不成立，故\( v_3 \)不能插入\( v_1 \)位置。
\( v_3 \)可不可以插入\( v_2 \)位置？檢查\( \displaystyle \Vert\; v_3 \Vert\;^2-\mu_{3,1}^2 \Vert\; v_1^* \Vert\;^2 < \frac{3}{4} \Vert\; v_2^* \Vert\;^2 \)是否成立？
\( \displaystyle (2^2+6^2+0^2)-\left( \frac{22}{53} \right)^2((-1)^2+4^2+(-6)^2) < \frac{3}{4}\left( \left( \frac{434}{53} \right)^2+\left( \frac{278}{53} \right)^2+\left( \frac{113}{53} \right)^2 \right) \)，\( 30.87<74.33 \)成立
\( v=\left[ \matrix{-1 & 4 & -6 \cr 9 & 2 & 7 \cr 2 & 6 & 0} \right] \)，將\( v_3 \)插入\( v_2 \)位置，\( v=\left[ \matrix{-1 & 4 & -6 \cr 2 & 6 & 0 \cr 9 & 2 & 7} \right] \)

第3次Deep  Insertion：
目前的\( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{22}{53} & 1 & 0 \cr \frac{19}{53} & -\frac{184}{409} & 1} \right] \)，\( v^*=\left[ \matrix{\displaystyle -1 & 4 & -6 \cr \frac{128}{53} & \frac{230}{53} & \frac{132}{53} \cr \frac{1818}{409} & -\frac{606}{409} & -\frac{707}{409}} \right] \)
\( v_3 \)可不可以插入\( v_1 \)位置？檢查\( \displaystyle \Vert\; v_3 \Vert\;^2 < \frac{3}{4} \Vert\; v_1^* \Vert\;^2
\)是否成立？
\( \displaystyle (3^2+(-2)^2+(-5)^2) < \frac{3}{4}((-1)^2+4^2+(-6)^2) \)，\( 38<39.75 \)成立
\( v=\left[ \matrix{-1 & 4 & -6 \cr 2 & 6 & 0 \cr 3 & -2 & -5} \right] \)，將\( v_3 \)插入\( v_1 \)位置，\( v=\left[ \matrix{3 & -2 & -5 \cr -1 & 4 & -6 \cr 2 & 6 & 0} \right] \)

第4次Deep  Insertion：
目前的\( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{1}{2} & 1 & 0 \cr \frac{13}{38} & -\frac{37}{87} & 1} \right] \)，\( v^*=\left[ \matrix{\displaystyle 3 & -2 & -5 \cr -\frac{5}{2} & 5 & -\frac{7}{2} \cr \frac{6464}{1653} & \frac{4646}{1653} & \frac{2020}{1653}} \right] \)
\( v_3 \)可不可以插入\( v_1 \)位置？檢查\( \displaystyle \Vert\; v_3 \Vert\;^2 < \frac{3}{4} \Vert\; v_1^* \Vert\;^2 \)是否成立？
\( \displaystyle (6^2+0^2+1^2) < \frac{3}{4}(3^2+(-2)^2+(-5)^2) \)，\( 37<28.5 \)不成立，故\( v_3 \)不能插入\( v_1 \)位置。
\( v_3 \)可不可以插入\( v_2 \)位置？檢查\( \displaystyle \Vert\; v_3 \Vert\;^2-\mu_{3,1}^2 \Vert\; v_1^* \Vert\;^2 < \frac{3}{4} \Vert\; v_2^* \Vert\;^2 \)是否成立？
\( \displaystyle (6^2+0^2+1^2)-\left( \frac{6464}{1653} \right)^2(3^2+(-2)^2+(-5)^2) < \frac{3}{4}\left( \left( -\frac{5}{2} \right)^2+5^2+\left( -\frac{7}{2} \right)^2 \right) \)，\( -544.09<32.63 \)成立
\( v=\left[ \matrix{3 & -2 & -5 \cr -1 & 4 & -6 \cr 6 & 0 & 1} \right] \)，將\( v_3 \)插入\( v_2 \)位置，\( v=\left[ \matrix{3 & -2 & -5 \cr 6 & 0 & 1 \cr -1 & 4 & -6} \right] \)

當\( v_k \)向量插入某個\( v_i \)位置之後，Gram-Schmidt正交化的\( \mu \)值和\( v^* \)向量都會受到影響，在Lattice Basis Reduction書中第5.3節有提到如何更新這些值，想了解細節的網友可自行查閱，但在這裡為了方便，我重新計算整個Gram-Schmidt正交化。


maxima程式碼有修改的地方我用紅色標示出來。
[color=red](%i1)[/color]
[color=blue]DeepInsertionLLL(v):=block
  (vstar:copymatrix(v),
   m:length(v),
   mu:zeromatrix(m,m),
   for i:1 thru m do
     (for j:1 thru i do
        (mu[ i ][j]:v[ i ].vstar[j]/vstar[j].vstar[j],
         vstar[ i ]:v[ i ]-sum(mu[ i ][j]*vstar[j],j,1,i-1)
        )
     ),
   print("Gram-Schmidt正交化  μ=",mu,"    v*=",vstar),
   k:2,
   while k<=m do
     (for i:k-1 thru 1 step -1 do
        (q:round(mu[k][ i ]),
         if q#0 then
           (print("round(μ[",k,"][",i,"])=",round(mu[k][ i ]),"違反Size condition"),
            print("v=",v,"  第",k,"列-",q,"*第",i,"列  v=",rowop(v,k,i,q)),
            v:rowop(v,k,i,q),
            print("μ=",mu,"  第",k,"列-",q,"*第",i,"列  μ=",rowop(mu,k,i,q)),
            mu:rowop(mu,k,i,q)
           )
        ),[/color][color=red]
      i:1,
      C:v[k].v[k],
      startagain:false,
      while i<k and startagain=false do
        (ci:vstar[ i ].vstar[ i ],
         if C>=3/4*ci then
          (C:C-mu[k][ i ]^2*ci,
           i:i+1
          )
         else
          (tempv:copymatrix(v),
           for j:k step -1 thru i+1 do
             (v[j]:v[j-1]
             ),
           v[ i ]:tempv[k],
           startagain:true,
           print("deep exchange condition成立"),
           print("目前的μ=",mu,"    v*=",vstar),
           print("v=",tempv,"  第",k,"列插入第",i,"列  v=",v),
           print("k值",k,"=>",max(i-1,2)),
           k:max(i-1,2),[/color][color=blue]
           
           vstar[1]:v[1],
           for i:1 thru m do
             (for j:1 thru i do
               (mu[ i ][j]:v[ i ].vstar[j]/vstar[j].vstar[j],
                vstar[ i ]:v[ i ]-sum(mu[ i ][j]*vstar[j],j,1,i-1)
               )
             ),
           print("更新μ=",mu,"    v*=",vstar)
           )
         ),
      print("找不到可插入的位置,換下一列  k值",k,"=>",k+1),
      k:k+1
     ),
  return(v)
)$[/color]

[color=green]書上第一個例子[/color]
[color=red](%i2)[/color]
[color=blue]DeepInsertionLLL(matrix([9,2,7],
                        [8,6,1],
                        [3,2,6]));[/color]
Gram-Schmidt正交化  \( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{91}{134} & 1 & 0 \cr \frac{73}{134} & -\frac{1015}{5253} & 1}  \right] \)    \( v^*=\left[ \matrix{\displaystyle 9 & 2 & 7 \cr \frac{253}{134} & \frac{311}{67} & -\frac{503}{134} \cr -\frac{8080}{5253} & \frac{9494}{5253} & \frac{7676}{5253}} \right] \)

round(μ[2][1])=1違反Size condition
\( v=\left[ \matrix{9 & 2 & 7 \cr 8 & 6 & 1 \cr 3 & 2 & 6} \right] \)  第2列-1*第1列  \( v=\left[ \matrix{9 & 2 & 7 \cr -1 & 4 & -6 \cr 3 & 2 & 6} \right] \)
\( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{91}{134} & 1 & 0 \cr \frac{73}{134} & -\frac{1015}{5253} & 1} \right] \)  第2列-1*第1列  \( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr -\frac{43}{134} & 1 & 0 \cr \frac{73}{134} & -\frac{1015}{5253} & 1} \right] \)

deep exchange condition成立
目前的\( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr -\frac{43}{134} & 1 & 0 \cr \frac{73}{134} & -\frac{1015}{5253} & 1} \right] \)    \( v^*=\left[ \matrix{\displaystyle 9 & 2 & 7 \cr \frac{253}{134} & \frac{311}{67} & -\frac{503}{134} \cr -\frac{8080}{5253} & \frac{9494}{5253} & \frac{7676}{5253}} \right] \)
\( v=\left[ \matrix{9 & 2 & 7 \cr -1 & 4 & -6 \cr 3 & 2 & 6} \right] \)  第2列插入第1列  \( v=\left[ \matrix{-1 & 4 & -6 \cr 9 & 2 & 7 \cr 3 & 2 & 6} \right] \)
k值2 => 2
更新\( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr -\frac{43}{53} & 1 & 0 \cr -\frac{31}{53} & \frac{2536}{5253} & 1} \right] \)    \( v^*=\left[ \matrix{\displaystyle -1 & 4 & -6 \cr \frac{434}{53} & \frac{278}{53} & \frac{113}{53} \cr -\frac{8080}{5253} & \frac{9494}{5253} & \frac{7676}{5253}} \right] \)

找不到可插入的位置,換下一列  k值2 => 3

round(μ[3][1])=-1違反Size condition
\( v=\left[ \matrix{-1 & 4 & -6 \cr 9 & 2 & 7 \cr 3 & 2 & 6} \right] \)  第3列- -1*第1列  \( v=\left[ \matrix{-1 & 4 & -6 \cr 9 & 2 & 7 \cr 2 & 6 & 0} \right] \)
\( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr -\frac{43}{53} & 1 & 0 \cr -\frac{31}{53} & \frac{2536}{5253} & 1} \right] \)  第3列- -1*第1列  \( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr -\frac{43}{53} & 1 & 0 \cr \frac{22}{53} & \frac{2536}{5253} & 1} \right] \)

deep exchange condition成立
目前的\( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr -\frac{43}{55} & 1 & 0 \cr \frac{22}{53} & \frac{2536}{5253} & 1} \right] \)    \( v^*=\left[ \matrix{\displaystyle -1 & 4 & -6 \cr \frac{434}{53} & \frac{278}{53} & \frac{113}{53} \cr -\frac{8080}{5253} & \frac{9494}{5253} & \frac{7676}{5253}} \right] \)
\( v=\left[ \matrix{-1 & 4 & -6 \cr 9 & 2 & 7 \cr 2 & 6 & 0} \right] \)    第3列插入第2列    \( v=\left[ \matrix{-1 & 4 & -6 \cr 2 & 6 & 0 \cr 9 & 2 & 7} \right] \)
k值3 => 2
更新\( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{22}{53} & 1 & 0 \cr -\frac{43}{53} & \frac{634}{409} & 1} \right] \)    \( v^*=\left[ \matrix{\displaystyle -1 & 4 & -6 \cr \frac{128}{53} & \frac{230}{53} & \frac{132}{53} \cr \frac{1818}{409} & -\frac{606}{409} & -\frac{707}{409}} \right] \)

找不到可插入的位置,換下一列  k值2 => 3

round(μ[3][2])=2違反Size condition
\( v=\left[ \matrix{-1 & 4 & -6 \cr 2 & 6 & 0 \cr 9 & 2 & 7} \right] \)    第3列-2*第2列    \( v=\left[ \matrix{-1 & 4 & -6 \cr 2 & 6 & 0 \cr 5 & -10 & 7} \right] \)
\( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{22}{53} & 1 & 0 \cr -\frac{43}{53} & \frac{634}{409} & 1} \right] \)    第3列-2*第2列    \( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{22}{53} & 1 & 0 \cr -\frac{87}{53} & -\frac{184}{409} & 1} \right] \)

round(μ[3][1])=-2違反Size condition
\( v=\left[ \matrix{-1 & 4 & -6 \cr 2 & 6 & 0 \cr 5 & -10 & 7} \right] \)    第3列- -2*第1列    \( v=\left[ \matrix{-1 & 4 & -6 \cr 2 & 6 & 0 \cr 3 & -2 & -5} \right] \)
\( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{22}{53} & 1 & 0 \cr -\frac{87}{53} & -\frac{184}{409} & 1} \right] \)    第3列- -2*第1列    \( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{22}{53} & 1 & 0 \cr \frac{19}{53} & -\frac{184}{409} & 1} \right] \)

deep exchange condition成立
目前的\( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{22}{53} & 1 & 0 \cr \frac{19}{53} & -\frac{184}{409} & 1} \right] \)    \( v^*=\left[ \matrix{\displaystyle -1 & 4 & -6 \cr \frac{128}{53} & \frac{230}{53} & \frac{132}{53} \cr \frac{1818}{409} & -\frac{606}{409} & -\frac{707}{409}} \right] \)
\( v=\left[ \matrix{-1 & 4 & -6 \cr 2 & 6 & 0 \cr 3 & -2 & -5} \right] \)    第3列插入第1列    \( v=\left[ \matrix{3 & -2 & -5 \cr -1 & 4 & -6 \cr 2 & 6 & 0} \right] \)
k值3 => 2
更新\( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{1}{2} & 1 & 0 \cr -\frac{3}{19} & \frac{50}{87} & 1} \right] \)    \( v^*=\left[ \matrix{\displaystyle 3 & -2 & -5 \cr -\frac{5}{2} & 5 & -\frac{7}{2} \cr \frac{6464}{1653} & \frac{4646}{1653} & \frac{2020}{1653}} \right] \)

找不到可插入的位置,換下一列  k值2 => 3

round(μ[3][2])=1違反Size condition
\( v=\left[ \matrix{3 & -2 & -5 \cr -1 & 4 & -6 \cr 2 & 6 & 0} \right] \)    第3列-1*第2列    \( v=\left[ \matrix{3 & -2 & -5 \cr -1 & 4 & -6 \cr 3 & 2 & 6} \right] \)
\( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{1}{2} & 1 & 0 \cr -\frac{3}{19} & \frac{50}{87} & 1} \right] \)    第3列-1*第2列    \( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{1}{2} & 1 & 0 \cr -\frac{25}{38} & -\frac{37}{87} & 1} \right] \)

round(μ[3][1])=-1違反Size condition
\( v=\left[ \matrix{3 & -2 & -5 \cr -1 & 4 & -6 \cr 3 & 2 & 6} \right] \)    第3列- -1*第1列    \( v=\left[ \matrix{3 & -2 & -5 \cr -1 & 4 & -6 \cr 6 & 0 & 1} \right] \)
\( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{1}{2} & 1 & 0 \cr -\frac{25}{38} & -\frac{37}{87} & 1} \right] \)    第3列- -1*第1列    \( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{1}{2} & 1 & 0 \cr \frac{13}{38} & -\frac{37}{87} & 1} \right] \)

deep exchange condition成立
目前的\( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{1}{2} & 1 & 0 \cr \frac{13}{38} & -\frac{37}{87} & 1} \right] \)    \( v^*=\left[ \matrix{\displaystyle 3 & -2 & -5 \cr -\frac{5}{2} & 5 & -\frac{7}{2} \cr \frac{6464}{1653} & \frac{4646}{1653} & \frac{2020}{1653}} \right] \)
\( v=\left[ \matrix{3 & -2 & -5 \cr -1 & 4 & -6 \cr 6 & 0 & 1} \right] \)    第3列插入第2列    \( v=\left[ \matrix{3 & -2 & -5 \cr 6 & 0 & 1 \cr -1 & 4 & -6} \right] \)
k值3 => 2
更新\(\ \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{13}{38} & 1 & 0 \cr \frac{1}{2} & -\frac{703}{1237} & 1} \right] \)    \( v^*=\left[ \matrix{\displaystyle 3 & -2 & -5 \cr \frac{189}{38} & \frac{13}{19} & \frac{103}{38} \cr \frac{404}{1237} & \frac{6666}{1237} & -\frac{2424}{1237}} \right] \)

找不到可插入的位置,換下一列  k值2 => 3

round(μ[3][2])=-1違反Size condition
\( v=\left[ \matrix{3 & -2 & -5 \cr 6 & 0 & 1 \cr -1 & 4 & -6} \right] \)    第3列- -1*第2列    \( v=\left[ \matrix{3 & -2 & -5 \cr 6 & 0 & 1 \cr 5 & 4 & -5} \right] \)
\( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{13}{38} & 1 & 0 \cr \frac{1}{2} & -\frac{703}{1237} & 1} \right] \)    第3列- -1*第2列    \( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{13}{38} & 1 & 0 \cr \frac{16}{19} & \frac{534}{1237} & 1} \right] \)

round(μ[3][1])=1違反Size condition
\( v=\left[ \matrix{3 & -2 & -5 \cr 6 & 0 & 1 \cr 5 & 4 & -5} \right] \)    第3列-1*第1列    \( v=\left[ \matrix{3 & -2 & -5 \cr 6 & 0 & 1 \cr 2 & 6 & 0} \right] \)
\( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{13}{38} & 1 & 0 \cr \frac{16}{19} & \frac{534}{1237} & 1} \right] \)    第3列-1*第1列    \( \mu=\left[ \matrix{\displaystyle 1 & 0 & 0 \cr \frac{13}{38} & 1 & 0 \cr -\frac{3}{19} & \frac{534}{1237} & 1} \right] \)

找不到可插入的位置,換下一列  k值3 => 4
[color=red](%o2)[/color]　\( \left[ \matrix{3 & -2 & -5 \cr 6 & 0 & 1 \cr 2 & 6 & 0} \right] \)

[color=green]書上第二個例子[/color]
[color=red](%i3)[/color]
[color=blue]DeepInsertionLLL(matrix([83,29,21],
                        [99,45,96],
                        [2,65,31]));[/color]

[color=green]書上第三個例子[/color]
[color=red](%i4)[/color]
[color=blue]DeepInsertionLLL(matrix([-270,983,-834],
                        [-725,-979,143],
                        [929,-612,-27]));[/color]

[color=green]書上第四個例子[/color]
[color=red](%i5)[/color]
[color=blue]DeepInsertionLLL(matrix([84,3,34,17],
                        [20,48,66,19],
                        [69,14,63,78],
                        [28,72,36,57]));[/color]



書上第一個例子：\( \left[ \matrix{9 & 2 & 7 \cr 8 & 6 & 1 \cr 3 & 2 & 6} \right] \)
原本的LLL的結果為\( \left[ \matrix{-1 & 4 & -6 \cr 2 & 6 & 0 \cr 3 & -2 & -5} \right] \)，向量長度\( \matrix{\sqrt{(-1)^2+4^2+(-6)^2}=\sqrt{53} \cr \sqrt{2^2+6^2+0^2}=\sqrt{40} \cr \sqrt{3^2+(-2)^2+(-5)^2}=\color{blue}{\sqrt{38}}} \)

DeepInsertionLLL的結果為\( \left[ \matrix{3 & -2 & -5 \cr 6 & 0 & 1 \cr 2 & 6 & 0} \right] \)，向量長度\( \array{\sqrt{3^2+(-2)^2+(-5)^2}=\sqrt{38} \cr \sqrt{6^2+0^2+1^2}=\color{blue}{\sqrt{37}} \cr \sqrt{2^2+6^2+0^2}=\sqrt{40}} \)
原來長度較短的向量\( [3,-2,-5] \)又找到更短的向量\( [6,0,1] \)。


書上第二個例子：\( \left[ \matrix{83 & 29 & 21 \cr 99 & 45 & 96 \cr 2 & 65 & 31} \right] \)
原本的LLL的結果為\( \left[ \matrix{83 & 29 & 21 \cr 16 & 16 & 75 \cr 2 & 65 & 31} \right] \)，向量長度\( \array{\sqrt{83^2+29^2+21^2}=\sqrt{8171} \cr \sqrt{16^2+16^2+75^2}=\sqrt{6137} \cr \sqrt{2^2+65^2+31^2}=\color{blue}{\sqrt{5190}}} \)

DeepInsertionLLL的結果為\( \left[ \matrix{2 & 65 & 31 \cr 14 & -49 & 44 \cr 81 & -36 & -10} \right] \)，向量長度\( \matrix{\sqrt{2^2+65^2+31^2}=\sqrt{5190} \cr \sqrt{14^2+(-49)^2+44^2}=\color{blue}{\sqrt{4533}} \cr \sqrt{81^2+(-36)^2+(-10)^2}=\sqrt{7957}} \)
原來長度較短的向量\( [2,65,31] \)又找到更短的向量\( [14,-49,44] \)。


書上第三個例子：\( \left[ \matrix{-270 & 983 & -834 \cr -725 & -979 & 143 \cr 929 & -612 & -27} \right] \)
原本的LLL的結果為\( \left[ \matrix{-270 & 983 & -834 \cr -995 & 4 & -691 \cr 929 & -612 & -27} \right] \)，向量長度\( \matrix{\sqrt{(-270)^2+983^2+(-834)^2}=\sqrt{1734745} \cr \sqrt{(-995)^2+4^2+(-691)^2}=\sqrt{1467522} \cr \sqrt{929^2+(-612)^2+(-27)^2}=\color{blue}{\sqrt{1238314}}} \)

DeepInsertionLLL的結果為\( \left[ \matrix{-66 & -608 & -718 \cr 929 & -612 & -27 \cr 659 & 371 & -861} \right] \)，向量長度\( \matrix{\sqrt{(-66)^2+(-608)^2+(-718)^2}=\color{blue}{\sqrt{889544}} \cr \sqrt{929^2+(-612)^2+(-27)^2}=\sqrt{1238314} \cr \sqrt{659^2+371^2+(-861)^2}=\sqrt{1313243}} \)
原來長度較短的向量\( [929,-612,-27] \)又找到更短的向量\( [-66,-608,-718] \)。


書上第四個例子：\( \left[ \matrix{84 & 3 & 34 & 17 \cr 20 & 48 & 66 & 19 \cr 69 & 14 & 63 & 78 \cr 28 & 72 & 36 & 57} \right] \)
原本的LLL的結果為\( \left[ \matrix{84 & 3 & 34 & 17 \cr -64 & 45 & 32 & 2 \cr -35 & -37 & -37 & 42 \cr 43 & 61 & 7 & -4} \right] \)，向量長度\( \matrix{\sqrt{84^2+3^2+34^2+17^2}=\sqrt{8510} \cr \sqrt{(-64)^2+45^2+32^2+2^2}=\sqrt{7149} \cr \sqrt{(-35)^2+(-37)^2+(-37)^2+42^2}=\sqrt{5727} \cr \sqrt{43^2+61^2+7^2+(-4)^2}=\color{blue}{\sqrt{5635}}} \)

DeepInsertionLLL的結果為\( \left[ \matrix{8 & 24 & -30 & 38 \cr -35 & -37 & -37 & 42 \cr -23 & -13 & 59 & 23 \cr 41 & -58 & 27 & 21} \right] \)，向量長度\( \matrix{\sqrt{8^2+24^2+(-30)^2+38^2}=\color{blue}{\sqrt{2984}} \cr \sqrt{(-35)^2+(-37)^2+(-37)^2+42^2}=\sqrt{5727} \cr \sqrt{(-23)^2+(-13)^2+59^2+23^2}=\sqrt{4708} \cr \sqrt{41^2+(-58)^2+27^2+21^2}=\sqrt{6215}} \)
原來長度較短的向量\( [43,61,7,-4] \)又找到更短的向量\( [8,24,-30,38] \)。



參考資料
C. P. Schnorr , M. Euchner, Lattice basis reduction: improved practical algorithms and solving subset sum problems, Mathematical Programming: Series A and B, v.66 n.2, p.181-199, Sept. 7, 1994.

Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications.的第五章

原本的論文關於Deep Insertion只有一小段而已，但在Lattice Basis Reduction一書中則擴展成一章的內容，這篇文章的範例及程式碼就是參考這本書而來的。

bugmens 發表於 2015-5-20 22:56

3.改進LLL方法－modified LLL或MLLL

原本的LLL需要線性獨立的向量，若Lattice中有線性相依的向量，那在計算Gram Schmidt正交化時會發生錯誤，Pohst在1987年發表了modified
LLL演算法，就算有線性相依的向量也能處理。

maxima程式碼我參考Computation with finitely presented groups的第374頁的虛擬碼，只是我寫的maxima程式碼一直有錯誤，而我找不出錯誤在哪裡，所以我將我目前所寫的程式碼公布出來，看有沒有網友能幫我除錯。
[img]http://i.imgur.com/SSvY1dY.jpg[/img]

[img]http://i.imgur.com/WaQ9igH.jpg[/img]

[img]http://i.imgur.com/SQxczdv.jpg[/img]

[img]http://i.imgur.com/VppkVLG.jpg[/img]

[img]http://i.imgur.com/NOSa10e.jpg[/img]



[color=red](%i1)[/color]
[color=blue]ADJUST_MU(m,p):=block
(if abs(mu[m,p])>1/2 then
   (r:round(mu[m,p]),if mu[m,p]=-5/2 then r:-3,
    b[m]:b[m]-r*b[p],
    mu[m,p]:mu[m,p]-r,
    for j:1 thru p-1 do
      (mu[m,j]:mu[m,j]-r*mu[p,j])
   )
)$[/color]

[color=red](%i2)[/color]
[color=blue]MLLL(c):=block
([bstar,s,h,k,i,t,m,nu,B,C],
h:length(c[1]),
k:length(c),
mu:zeromatrix(k,k),
b:zeromatrix(k,k),
ZeroVector:create_list(0,i,1,h),
bstar:zeromatrix(k,h),
B:create_list(0,i,1,k),
b:c,
s:k,
i:1,
startagain:false,
while i<=s and startagain=false do
   (if b[ i ]=ZeroVector then
      (if i<s then ([b[ i ],b[s]]:[b[s],b[ i ]],                print(" P1",b)),
       s:s-1
      )
    else  /*b[ i ]不為零向量*/
      (bstar[ i ]:b[ i ],     print("i=",i,"b*[",i,"]=",bstar[ i ],"b*=",bstar),
       for j:1 thru i-1 do (mu[i,j]: (b[ i ].bstar[j])/B[j],  bstar[ i ]:bstar[ i ]-mu[i,j]*bstar[j] /*,print("i=",i,"j=",j,"mu=",mu,"b*=",bstar,"B=",B)*/),
       B[ i ]:bstar[ i ].bstar[ i ],
       if i=1 then
         (i:2)
       else  /*i>1*/
         (t:i,          m:i,
          while m<=t do
            (ADJUST_MU(m,m-1),               print(" P2",b),
             nu:mu[m,m-1],       C:B[m]+nu^2*B[m-1],
             if C>=3/4*B[m-1] then
               (for p:m-2 thru 1 step -1 do (ADJUST_MU(m,p),            print("P 3",b)),
                m:m+1
               )
             else
               (if b[m]=ZeroVector then
                  (if m<s then
                     ([b[m],b[s]]:[b[s],b[m]],  print("P 4",b)),
                   s:s-1,                   i:m,                   startagain:true
                  ),
                if C#0 then
                  (mu[m,m-1]:nu*B[m-1]/C,              B[m]:B[m-1]*B[m]/C,
                   for j:m+1 thru t do
                      (temp:matrix([1,mu[m,m-1]],[0,1]).matrix([0,1],[1,-nu]).matrix([mu[j,m-1]],[mu[j,m]]),
                       mu[j,m-1]:temp[1][1],               mu[j,m]:temp[2][1]
                      )
                  ),
                 B[m-1]:C,
                 [b[m-1],b[m]]:[b[m],b[m-1]], print("P 5",b),    print("m=",m,"t=",t,"B=",B,"bstar=",bstar,"mu=",mu),
                 if B[m-1]=0 then  (t:m-1),/*b1...bm-1是線性相依*/
                 for j:1 thru m-2 do ([mu[m-1,j],mu[m,j]]:[mu[m,j],mu[m-1,j]]),
                 bstar[m-1]:b[m-1],
                 for j:1 thru m-2 do (bstar[m-1]:bstar[m-1]-mu[m-1,j]*bstar[j]),
                 if m<=t then
                   (bstar[m]:b[m],
                    for j:1 thru m-1 do (bstar[m]:bstar[m]-mu[m,j]*bstar[j])
                   ),
                 print("b=",b,"m=",m,"t=",t,"B=",B,"bstar=",bstar,"mu=",mu),
                 if m>2 then (m:m-1)
               )/*C<3/4B[m-1]*/
            ),/*While m<=t */
            i:i+1
         )/* i>1 */
      )/* b[ i ]#0 */
   ),
return(b)
)$[/color]

[color=red](%i3)[/color]
[color=blue]c:matrix([4,-1],
             [5,4],
             [-2,-4])$
MLLL(c);[/color]

執行的結果和書上寫的不一樣









[table=50%][tr][td]\( b_1 \)[/td][td]\( b_2 \)[/td][td]\( b_3 \)[/td][td]Place[/td][/tr][tr][td]\( (4,-1) \)[/td][td]\( (5,4) \)[/td][td]\( (-2,-4) \)[/td][td][/td][/tr][tr][td]\( (4,-1) \)[/td][td]\( (1,5) \)[/td][td]\( (-2,-4) \)[/td][td]2[/td][/tr][tr][td]\( (4,-1) \)[/td][td]\( (1,5) \)[/td][td]\( (-1,1) \)[/td][td]2[/td][/tr][tr][td]\( (4,-1) \)[/td][td]\( (-1,1) \)[/td][td]\( (1,5) \)[/td][td]5[/td][/tr][tr][td]\( (-1,1) \)[/td][td]\( (4,-1) \)[/td][td]\( (1,5) \)[/td][td]5[/td][/tr][tr][td]\( (-1,1) \)[/td][td]\( (1,2) \)[/td][td]\( (1,5) \)[/td][td]2[/td][/tr][tr][td]\( (-1,1) \)[/td][td]\( (1,2) \)[/td][td]\( (-1,1) \)[/td][td]2[/td][/tr][tr][td]\( (-1,1) \)[/td][td]\( (-1,1) \)[/td][td]\( (1,2) \)[/td][td]5[/td][/tr][tr][td]\( (-1,1) \)[/td][td]\( (0,0) \)[/td][td]\( (1,2) \)[/td][td]2[/td][/tr][tr][td]\( (-1,1) \)[/td][td]\( (1,2) \)[/td][td]\( (0,0) \)[/td][td]4[/td][/tr][/table]



另外[url=http://www.numbertheory.org/calc/krm_calc.html]http://www.numbertheory.org/calc/krm_calc.html[/url]有calc的數學軟體
在[url=http://www.numbertheory.org/calc/]http://www.numbertheory.org/calc/[/url]下載calc_win32.exe，輸入以下指令(紅色文字)

                        CALC

                A NUMBER THEORY CALCULATOR
                K.R.MATTHEWS, 16th January 2015


Type exit to quit, help for information:
> [color=red]mlll()[/color]
Do you wish to use an existing matrix from a file? (Y/N)
Enter y or n : [color=red]n[/color]
enter the matrix of integers (first row non-zero) :
Enter the number of rows and number of columns
[color=red]3 2[/color]
Enter row 1:
[color=red]4 -1[/color]
Enter row 2:
[color=red]5 4[/color]
Enter row 3:
[color=red]-2 -4[/color]
The matrix entered is

4 -1
5  4
-2 -4
VERBOSE? (Y/N)
Enter y or n : [color=red]n[/color]
enter the parameters m1 and n1 (normally 1 and 1) :[color=red]1 1[/color]
L =
0 0 0
1 0 0
1 0 0
D[0] = 1, D[1] = 2, D[2] = 9, D[3] = 0,


The corresponding transformation matrix is
-1  1  1
-2  3  3
4 -6 -7
The corresponding reduced basis is
-1 1
1 2
>

程式輸出\( (-1,1),(1,2) \)結果是正確的但對除錯沒有太大的幫助。


參考資料
Computational Algebraic Number Theory
作者：Michael Pohst
[url=https://books.google.com.tw/books?id=Ar0bY3mN-7kC&pg=PA22&lpg=PA22&dq=%22mlll%22+lattice+reduction&source=bl&ots=Gf9g1sddWr&sig=Fs-8EunV5z8h1olTrE0obV1qjBM&hl=zh-TW&sa=X&ei=XM3cVNWNBZGk8AWXioDQCw&ved=0CEUQ6AEwBTgK#v=onepage&q=%22mlll%22%20lattice%20reduction&f=false]https://books.google.com.tw/book ... 20reduction&f=false[/url]

MLLL原始的論文
[url=http://www.researchgate.net/profile/Michael_Pohst/publication/220161104_A_Modification_of_the_LLL_Reduction_Algorithm/links/0c960529773c47f645000000.pdf]http://www.researchgate.net/prof ... 73c47f645000000.pdf[/url]

有MLLL演算法虛擬碼
[url=http://www.numbertheory.org/pdfs/mlll.pdf]http://www.numbertheory.org/pdfs/mlll.pdf[/url]

[[i] 本帖最後由 bugmens 於 2015-5-20 11:04 PM 編輯 [/i]]

bugmens 發表於 2015-6-20 08:24

4.改進LLL方法－遞迴LLL

原本LLL方法是針對整個Lattice進行LLL運算，而遞迴LLL一開始先對前兩個向量進行LLL運算，之後再加入第三個向量進行LLL運算...，每次都新增一個向量進行LLL運算直到整個Lattice都化簡為止。

範例出自[url]https://thomas-plantard.github.io/pdf/talk10-scn.pdf[/url]

[color=green]這個LLL副程式略有修改，參數\( m \)代表將第1~m列向量進行LLL運算。[/color]
[color=red](%i1)[/color]
[color=blue]LLL(v,m):=block
  (vstar:copymatrix(v),
   delta:3/4,
   mu:zeromatrix(m,m),
   for i:1 thru m do
     (for j:1 thru i do
        (mu[ i ][j]:v[ i ].vstar[j]/vstar[j].vstar[j],
         vstar[ i ]:v[ i ]-sum(mu[ i ][j]*vstar[j],j,1,i-1)
        )
     ),
   k:2,
   while k<=m do
     (for i:k-1 thru 1 step -1 do
        (q:round(mu[k][ i ]),
         if q#0 then
           (v:rowop(v,k,i,q),
            mu:rowop(mu,k,i,q)
           )
        ),
      if (vstar[k].vstar[k])>=(delta-mu[k][k-1]^2)*(vstar[k-1].vstar[k-1]) then
        (k:k+1
        )
      else
        (v:rowswap(v,k,k-1),
         vstar[1]:v[1],
         for i:1 thru m do
           (for j:1 thru i do
             (mu[ i ][j]:v[ i ].vstar[j]/vstar[j].vstar[j],
              vstar[ i ]:v[ i ]-sum(mu[ i ][j]*vstar[j],j,1,i-1)
             )
           ),
         if k>2 then
           (k:k-1
           )
        )
     ),
  return(v)
)$[/color]

[color=red](%i2)[/color]
[color=blue]B:matrix([1031,0,0,0,0],
         [354,1,0,0,0],
         [322,0,1,0,0],
         [916,0,0,1,0],
         [426,0,0,0,1]);[/color]
[color=red](%o2)[/color]　\( \left[ \matrix{1031 & 0 & 0 & 0 & 0 \cr 354 & 1 & 0 & 0 & 0 \cr 322 & 0 & 1 & 0 & 0 \cr 916 & 0 & 0 & 1 & 0 \cr 426 & 0 & 0 & 0 & 1} \right] \)

[color=red](%i3)[/color]
[color=blue]for i:2 thru length(B) do
  (B: LLL(B,i),
   print(B)
  );[/color]
\( \left[ \matrix{-31 & -3 & 0 & 0 & 0 \cr 13 & -32 & 0 & 0 & 0 \cr 322 & 0 & 1 & 0 & 0 \cr 916 & 0 & 0 & 1 & 0 \cr 426 & 0 & 0 & 0 & 1} \right] \)

\( \left[ \matrix{-1 & 2 & 1 & 0 & 0 \cr 0 & -6 & 13 & 0 & 0 \cr -27 & -11 & -4 & 0 & 0 \cr 916 & 0 & 0 & 1 & 0 \cr 426 & 0 & 0 & 0 & 1} \right] \)

\( \left[ \matrix{-1 & 2 & 1 & 0 & 0 \cr -4 & -3 & 4 & 2 & 0 \cr 4 & 0 & 5 & 5 & 0 \cr 0 & -3 & 4 & -7 & 0 \cr 426 & 0 & 0 & 0 & 1} \right] \)

\( \left[ \matrix{-1 & 2 & 1 & 0 & 0 \cr 0 & -2 & 2 & 1 & -2 \cr -2 & -2 & 3 & -3 & 1 \cr -2 & 1 & -1 & 4 & 1 \cr 3 & 0 & 3 & 0 & 5} \right] \)
[color=red](%o3)[/color]　[i]done[/i]

[color=green]另一個範例出自[url]http://www1.uwindsor.ca/sac2012/system/files/2a_Plantard.pdf[/url][/color]
[color=red](%i4)[/color]
[color=blue]B:matrix([86670401,0,0,0,0,0,0,0],
         [38009011,1,0,0,0,0,0,0],
         [10117311,0,1,0,0,0,0,0],
         [38269415,0,0,1,0,0,0,0],
         [45874978,0,0,0,1,0,0,0],
         [33538152,0,0,0,0,1,0,0],
         [61611560,0,0,0,0,0,1,0],
         [66174289,0,0,0,0,0,0,1]);[/color]
[color=red](%o4)[/color]　\( \left[\matrix{
86670401&0&0&0&0&0&0&0 \cr
38009011&1&0&0&0&0&0&0 \cr
10117311&0&1&0&0&0&0&0 \cr
38269415&0&0&1&0&0&0&0 \cr
45874978&0&0&0&1&0&0&0 \cr
33538152&0&0&0&0&1&0&0 \cr
61611560&0&0&0&0&0&1&0 \cr
66174289&0&0&0&0&0&0&1 }\right] \)

[color=red](%i5)[/color]
[color=blue]for i:2 thru length(B) do
  (B: LLL(B,i),
   print(B)
  );[/color]
\( \left[\matrix{
-3227&-3165&0&0&0&0&0&0 \cr
-14111&13018&0&0&0&0&0&0 \cr
10117311&0&1&0&0&0&0&0 \cr
38269415&0&0&1&0&0&0&0 \cr
45874979&0&0&0&1&0&0&0 \cr
33538154&0&0&0&0&1&0&0 \cr
61611560&0&0&0&0&0&1&0 \cr
66174289&0&0&0&0&0&0&1 }\right] \)

\( \left[\matrix{
-24&153&-215&0&0&0&0&0 \cr
183&242&76&0&0&0&0&0 \cr
-920&440&343&0&0&0&0&0 \cr
38266415&0&0&1&0&0&0&0 \cr
45874978&0&0&0&1&0&0&0 \cr
33538152&0&0&0&0&1&0&0 \cr
61611560&0&0&0&0&0&1&0 \cr
66174289&0&0&0&0&0&0&1 }\right] \)

\( \left[\matrix{
8&-27&-66&42&0&0&0&0 \cr
-40&-45&-47&-38&0&0&0&0 \cr
0&126&-18&-23&0&0&0&0 \cr
103&26&0&-53&0&0&0&0 \cr
45874978&0&0&0&1&0&0&0 \cr
33538152&0&0&0&0&1&0&0 \cr
61611560&0&0&0&0&0&1&0 \cr
66174289&0&0&0&0&0&0&1 }\right] \)

\( \left[\matrix{
-17&-31&-5&6&1&0&0&0 \cr
24&-20&-6&4&7&0&0&0 \cr
-3&-7&-45&3&17&0&0&0 \cr
8&4&-13&-14&-36&0&0&0 \cr
13&0&15&-35&24&0&0&0 \cr
33538152&0&0&0&0&1&0&0 \cr
61611560&0&0&0&0&0&1&0 \cr
66174289&0&0&0&0&0&0&1 }\right] \)

\( \left[\matrix{
-7&-6&-14&11&4&-7&0&0 \cr
-14&-9&-3&-1&-15&-6&0&0 \cr
-2&15&14&10&-6&4&0&0 \cr
8&-14&5&13&-14&-2&0&0 \cr
-5&11&-6&-10&-12&12&0&0 \cr
4&-16&12&-4&12&13&0&0 \cr
61611560&0&0&0&0&0&1&0 \cr
66174289&0&0&0&0&0&0&1 }\right] \)

\( \left[\matrix{
5&-4&-8&0&1&10&-1&0 \cr
9&-1&4&-6&-7&-8&2&0 \cr
1&-4&0&6&-12&-1&4&0 \cr
4&8&-4&9&4&0&-3&0 \cr
3&-2&-11&-4&-5&-3&-6&0 \cr
4&-9&-7&9&3&-2&7&0 \cr
7&-10&5&7&-2&-1&-4&0 \cr
66174289&0&0&0&0&0&0&1 }\right] \)

\( \left[\matrix{
-2&6&-1&-8&0&1&-3&1 \cr
2&-3&-8&1&3&-1&4&1 \cr
\color{red}{3}&\color{red}{0}&\color{red}{-3}&\color{red}{-5}&\color{red}{-3}&\color{red}{2}&\color{red}{5}&\color{red}{5} \cr
-2&-1&-6&4&-6&-3&0&-3 \cr
5&-4&4&-1&-2&0&-7&1 \cr
4&2&3&-1&-4&1&-1&-7 \cr
-2&3&-4&0&0&11&2&-2 \cr
5&11&1&3&-2&3&-2&4 }\right] \)
[color=red](%o5)[/color]　[i]done[/i]




執行結果第三列向量和pdf檔所寫的不一樣，我還以為我的LLL程式出了問題，我還另外用maple再寫一次來測試，結果是相同的。
[img]https://math.pro/db/attachment.php?aid=2953&k=9db2f7ab2b8b02bbfbce083b07de22e0&t=1434757468&noupdate=yes[/img]
maple檔下載[url=https://math.pro/db/attachment.php?aid=2952&k=3a2bd59d28fc019767fbe4d41a8d4723&t=1434757468]遞迴LLL1.rar[/url]
\( \left[\matrix{
-2&6&-1&-8&0&1&-3&1 \cr
2&-3&-8&1&3&-1&4&1 \cr
\color{red}{3}&\color{red}{0}&\color{red}{-3}&\color{red}{-5}&\color{red}{-3}&\color{red}{2}&\color{red}{5}&\color{red}{5} \cr
-2&-1&-6&4&-6&-3&0&-3 \cr
5&-4&4&-1&-2&0&-7&1 \cr
4&2&3&-1&-4&1&-1&-7 \cr
-2&3&-4&0&0&11&2&-2 \cr
5&11&1&3&-2&3&-2&4 }\right] \)\( \left[\matrix{
-2&6&-1&-8&0&1&-3&1 \cr
2&-3&-8&1&3&-1&4&1 \cr
\color{red}{3}&\color{red}{-3}&\color{red}{6}&\color{red}{2}&\color{red}{-6}&\color{red}{2}&\color{red}{4}&\color{red}{3} \cr
-2&-1&-6&4&-6&-3&0&-3 \cr
5&-4&4&-1&-2&0&-7&1 \cr
4&2&3&-1&-4&1&-1&-7 \cr
-2&3&-4&0&0&11&2&-2 \cr
5&11&1&3&-2&3&-2&4 }\right] \)





＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
在 [url]http://www1.uwindsor.ca/sac2012/system/files/2a_Plantard.pdf[/url] 還提到另外一種遞迴LLL方法，先將兩個向量為一組進行LLL運算，再以四個向量為一組進行LLL運算，再以八個向量為一組進行LLL運算…，直到全部的Lattice向量都化簡完為止。

[color=green]這個LLL副程式略有修改，參數\( m1,m2 \)代表將第m1~m2列向量進行LLL運算。[/color]
[color=red](%i1)[/color]
[color=blue]LLL(v,m1,m2):=block
  (vstar:copymatrix(v),
   delta:3/4,
   m:length(v),
   mu:zeromatrix(m,m),
   for i:m1 thru m2 do
     (for j:m1 thru i do
        (mu[ i ][j]:v[ i ].vstar[j]/vstar[j].vstar[j],
         vstar[ i ]:v[ i ]-sum(mu[ i ][j]*vstar[j],j,1,i-1)
        )
     ),
   k:m1+1,
   while k<=m2 do
     (for i:k-1 thru 1 step -1 do
        (q:round(mu[k][ i ]),
         if q#0 then
           (v:rowop(v,k,i,q),
            mu:rowop(mu,k,i,q)
           )
        ),
      if (vstar[k].vstar[k])>=(delta-mu[k][k-1]^2)*(vstar[k-1].vstar[k-1]) then
        (k:k+1
        )
      else
        (v:rowswap(v,k,k-1),
         vstar[m1]:v[m1],
         for i:m1 thru m2 do
           (for j:m1 thru i do
             (mu[ i ][j]:v[ i ].vstar[j]/vstar[j].vstar[j],
              vstar[ i ]:v[ i ]-sum(mu[ i ][j]*vstar[j],j,1,i-1)
             )
           ),
         if k>m1+1 then
           (k:k-1
           )
        )
     ),
  return(v)
)$[/color]

[color=red](%i2)[/color]
[color=blue]B:matrix([86670401,0,0,0,0,0,0,0],
         [38009011,1,0,0,0,0,0,0],
         [10117311,0,1,0,0,0,0,0],
         [38269415,0,0,1,0,0,0,0],
         [45874978,0,0,0,1,0,0,0],
         [33538152,0,0,0,0,1,0,0],
         [61611560,0,0,0,0,0,1,0],
         [66174289,0,0,0,0,0,0,1]);[/color]
[color=red](%o2)[/color]　\( \left[ \matrix{
86670401&0&0&0&0&0&0&0 \cr
38009011&1&0&0&0&0&0&0 \cr
10117311&0&1&0&0&0&0&0 \cr
38269415&0&0&1&0&0&0&0 \cr
45874978&0&0&0&1&0&0&0 \cr
33538152&0&0&0&0&1&0&0 \cr
61611560&0&0&0&0&0&1&0 \cr
66174289&0&0&0&0&0&0&1 } \right] \)

[color=red](%i3)[/color]
[color=blue]d:length(B)$
for i:1 thru ceiling(log(d)/log(2)) do
  (for j:1 thru ceiling(d/2^i) do
     (m1: (j-1)*2^i+1,
      m2:j*2^i,
      if m2>d then
        (m2:d),
      B: LLL(B,m1,m2),
      print("第",m1,"到",m2,"列向量進行LLL運算"),
      print(B)
     )
  );[/color]
第1到2列向量進行LLL運算
\( \left[ \matrix{
-3227&-3165&0&0&0&0&0&0 \cr
-14111&13018&0&0&0&0&0&0 \cr
10117311&0&1&0&0&0&0&0 \cr
38269415&0&0&1&0&0&0&0 \cr
45874978&0&0&0&1&0&0&0 \cr
33538152&0&0&0&0&1&0&0 \cr
61611560&0&0&0&0&0&1&0 \cr
66174289&0&0&0&0&0&0&1 } \right] \)

第3到4列向量進行LLL運算
\( \left[ \matrix{
-3227&-3165&0&0&0&0&0&0 \cr
-14111&13018&0&0&0&0&0&0 \cr
1391&0&4036&-1067&0&0&0&0 \cr
-8121&0&3949&-1044&0&0&0&0 \cr
45874978&0&0&0&1&0&0&0 \cr
33538152&0&0&0&0&1&0&0 \cr
61611560&0&0&0&0&0&1&0 \cr
66174289&0&0&0&0&0&0&1 } \right] \)

第5到6列向量進行LLL運算
\( \left[ \matrix{
-3227&-3165&0&0&0&0&0&0 \cr
-14111&13018&0&0&0&0&0&0 \cr
1391&0&4036&-1067&0&0&0&0 \cr
-8121&0&3949&-1044&0&0&0&0 \cr
1348&0&0&0&2830&-3871&0&0 \cr
10894&0&0&0&-2009&2748&0&0 \cr
61611560&0&0&0&0&0&1&0 \cr
66174289&0&0&0&0&0&0&1 } \right] \)

第7到8列向量進行LLL運算
\( \left[ \matrix{
-3227&-3165&0&0&0&0&0&0 \cr
-14111&13018&0&0&0&0&0&0 \cr
1391&0&4036&-1067&0&0&0&0 \cr
-8121&0&3949&-1044&0&0&0&0 \cr
1348&0&0&0&2830&-3871&0&0 \cr
10894&0&0&0&-2009&2748&0&0 \cr
3&0&0&0&0&0&2248&-2093 \cr
29437&0&0&0&0&0&29&-27 } \right] \)

第1到4列向量進行LLL運算
\( \left[ \matrix{
8&-27&-66&42&0&0&0&0 \cr
-40&-45&-47&-38&0&0&0&0 \cr
0&126&-18&-23&0&0&0&0 \cr
\color{red}{-103}&\color{red}{-26}&0&\color{red}{53}&0&0&0&0 \cr
1348&0&0&0&2830&-3871&0&0 \cr
10894&0&0&0&-2009&2748&0&0 \cr
3&0&0&0&0&0&2248&-2093 \cr
29437&0&0&0&0&0&29&-27 } \right] \)

第5到8列向量進行LLL運算
\( \left[ \matrix{
8&-27&-66&42&0&0&0&0 \cr
-40&-45&-47&-38&0&0&0&0 \cr
0&126&-18&-23&0&0&0&0 \cr
-103&-26&0&53&0&0&0&0 \cr
-22&0&0&0&-7&-19&-36&48 \cr
\color{red}{-93}&0&0&0&\color{red}{25}&\color{red}{2}&\color{red}{5}&\color{red}{-23} \cr
\color{red}{32}&0&0&0&\color{red}{97}&\color{red}{-13}&\color{red}{-63}&\color{red}{-2} \cr
\color{red}{-1}&0&0&0&\color{red}{25}&\color{red}{111}&\color{red}{-93}&\color{red}{13} } \right] \)

第1到8列向量進行LLL運算
\( \left[ \matrix{
\color{red}{-2}&\color{red}{3}&\color{red}{8}&\color{red}{-1}&\color{red}{-3}&\color{red}{1}&\color{red}{-4}&\color{red}{-1} \cr
\color{red}{-3}&\color{red}{0}&\color{red}{3}&\color{red}{5}&\color{red}{3}&\color{red}{-2}&\color{red}{-5}&\color{red}{-5} \cr
\color{red}{2}&\color{red}{1}&\color{red}{6}&\color{red}{-4}&\color{red}{6}&\color{red}{3}&\color{red}{0}&\color{red}{3} \cr
\color{red}{-4}&\color{red}{-2}&\color{red}{-3}&\color{red}{1}&\color{red}{4}&\color{red}{-1}&\color{red}{1}&\color{red}{7} \cr
\color{red}{-2}&\color{red}{6}&\color{red}{-1}&\color{red}{-8}&\color{red}{0}&\color{red}{1}&\color{red}{-3}&\color{red}{1} \cr
\color{red}{-5}&\color{red}{4}&\color{red}{-4}&\color{red}{1}&\color{red}{2}&\color{red}{0}&\color{red}{7}&\color{red}{-1} \cr
\color{red}{3}&\color{red}{-1}&\color{red}{0}&\color{red}{-1}&\color{red}{-2}&\color{red}{11}&\color{red}{-5}&\color{red}{-1} \cr
5&11&1&3&-2&3&-2&4 } \right] \)
[color=red](%o4)[/color]　[i]done[/i]




紅色數字都是執行結果和pdf檔所寫的不一樣的地方，只是再用maple測試，執行結果和我的相同，或許原作者所使用的LLL程式多了其他的設定(\( \delta=0.75 \)改為\( \delta=0.99 \))
[img]https://math.pro/db/attachment.php?aid=2955&k=c7a3f0b2cdd03e27bc250d4791c91294&t=1434757468&noupdate=yes[/img]
maple下載[url=https://math.pro/db/attachment.php?aid=2954&k=336e04dc91c1115622d08c3b166014ad&t=1434757468]遞迴LLL2.rar[/url]
\( \left[ \matrix{
\color{red}{-2}&\color{red}{3}&\color{red}{8}&\color{red}{-1}&\color{red}{-3}&\color{red}{1}&\color{red}{-4}&\color{red}{-1} \cr
\color{red}{-3}&\color{red}{0}&\color{red}{3}&\color{red}{5}&\color{red}{3}&\color{red}{-2}&\color{red}{-5}&\color{red}{-5} \cr
\color{red}{2}&\color{red}{1}&\color{red}{6}&\color{red}{-4}&\color{red}{6}&\color{red}{3}&\color{red}{0}&\color{red}{3} \cr
\color{red}{-4}&\color{red}{-2}&\color{red}{-3}&\color{red}{1}&\color{red}{4}&\color{red}{-1}&\color{red}{1}&\color{red}{7} \cr
\color{red}{-2}&\color{red}{6}&\color{red}{-1}&\color{red}{-8}&\color{red}{0}&\color{red}{1}&\color{red}{-3}&\color{red}{1} \cr
\color{red}{-5}&\color{red}{4}&\color{red}{-4}&\color{red}{1}&\color{red}{2}&\color{red}{0}&\color{red}{7}&\color{red}{-1} \cr
\color{red}{3}&\color{red}{-1}&\color{red}{0}&\color{red}{-1}&\color{red}{-2}&\color{red}{11}&\color{red}{-5}&\color{red}{-1} \cr
5&11&1&3&-2&3&-2&4 } \right] \)\( \left[ \matrix{
\color{red}{-2}&\color{red}{6}&\color{red}{-1}&\color{red}{-8}&\color{red}{0}&\color{red}{1}&\color{red}{-3}&\color{red}{1} \cr
\color{red}{2}&\color{red}{-3}&\color{red}{-8}&\color{red}{1}&\color{red}{3}&\color{red}{-1}&\color{red}{4}&\color{red}{1} \cr
\color{red}{3}&\color{red}{-3}&\color{red}{6}&\color{red}{2}&\color{red}{-6}&\color{red}{2}&\color{red}{4}&\color{red}{3} \cr
\color{red}{-2}&\color{red}{-1}&\color{red}{-6}&\color{red}{4}&\color{red}{-6}&\color{red}{-3}&\color{red}{0}&\color{red}{-3} \cr
\color{red}{5}&\color{red}{-4}&\color{red}{4}&\color{red}{-1}&\color{red}{-2}&\color{red}{0}&\color{red}{-7}&\color{red}{1} \cr
\color{red}{4}&\color{red}{2}&\color{red}{3}&\color{red}{-1}&\color{red}{-4}&\color{red}{1}&\color{red}{-1}&\color{red}{-7} \cr
\color{red}{-2}&\color{red}{3}&\color{red}{-4}&\color{red}{0}&\color{red}{0}&\color{red}{11}&\color{red}{2}&\color{red}{-2} \cr
5&11&1&3&-2&3&-2&4 } \right] \)



參考資料：
Recursive Lattice Reduction，Thomas Plantard, Willy Susilo
[url]https://thomas-plantard.github.io/pdf/PlaSus10.pdf[/url]
簡報檔
[url]https://thomas-plantard.github.io/pdf/talk10-scn.pdf[/url]

Lattice Reduction for Modular Knapsack，Thomas Plantard, Willy Susilo, Zhenfei Zhang
[url]https://thomas-plantard.github.io/pdf/PlaSusZha12.pdf[/url]
簡報檔
[url]http://www1.uwindsor.ca/sac2012/system/files/2a_Plantard.pdf[/url]

bugmens 發表於 2017-1-25 10:42

5.改進LLL方法－PotLLL

原本的LLL只考慮相鄰的兩列向量( \( v_i^*、v_{i-1}^* \) )是否滿足Lovász condition( \( \displaystyle \Vert\; v_i^* \Vert\;^2 \ge (\frac{3}{4}-\mu_{i,i-1}^2)\Vert\; v_{i-1}^* \Vert\;^2 \) )，違反的話則將\( v_{k-1},v_k \)交換。而PotLLL考慮是否滿足(\( \delta \cdot Pot(B)\le Pot(\sigma_{k,l}B) \))，違反的話則將第\( l \)列向量插入第\( k \)列向量的位置。


\( \sigma_{k,l}(i)=\cases{i \cr l \cr i-1}\matrix{\hbox{for　i<k or i>l}, \cr \hbox{for　i=k,　} \cr \hbox{for　k<i ≦ l.}} \)代表將第\( l \)列向量插入第\(k\)列向量。
\( B \)是論文用來代表lattice，我的maxima程式用\( v \)表示。
\( \displaystyle Pot(B):= \prod_{i=1}^n vol(L(b_1,\ldots,b_i))^2= \prod_{i=1}^n \Vert\; b_i^* \Vert\;^{2(n-i+1)} \)計算lattice的Potential值
以上式子就是將lattice \(B\)分成很多sub lattice
\( B_1=L(b_1) \)，由\( b_1 \)向量所組成的lattice，其體積的平方為\( \Vert\; b_1^* \Vert\;^2 \)
\( B_2=L(b_1,b_2) \)，由\( b_1,b_2 \)向量組成的lattice，其體積的平方為\( \Vert\; b_1^* \Vert\;^2 \cdot \Vert\; b_2^* \Vert\;^2 \)
\( \ldots \)
\( B_n=L(b_1,b_2,\ldots,b_n) \)，由\( b_1,b_2,\ldots,b_n \)向量組成的lattice，其體積的平方為\( \Vert\; b_1^* \Vert\;^2 \cdot \Vert\; b_2^* \Vert\;^2 \ldots \Vert\; b_n^* \Vert\;^2 \)
將全部sub lattice體積的平方全部乘起來\( \displaystyle \prod_{i=1}^n \Vert\; b_i^* \Vert\;^{2(n-i+1)} \)就是Potential值


以\( B=\left[ \matrix{9&2&7 \cr 8&6&1 \cr 3&2&6 } \right] \)為例，計算\( B \)的Potential值
先計算GramSchmit正交化後的向量\( b^*=\left[ \matrix{\displaystyle 9&2&7\cr \frac{253}{134}&\frac{311}{67}&-\frac{503}{134}\cr -\frac{8080}{5253}&\frac{9494}{5253}&\frac{7676}{5253}} \right] \)，注意各向量彼此正交(垂直)。

各向量長度的平方為\( \matrix{\displaystyle \Vert\; b_1^*\Vert\;^2=9^2+2^2+7^2=134　　　　　　　　　　 \cr \Vert\; b_2^*\Vert\;^2=\left( \frac{253}{134} \right)^2+\left( \frac{311}{67} \right)^2+\left( -\frac{503}{134} \right)^2=\frac{5253}{134}　 \cr \Vert\; b_3^*\Vert\;^2=\left( -\frac{8080}{5253} \right)^2+\left( \frac{9494}{5253} \right)^2+\left( \frac{7676}{5253} \right)^2=\frac{40804}{5253}} \)
\( B_1=\left[ \matrix{9&2&7} \right] \)，\( b_1 \)向量長度就是\( \Vert\; b_1^* \Vert\; \)，平方為\( \Vert\; b_1^* \Vert\;^2=134 \)
\( B_2=\left[ \matrix{9&2&7 \cr 8&6&1} \right] \)，\( b_1,b_2 \)所張成的平行四邊形面積等同於\( b_1^*\)長、\(b_2^* \)寬所張成的長方形面積，平方為\( \displaystyle \Vert\; b_1^* \Vert\;^2 \cdot \Vert\; b_2^* \Vert\;^2=134 \cdot \frac{5253}{134}=5253 \)
\( B_3=\left[ \matrix{9&2&7 \cr 8&6&1 \cr 3&2&6} \right] \)，\( b_1,b_2,b_3 \)所張成的平行六面體體積等同於\( b_1^*\)長、\( b_2^*\)寬、\( b_3^* \)高所張成的長方體體積，平方為\( \displaystyle \Vert\; b_1^* \Vert\;^2 \cdot \Vert\; b_2^* \Vert\;^2 \cdot \Vert\; b_3^* \Vert\;^2=134 \cdot \frac{5253}{134} \cdot \frac{40804}{5253}=40804 \)
將全部sub lattice體積的平方全部乘起來\( 134 \cdot 5253 \cdot 40804=28722017208 \)就是Potential值


＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
以下程式計算Potential值

[color=green]要先載入eigen.mac才能使用gramschmidt指令[/color]
[color=red](%i1)[/color]　[color=blue]load("eigen.mac");[/color]
[color=red](%o1)[/color]　C:/Program Files (x86)/Maxima-sbcl-5.37.1/share/maxima/5.37.1/share/matrix/eigen.mac

[color=green]計算Potential值副程式[/color]
[color=red](%i2)[/color]
[color=blue]Pot(v):=block
(vstar:gramschmidt(v),
n:length(v[1]),
product((vstar[ i ].vstar[ i ])^(n-i+1),i,1,n)
)$[/color]

[color=green]計算v的Potential值[/color]
[color=red](%i3)[/color]
[color=blue]v:matrix([9,2,7],
              [8,6,1],
              [3,2,6]);
Pot(v);[/color]
[color=red](%o3)[/color]　\( \left[ \matrix{9&2&7 \cr 8&6&1 \cr 3&2&6} \right] \)
[color=red](%o4)[/color]　28722017208



＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
以下程式為PotLLL執行結果

[color=green]GramSchmit正交化[/color]
[color=red](%i1)[/color]
[color=blue]GramSchmit(v):=block
([m:length(v)],
vstar:copymatrix(v),
mu:zeromatrix(m,m),
for i:1 thru m do
  (for j:1 thru i do
     (mu[ i ][j]:v[ i ].vstar[j]/vstar[j].vstar[j],
      vstar[ i ]:v[ i ]-sum(mu[ i ][j]*vstar[j],j,1,i-1)
     )
  )
)$[/color]

[color=green]檢查是否違反Size condition[/color]
[color=red](%i2)[/color]
[color=blue]SizeReduce(i,j):=block
([q:round(mu[ i ][j])],
if q#0 then
   (print("round(μ[",i,"][",j,"])=",round(mu[ i ][j]),"違反Size condition"),
    print("v=",v,"  第",i,"列-",q,"*第",j,"列  v=",rowop(v,i,j,q)),
    v:rowop(v,i,j,q)
   )
)$[/color]

[color=green]第l列移動到第k列[/color]
[color=red](%i3)[/color]
[color=blue]MoveRow(v,k,l) := block
([n:length(v)],
head(v, n) :=if n > 0 then head(submatrix(length(v), v), n - 1) else v,
tail(v, n) :=if n > 0 then tail(submatrix(1, v), n - 1) else v,
v:addrow(head(v, n - k+1), v[l], tail(v, k-1)),
if k<l then v:submatrix(l+1,v) else v:submatrix(l,v)
)$[/color]

[color=green]PotLLL主程式[/color]
[color=red](%i4)[/color]
[color=blue]PotLLL(v):=block(
[l:1,n:length(v),delta:3/4],
while l<=n do
  (if l>1 then
     (print("第",l,"列進行SizeReduce,μ=",mu)
     ),
   for i:1 thru l-1 do
     (SizeReduce(l,i)
     ),
   GramSchmit(v),
   P:1,
   Pmin:1,
   k:1,
   for j:l-1 thru 1 step -1 do
     (P: P*(vstar[l].vstar[l]+sum(mu[l,i]^2*vstar[ i ].vstar[ i ],i,j,l-1))/(vstar[j].vstar[j]),
      if P< Pmin then
        (k:j,
         Pmin: P
        )
     ),
   print("第",l,"列移到第",k,"列有最小的potential比值",Pmin),
   if delta> Pmin then
     (print("potential比值",Pmin,"比",delta,"小"),
      tempv:v,
      v:MoveRow(v,k,l),
      print(tempv,"第",l,"列移到第",k,"列",v),
      GramSchmit(v),
      print("l值",l,"=>",k),
      l:k
     )
   else
     (print("potential比值",Pmin,"比",delta,"大,l值",l,"=>",l+1),
      l:l+1
     )
  ),
return(v)
)$[/color]

[color=red](%i6)[/color]
[color=blue]v:matrix([9,2,7],
              [8,6,1],
              [3,2,6]);
PotLLL(v);[/color]
[color=red](%o5)[/color]　\( \left[ \matrix{9&2&7 \cr 8&6&1 \cr 3&2&6} \right] \)
第1列移到第1列有最小的potential比值1
potential比值1比\( \displaystyle \frac{3}{4} \)大,l值1=>2

第2列進行SizeReduce,μ=\( \left[ \matrix{\displaystyle 1&0&0 \cr \frac{91}{134}&1&0 \cr \frac{73}{134}&-\frac{1015}{5253}&1} \right] \)
round(μ[2][1])=1違反Size condition
\( v=\left[ \matrix{9&2&7 \cr 8&6&1 \cr 3&2&6} \right] \)  第2列\(-1*\)第1列  \( \left[ \matrix{9&2&7 \cr -1&4&-6 \cr 3&2&6} \right] \)

第2列移到第1列有最小的potential比值\( \displaystyle \frac{53}{134} \)
potential比值\( \displaystyle \frac{53}{134} \)比\( \displaystyle \frac{3}{4} \)小
\( \left[ \matrix{9&2&7\cr -1&4&-6\cr 3&2&6} \right] \)第2列移到第1列\( \left[ \matrix{-1&4&-6 \cr 9&2&7 \cr 3&2&6} \right] \)
l值2=>1

第1列移到第1列有最小的potential比值1
potential比值1比\( \displaystyle \frac{3}{4} \)大,l值1=>2

第2列進行SizeReduce,\( \mu=\left[ \matrix{\displaystyle 1&0&0\cr -\frac{43}{53}&1&0\cr -\frac{31}{53}&\frac{2536}{5253}&1} \right] \)
round(μ[2][1])=-1違反Size condition
\( v=\left[ \matrix{-1&4&-6\cr 9&2&7\cr 3&2&6} \right] \)  第2列\( - -1* \)第1列  \( v=\left[ \matrix{-1&4&-6\cr 8&6&1\cr 3&2&6} \right] \)

第2列移到第1列有最小的potential比值1
potential比值1比\( \displaystyle \frac{3}{4} \)大,l值2=>3

第3列進行SizeReduce,\( \mu=\left[ \matrix{\displaystyle 1&0&0\cr \frac{10}{53}&1&0\cr -\frac{31}{53}&\frac{2536}{5253}&1} \right] \)
round(μ[3][1])=-1違反Size condition
\( v=\left[ \matrix{-1&4&-6\cr 8&6&1\cr 3&2&6} \right] \)  第3列\( - -1* \)第1列  \( v=\left[ \matrix{-1&4&-6\cr 8&6&1\cr 2&6&0} \right] \)

第2列移到第1列有最小的potential比值1
potential比值1比\( \displaystyle \frac{3}{4} \)大,l值2=>3

第3列進行SizeReduce,\( \mu=\left[ \matrix{\displaystyle 1&0&0\cr -\frac{9}{20}&1&0\cr \frac{13}{10}&-\frac{186}{409}&1} \right] \)
round(μ[3][1])=1違反Size condition
\( v=\left[ \matrix{2&6&0\cr -3&-2&-6\cr 8&6&1} \right] \)  第3列\( -1* \)第1列  \( v=\left[ \matrix{2&6&0\cr -3&-2&-6\cr 6&0&1} \right] \)

第3列移到第1列有最小的potential比值\( \displaystyle \frac{65440}{278409} \)
potential 比值\( \displaystyle \frac{65440}{278409} \)比\( \displaystyle \frac{3}{4} \)小
\( \left[ \matrix{-1&4&-6 \cr 8&6&1 \cr 2&6&0} \right] \)第3列移到第1列\(  \left[ \matrix{2&6&0 \cr -1&4&-6 \cr 8&6&1} \right]\)
l值3=>1

第1列移到第1列有最小的potential比值1
potential比值1比\( \displaystyle \frac{3}{4} \)大,l值1=>2
第2列進行SizeReduce,\( \mu=\left[ \matrix{\displaystyle 1&0&0 \cr \frac{11}{20}&1&0 \cr \frac{13}{10}&-\frac{186}{409}&1} \right] \)
round(μ[2][1])=1違反Size condition
\( v=\left[ \matrix{2&6&0 \cr -1&4&-6 \cr 8&6&1} \right] \)  第2列\(-1*\)第1列  \( v=\left[ \matrix{2&6&0 \cr -3 & -2 &-6 \cr 8&6&1} \right] \)

第2列移到第1列有最小的potential比值1
potential比值1比\( \displaystyle \frac{3}{4} \)大,l值2=>3
第3列進行SizeReduce,\( \mu=\left[ \matrix{\displaystyle 1&0&0 \cr -\frac{9}{20}&1&0 \cr \frac{13}{10}&-\frac{186}{409}&1} \right] \)
round(μ[3][1])=1違反Size condition
\( v=\left[ \matrix{2&6&0 \cr -3&-2&-6 \cr 8&6&1} \right] \)  第3列\(-1*\)第1列  \( v=\left[ \matrix{2&6&0 \cr -3&-2&-6 \cr 6&0&1} \right] \)
第3列移到第1列有最小的potential比值\( \displaystyle \frac{6179}{8180} \)
potential比值\( \displaystyle \frac{6179}{8180} \)比\( \displaystyle \frac{3}{4} \)大,l值3=>4
[color=red](%o6)[/color]　\( \left[ \matrix{2&6&0 \cr -3&-2&-6 \cr 6&0&1} \right] \)


參考資料
PotLLL: A Polynomial Time Version of LLL With Deep Insertions
[url]https://arxiv.org/abs/1307.7534[/url]
PDF檔[url]https://arxiv.org/pdf/1307.7534v1.pdf[/url]

bugmens 發表於 2017-12-30 13:55

6-1.改進LLL方法－Jacobi方法

之前的Gaussian/Lagrange方法針對兩個向量進行化簡
[url]https://math.pro/db/viewthread.php?tid=1876&page=1#pid10232[/url]
化簡後的向量符合(1)\(  \displaystyle \Bigg\vert\; \frac{v_1 \cdot v_2}{v_1 \cdot v_1} \Bigg\vert\;\le \frac{1}{2} \)　(2)\( \Vert\; v_1 \Vert\; \le \Vert\; v_2 \Vert\; \)兩個條件
擴展到更多向量就是將任兩個向量進行Gaussian/Lagrange化簡，任兩個向量滿足
(1)\(  \displaystyle \Bigg\vert\; \frac{v_i \cdot v_j}{v_i \cdot v_i} \Bigg\vert\;\le \frac{1}{2} \)　(2)\( \Vert\; v_i \Vert\; \le \Vert\; v_j \Vert\; \)，\( 1 \le i<j\le n \)兩個條件



[color=red](%i1)[/color]
[color=blue]Jacobi(v):=block
([i,j,n:length(v),t,End],
do
  (End:true,
   for i:1 thru n-1 do
     (for j:i+1 thru n do
        (if v[ i ].v[ i ]>v[j].v[j] then
           (print("第",i,"列長度",sqrt(v[ i ].v[ i ]),"比第",j,"列長度",sqrt(v[j].v[j]),"長"),
            print(v,"第",i,"列和第",j,"列交換",v:rowswap(v,i,j)),
            End:false
           ),
        t:round(v[ i ].v[j]/v[ i ].v[ i ]),
        if t#0 then
           (print("t=round(v",i,".v",j,"/v",i,".v",i,")=round(",v[ i ].v[j],"/",v[ i ].v[ i ],")=",t,"不等於0"),
            print(v,"第",j,"列-",t,"*第",i,"列",v:rowop(v,j,i,t)),
            End:false
           )
        )
     ),
   if End=true then
     (print("化簡後v=",v,
             ",",vi.vj/vi.vi,"=",genmatrix(lambda([i,j],if i<j then v[ i ].v[j]/v[ i ].v[ i ] else "*"),n,n),
             ",向量長度=",genmatrix(lambda([i,j],sqrt(v[ i ].v[ i ])),n,1)),
      print("所有向量符合(1)|vi.vj/vi.vi|≦1/2，(2)∥vi∥≦∥vj∥，1≦i<j≦n兩個條件，程式結束"),
      return(v)
     ),
   print("------------------------")
  )
)$[/color]

[color=red](%i2)[/color]
[color=blue]v:matrix([1,1,1],
             [-1,0,2],
             [3,5,6]);[/color]
[color=red](%o2)[/color]　\( \left[ \matrix{1&1&1\cr -1&0&2\cr 3&5&6} \right] \)

[color=red](%i3)[/color]　[color=blue]Jacobi(v);[/color]
\( \displaystyle t=round(v1.v3/v1.v1)=round(14/3)=5\)不等於0
\( \left[ \matrix{1&1&1\cr -1&0&2\cr 3&5&6} \right] \)第3列-5*第1列\( \left[ \matrix{1&1&1\cr -1&0&2\cr -2&0&1} \right] \)
\( \displaystyle t=round(v2.v3/v2.v2)=round(4/5)=1\)不等於0
\( \left[ \matrix{1&1&1\cr -1&0&2\cr -2&0&1} \right] \)第3列-1*第2列\( \left[ \matrix{1&1&1\cr -1&0&2\cr -1&0&-1} \right] \)
------------------------
第1列長度\( \sqrt{3}\)比第3列長度\( \sqrt{2}\)長
\( \left[ \matrix{1&1&1\cr -1&0&2\cr -1&0&-1} \right] \)第1列和第3列交換\( \left[ \matrix{-1&0&-1\cr -1&0&2\cr 1&1&1} \right] \)
\( \displaystyle t=round(v1.v3/v1.v1)=round(-2/2)=-1\)不等於0
\( \left[ \matrix{-1&0&-1\cr -1&0&2\cr 1&1&1} \right] \)第3列--1*第1列\( \left[ \matrix{-1&0&-1\cr -1&0&2\cr 0&1&0} \right] \)
第2列長度\( \sqrt{5}\)比第3列長度1長
\( \left[ \matrix{-1&0&-1\cr -1&0&2\cr 0&1&0} \right] \)第2列和第3列交換\( \left[ \matrix{-1&0&-1\cr 0&1&0\cr -1&0&2} \right] \)
------------------------
第1列長度\(\sqrt{2}\)比第2列長度1長
\( \left[ \matrix{-1&0&-1\cr 0&1&0\cr -1&0&2} \right] \)第1列和第2列交換\( \left[ \matrix{0&1&0\cr -1&0&-1\cr -1&0&2} \right] \)
------------------------
化簡後\( v=\left[ \matrix{0&1&0\cr -1&0&-1\cr -1&0&2} \right] \),\( \frac{vi.vj}{vi^2}=\left[ \matrix{*&0&0\cr *&*&-\frac{1}{2} \cr *&*&*} \right] \),向量長度\( =\left[ \matrix{1 \cr \sqrt{2} \cr \sqrt{5}} \right] \)
所有向量符合(1)|vi.vj/vi.vi|≦1/2，(2)∥vi∥≦∥vj∥，1≦i<j≦n兩個條件，程式結束

[color=red](%o3)[/color]　\( \left[ \matrix{0&1&0\cr -1&0&-1\cr -1&0&2} \right] \)

[color=red](%i4)[/color]
[color=blue]v:matrix([1,1,7,2],
         [9,8,4,6],
         [1,8,5,7],
         [2,3,1,1]);[/color]
[color=red](%o4)[/color]　\( \left[ \matrix{1&1&7&2\cr 9&8&4&6\cr 1&8&5&7\cr 2&3&1&1} \right] \)

[color=red](%i5)[/color]　[color=blue]Jacobi(v);[/color]
\( \displaystyle t=round(v1.v2/v1.v1)=round(57/55)=1\)不等於0
\( \left[ \matrix{1&1&7&2\cr 9&8&4&6\cr 1&8&5&7\cr 2&3&1&1}\right] \)第2列-1*第1列\( \left[ \matrix{1&1&7&2\cr 8&7&-3&4\cr 1&8&5&7\cr 2&3&1&1} \right] \)
\( \displaystyle t=round(v1.v3/v1.v1)=round(58/55)=1\)不等於0
\( \left[ \matrix{1&1&7&2\cr 8&7&-3&4\cr 1&8&5&7\cr 2&3&1&1}\right] \)第3列-1*第1列\( \left[ \matrix{1&1&7&2\cr 8&7&-3&4\cr 0&7&-2&5\cr 2&3&1&1} \right] \)
第1列長度\( \sqrt{55}\)比第4列長度\( \sqrt{15}\)長
\( \left[ \matrix{1&1&7&2\cr 8&7&-3&4\cr 0&7&-2&5\cr 2&3&1&1}\right] \)第1列和第4列交換\( \left[ \matrix{2&3&1&1\cr 8&7&-3&4\cr 0&7&-2&5\cr 1&1&7&2} \right] \)
\( \displaystyle t=round(v1.v4/v1.v1)=round(14/15)=1\)不等於0
\( \left[ \matrix{2&3&1&1\cr 8&7&-3&4\cr 0&7&-2&5\cr 1&1&7&2}\right] \)第4列-1*第1列\( \left[ \matrix{2&3&1&1\cr 8&7&-3&4\cr 0&7&-2&5\cr -1&-2&6&1} \right] \)
第2列長度\( \sqrt{138}\)比第3列長度\( \sqrt{78}\)長
\( \left[ \matrix{2&3&1&1\cr 8&7&-3&4\cr 0&7&-2&5\cr -1&-2&6&1}\right] \)第2列和第3列交換\( \left[ \matrix{2&3&1&1\cr 0&7&-2&5\cr 8&7&-3&4\cr -1&-2&6&1} \right] \)
\( \displaystyle t=round(v2.v3/v2.v2)=round(75/78)=1\)不等於0
\( \left[ \matrix{2&3&1&1\cr 0&7&-2&5\cr 8&7&-3&4\cr -1&-2&6&1}\right] \)第3列-1*第2列\( \left[ \matrix{2&3&1&1\cr 0&7&-2&5\cr 8&0&-1&-1\cr -1&-2&6&1} \right] \)
第2列長度\( \sqrt{78}\)比第4列長度\( \sqrt{42}\)長
\( \left[ \matrix{2&3&1&1\cr 0&7&-2&5\cr 8&0&-1&-1\cr -1&-2&6&1}\right] \)第2列和第4列交換\( \left[ \matrix{2&3&1&1\cr -1&-2&6&1\cr 8&0&-1&-1\cr 0&7&-2&5} \right] \)
------------------------
\( \displaystyle t=round(v1.v3/v1.v1)=round(14/15)=1\)不等於0
\( \left[ \matrix{2&3&1&1\cr -1&-2&6&1\cr 8&0&-1&-1\cr 0&7&-2&5}\right] \)第3列-1*第1列\( \left[ \matrix{2&3&1&1\cr -1&-2&6&1\cr 6&-3&-2&-2\cr 0&7&-2&5} \right] \)
\( \displaystyle t=round(v1.v4/v1.v1)=round(24/15)=2\)不等於0
\( \left[ \matrix{2&3&1&1\cr -1&-2&6&1\cr 6&-3&-2&-2\cr 0&7&-2&5}\right] \)第4列-2*第1列\( \left[ \matrix{2&3&1&1\cr -1&-2&6&1\cr 6&-3&-2&-2\cr -4&1&-4&3} \right] \)
第3列長度\( \sqrt{53}\)比第4列長度\( \sqrt{42}\)長
\( \left[ \matrix{2&3&1&1\cr -1&-2&6&1\cr 6&-3&-2&-2\cr -4&1&-4&3}\right] \)第3列和第4列交換\( \left[ \matrix{2&3&1&1\cr -1&-2&6&1\cr -4&1&-4&3\cr 6&-3&-2&-2} \right] \)
\( \displaystyle t=round(v3.v4/v3.v3)=round(-25/42)=-1\)不等於0
\( \left[ \matrix{2&3&1&1\cr -1&-2&6&1\cr -4&1&-4&3\cr 6&-3&-2&-2}\right] \)第4列--1*第3列\( \left[ \matrix{2&3&1&1\cr -1&-2&6&1\cr -4&1&-4&3\cr 2&-2&-6&1} \right] \)
------------------------
\( \displaystyle t=round(v2.v4/v2.v2)=round(-33/42)=-1\)不等於0
\( \left[ \matrix{2&3&1&1\cr -1&-2&6&1\cr -4&1&-4&3\cr 2&-2&-6&1}\right] \)第4列--1*第2列\( \left[ \matrix{2&3&1&1\cr -1&-2&6&1\cr -4&1&-4&3\cr 1&-4&0&2} \right] \)
第3列長度\( \sqrt{42}\)比第4列長度\( \sqrt{21}\)長
\( \left[ \matrix{2&3&1&1\cr -1&-2&6&1\cr -4&1&-4&3\cr 1&-4&0&2}\right] \)第3列和第4列交換\( \left[ \matrix{2&3&1&1\cr -1&-2&6&1\cr 1&-4&0&2\cr -4&1&-4&3} \right] \)
------------------------
\( \displaystyle t=round(v1.v3/v1.v1)=round(-8/15)=-1\)不等於0
\( \left[ \matrix{2&3&1&1\cr -1&-2&6&1\cr 1&-4&0&2\cr -4&1&-4&3}\right] \)第3列--1*第1列\( \left[ \matrix{2&3&1&1\cr -1&-2&6&1\cr 3&-1&1&3\cr -4&1&-4&3} \right] \)
第2列長度\( \sqrt{42}\)比第3列長度\(2\sqrt{5}\)長
\( \left[ \matrix{2&3&1&1\cr -1&-2&6&1\cr 3&-1&1&3\cr -4&1&-4&3}\right] \)第2列和第3列交換\( \left[ \matrix{2&3&1&1\cr 3&-1&1&3\cr -1&-2&6&1\cr -4&1&-4&3} \right] \)
------------------------
化簡後\( v=\left[ \matrix{2&3&1&1\cr 3&-1&1&3\cr -1&-2&6&1\cr -4&1&-4&3} \right] \),\( \frac{vi.vj}{vi^2}=\left[ \matrix{ *&\frac{7}{15}&-\frac{1}{15}&-\frac{2}{5} \cr *&*&\frac{2}{5}&-\frac{2}{5} \cr *&*&*&-\frac{19}{42} \cr *&*&*&*} \right] \),向量長度\( =\left[ \matrix{\sqrt{15} \cr 2\sqrt{5} \cr \sqrt{42} \cr \sqrt{42}} \right] \)
所有向量符合(1)|vi.vj/vi.vi|≦1/2，(2)∥vi∥≦∥vj∥，1≦i<j≦n兩個條件，程式結束
[color=red](%o5)[/color]　\( \left[ \matrix{2&3&1&1\cr 3&-1&1&3\cr -1&-2&6&1\cr -4&1&-4&3} \right] \)

bugmens 發表於 2017-12-31 13:44

6-2.改進LLL方法－Jacobi方法

[table=100%][tr][td]原本的Gauss/Lagrange方法[/td][td]本論文的Gauss/Lagrange方法[/td][/tr]
[tr][td]1  \( do\{\; \)
2　\(if(v_1的長度>v_2的長度)\)
3　　\( \{\; v_1和v_2兩個向量交換 \}\; \)
4　\(t=\lfloor\; v_1.v_2/v_1.v_1 \rceil\; \)
5  \(if(t!=0)\)
6    \(\{\; v_2=v_2−tv_1; \}\;\)
7　 \(\}\;\)
8  \(while(t!=0);\)[/td][td]1  \(G=V^TV\)
2  \(U=I_2\)
3  \( if \) \(G(1,1)<G(2,2)\)
4    \( swap \) \(G(:,1)\) \(and\) \(G(:,2)\)
5    \( swap \) \(G(1,: )\) \(and\) \(G(2,: )\)
6    \( swap \) \(Z(:,1)\) \(and\) \(G(:,2)\)
7  \(end\)
8
9  \(while\) \(G(1,1)>G(2,2)\)
10   \(q=\lfloor\; G(1,2)/G(2,2) \rceil\;\)
11   \(G(:,2)=G(:,2)-q \times G(:,1)\)
12   \(G(2,: )=G(2,: )-q \times G(1,: )\)
13   \(U(:,2)=U(:,2)-q \times U(:,1)\)
14 \(end\)
15
16 \(return\) \(U\)[/td][/tr]
[/table]註：說明論文所用的符號
1.\(G=V^TV\)代表gram矩陣，其中\(G(i,i)=v_i.v_i,G(i,j)=v_i.v_j\)，對角線元素為每個向量長度的平方，其他元素為兩向量的內積。
2.\(B\)代表lattice，為文章一致改用\(V\)表示lattice。
3.\(Z\)代表unimodular矩陣，但一般常用\(U\)表示unimodular矩陣，其中\(det(U)=+1或-1\)。



[table=100%][tr][td]Jacobi方法以列計算[/td][td]Jacobi方法以行計算[/td][/tr]
[tr][td]1  \(G=VV^T\)
2  \(U=I_n\)
3
4  \(while\) \(not\) \(all\) \(pairs\) \((v_i,v_j)\) \(satisfy\) \( \Vert\; v_i \Vert\; \le \Vert\; v_j \Vert\; \) and \( \displaystyle |\; v_i v_j |\; \le \frac{\Vert\; v_i \Vert\;^2}{2} \)
5    \(for\) \(i=1\) \(to\) \(n-1\)
6      \(for\) \(j=i+1\) \(to\) \(n\)
7        \(q=G(i,j)/G(i,i)\)
8        \(if\) \(|\; q |\;>1/2\)
9          \(G(:,j)=G(:,j)-\lfloor\; q \rceil\; \times G(:,i)\)
10         \(G(j,: )=G(j,: )-\lfloor\; q \rceil\; \times G(i,: )\)
11         \(U(j,: )=U(j,: )-\lfloor\; q \rceil\; \times U(i,: )\)
12       \(end\)
13       \(if\) \(G(i,i)>G(j,j)\)
14         \(swap\) \(G(:,i)\) \(and\) \(G(:,j)\)
15         \(swap\) \(G(i,: )\) \(and\) \(G(j,: )\)
16         \(swap\) \(U(i,: )\) \(and\) \(U(j,: )\)
17       \(end\)
18     \(end\)
19   \(end\)
20 \(end\)
21
22 \(return\) \(UV\)[/td][td]1  \(G=V^TV\)
2  \(U=I_n\)
3
4  \(while\) \(not\) \(all\) \(pairs\) \((v_i,v_j)\) \(satisfy\) \( \Vert\; v_i \Vert\; \le \Vert\; v_j \Vert\; \) and \( \displaystyle |\; v_i v_j |\; \le \frac{\Vert\; v_i \Vert\;^2}{2} \)
5    \(for\) \(i=1\) \(to\) \(n-1\)
6      \(for\) \(j=i+1\) \(to\) \(n\)
7        \(q=G(i,j)/G(i,i)\)
8        \(if\) \(|\; q |\;>1/2\)
9          \(G(:,j)=G(:,j)-\lfloor\; q \rceil\; \times G(:,i)\)
10         \(G(j,: )=G(j,: )-\lfloor\; q \rceil\; \times G(i,: )\)
11         \(U(:,j)=U(:,j)-\lfloor\; q \rceil\; \times U(:,i)\)
12       \(end\)
13       \(if\) \(G(i,i)>G(j,j)\)
14         \(swap\) \(G(:,i)\) \(and\) \(G(:,j)\)
15         \(swap\) \(G(i,: )\) \(and\) \(G(j,: )\)
16         \(swap\) \(U(:,i)\) \(and\) \(U(:,j)\)
17       \(end\)
18     \(end\)
19   \(end\)
20 \(end\)
21
22 \(return\) \(VU\)[/td][/tr]
[/table]註：
論文演算法以行向量運算，本文章卻以列向量運算，所以將兩個演算法並列出來，其中第1,11,16,22行有差異。
論文演算法第7行\(q=G(i,j)/G(j,j)\)會導致lattice尚未化簡完程式就提早結束，更正為\(q=G(i,j)/G(i,i)\)。

參考資料：
[url]http://www.cas.mcmaster.ca/~qiao/[/url]
Filip Jeremic and Sanzheng Qiao. A Parallel Jacobi-type Lattice Basis Reduction Algorithm. International Journal of Numerical Analysis and Modeling, Series B. Vol. 5, No. 1-2, 2014, 1-12.
[url]http://www.cas.mcmaster.ca/~qiao/publications/JQ14.pdf[/url]
Filip Jeremic and Sanzheng Qiao. A GPU Implementation of a Jacobi Method for Lattice Basis Reduction. Proceedings of International Workshop on Data-Intensive Scientific Discovery (DISD), 2013, Shanghai University, Shanghai, China, August 1-4, 2013.
[url]http://www.cas.mcmaster.ca/~qiao/publications/JQ13.pdf[/url]



[color=green]以列向量運算的Jacobi方法[/color]
[color=red](%i1)[/color]
[color=blue]JacobibyRow(V):=block
([End,G,n:length(V),U,i,j],
G:V.transpose(V),
U:ident(n),
do
(End:true,
for i:1 thru n-1 do
  (for j:i+1 thru n do
     (q:G[i,j]/G[i,i],
      if abs(q)>1/2 then
        (print("G(",i,",",j,")/G(",i,",",i,")=",q,">",1/2,"  ,  round(",q,")=",round(q)),
         print("G=",G,"  第",j,"行-",round(q),"*第",i,"行  G=",G:columnop(G,j,i,round(q))),
         print("G=",G,"  第",j,"列-",round(q),"*第",i,"列  G=",G:rowop(G,j,i,round(q))),
         print("U=",U,"  第",j,"列-",round(q),"*第",i,"列  U=",U:rowop(U,j,i,round(q))),
         End:false
        ),
      if G[i,i]>G[j,j] then
        (print("G(",i,",",i,")=",G[i,i],">G(",j,",",j,")=",G[j,j]),
         print("G=",G,"  第",i,"行和第",j,"行交換  G=",G:columnswap(G,i,j)),
         print("G=",G,"  第",i,"列和第",j,"列交換  G=",G:rowswap(G,i,j)),
         print("U=",U,"  第",i,"列和第",j,"列交換  U=",U:rowswap(U,i,j)),
         End:false
        )
     )
    ),
   if End=true then
     (print("G=",G,",",vi.vj/vi.vi,"=",genmatrix(lambda([i,j],if i<j then G[i,j]/G[i,i] else "*"),n,n),
             ",向量長度=",genmatrix(lambda([i,j],sqrt(G[i,i])),n,1)),
      print("所有向量符合(1)|vi.vj/vi.vi|≦1/2，(2)∥vi∥≦∥vj∥，1≦i<j≦n兩個條件，程式結束"),
      print("化簡後向量V=U.V=",U,V,"=",U.V),
      return(U.V)
     ),
    print("------------------------")
  )
)$[/color]

[color=green]列向量的lattice[/color]
[color=red](%i2)[/color]
[color=blue]V:matrix([1,1,1],
             [-1,0,2],
             [3,5,6]);[/color]

[color=red](%o2)[/color]　\( \left[ \matrix{1&1&1\cr -1&0&2\cr 3&5&6} \right] \)

[color=red](%i3)[/color]　[color=blue]JacobibyRow(V);[/color]
\( \displaystyle G( 1,3)/G(1,1)=\frac{14}{3}>\frac{1}{2}\)  ,  \( \displaystyle round(\frac{14}{3})=5\)
\( G=\left[ \matrix{3&1&14\cr 1&5&9\cr 14&9&70} \right] \)第3行-5*第1行  \( G=\left[ \matrix{3&1&-1\cr 1&5&4\cr 14&9&0} \right] \)
\( G=\left[ \matrix{3&1&-1\cr 1&5&4\cr 14&9&0} \right] \)第3列-5*第1列  \( G=\left[ \matrix{3&1&-1\cr 1&5&4\cr -1&4&5} \right] \)
\( U=\left[ \matrix{1&0&0\cr 0&1&0\cr 0&0&1} \right] \)第3列-5*第1列  \( U=\left[ \matrix{1&0&0\cr 0&1&0\cr -5&0&1} \right] \)
\( \displaystyle G( 2,3)/G(2,2)=\frac{4}{5}>\frac{1}{2}\)  ,  \( \displaystyle round(\frac{4}{5})=1\)
\( G=\left[ \matrix{3&1&-1\cr 1&5&4\cr -1&4&5} \right] \)第3行-1*第2行  \( G=\left[ \matrix{3&1&-2\cr
1&5&-1\cr -1&4&1} \right] \)
\( G=\left[ \matrix{3&1&-2\cr 1&5&-1\cr -1&4&1} \right] \)第3列-1*第2列  \( G=\left[ \matrix{3&1&-2\cr 1&5&-1\cr -2&-1&2} \right] \)
\( U=\left[ \matrix{1&0&0\cr 0&1&0\cr -5&0&1} \right] \)第3列-1*第2列  \( U=\left[ \matrix{1&0&0\cr
0&1&0\cr -5&-1&1} \right] \)
\( G( 2,2)=5>G(3,3)=2 \)
\( G=\left[ \matrix{3&1&-2\cr 1&5&-1\cr -2&-1&2} \right] \)第2行和第3行交換  \( G=\left[ \matrix{3&-2&1\cr 1&-1&5\cr -2&2&-1} \right] \)
\( G=\left[ \matrix{3&-2&1\cr 1&-1&5\cr -2&2&-1} \right] \)第2列和第3列交換  \( G=\left[ \matrix{3&-2&1\cr -2&2&-1\cr 1&-1&5} \right] \)
\( U=\left[ \matrix{1&0&0\cr 0&1&0\cr -5&-1&1} \right] \)第2列和第3列交換  \( U=\left[ \matrix{1&0&0\cr -5&-1&1\cr 0&1&0} \right] \)
------------------------
\( \displaystyle G( 1,2)/G(1,1)=-\frac{2}{3}>\frac{1}{2}\)  ,  \( \displaystyle round(\frac{-2}{3})=-1\)
\( G=\left[ \matrix{3&-2&1\cr -2&2&-1\cr 1&-1&5} \right] \)第2行--1*第1行  \( G=\left[ \matrix{3&1&1\cr -2&0&-1\cr 1&0&5} \right] \)
\( G=\left[ \matrix{3&1&1\cr -2&0&-1\cr 1&0&5} \right] \)第2列--1*第1列  \( G=\left[ \matrix{3&1&1\cr
1&1&0\cr 1&0&5} \right] \)
\( U=\left[ \matrix{1&0&0\cr -5&-1&1\cr 0&1&0} \right] \)第2列--1*第1列  \( U=\left[ \matrix{1&0&0\cr -4&-1&1\cr 0&1&0} \right] \)
\( G( 1,1)=3>G(2,2)=1\)
\( G=\left[ \matrix{3&1&1\cr 1&1&0\cr 1&0&5} \right] \)第1行和第2行交換  \( G=\left[ \matrix{1&3&1\cr 1&1&0\cr 0&1&5} \right] \)
\( G=\left[ \matrix{1&3&1\cr 1&1&0\cr 0&1&5} \right] \)第1列和第2列交換  \( G=\left[ \matrix{1&1&0\cr 1&3&1\cr 0&1&5} \right] \)
\( U=\left[ \matrix{1&0&0\cr -4&-1&1\cr 0&1&0} \right] \)第1列和第2列交換  \( U=\left[ \matrix{
-4&-1&1\cr 1&0&0\cr 0&1&0} \right] \)
------------------------
\( \displaystyle G( 1,2)/G(1,1)=1>\frac{1}{2}\)  ,  \( \displaystyle round(1)=1\)
\( G=\left[ \matrix{1&1&0\cr 1&3&1\cr 0&1&5} \right] \)第2行-1*第1行  \( G=\left[ \matrix{1&0&0\cr
1&2&1\cr 0&1&5} \right] \)
\( G=\left[ \matrix{1&0&0\cr 1&2&1\cr 0&1&5} \right] \)第2列-1*第1列  \( G=\left[ \matrix{1&0&0\cr
0&2&1\cr 0&1&5} \right] \)
\( U=\left[ \matrix{-4&-1&1\cr 1&0&0\cr 0&1&0} \right] \)第2列-1*第1列  \( U=\left[ \matrix{-4&-1&1\cr 5&1&-1\cr 0&1&0} \right] \)
------------------------
\( G=\left[ \matrix{1&0&0\cr 0&2&1\cr 0&1&5} \right]\),\( \displaystyle \frac{vi.vj}{vi^2}=\left[\matrix{\displaystyle *&0&0\cr *&*&\frac{1}{2}\cr *&*&*}\right]\),向量長度\(=\left[ \matrix{1\cr \sqrt{2}\cr \sqrt{5}} \right] \)
所有向量符合(1)|vi.vj/vi.vi|≦1/2，(2)∥vi∥≦∥vj∥，1≦i<j≦n兩個條件，程式結束
化簡後向量\( V=U.V=\left[ \matrix{-4&-1&1\cr 5&1&-1\cr 0&1&0} \right] \left[\matrix{1&1&1\cr -1&0&2\cr 3&5&6}\right]=\left[ \matrix{0&1&0\cr 1&0&1\cr -1&0&2} \right]\)
[color=red](%o3)[/color]　\( \left[ \matrix{0&1&0\cr 1&0&1\cr -1&0&2} \right] \)



－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－



[color=green]以行向量運算的Jacobi方法[/color]
[color=red](%i1)[/color]
[color=blue]JacobibyColumn(V):=block
([End,G,n:length(V),U,i,j],
G:transpose(V).V,
U:ident(n),
do
(End:true,
for i:1 thru n-1 do
  (for j:i+1 thru n do
     (q:G[i,j]/G[i,i],
      if abs(q)>1/2 then
        (print("G(",i,",",j,")/G(",i,",",i,")=",q,">",1/2,"  ,  round(",q,")=",round(q)),
         print("G=",G,"  第",j,"行-",round(q),"*第",i,"行  G=",G:columnop(G,j,i,round(q))),
         print("G=",G,"  第",j,"列-",round(q),"*第",i,"列  G=",G:rowop(G,j,i,round(q))),
         print("U=",U,"  第",j,"行-",round(q),"*第",i,"行  U=",U:columnop(U,j,i,round(q))),
         End:false
        ),
      if G[i,i]>G[j,j] then
        (print("G(",i,",",i,")=",G[i,i],">G(",j,",",j,")=",G[j,j]),
         print("G=",G,"  第",i,"行和第",j,"行交換  G=",G:columnswap(G,i,j)),
         print("G=",G,"  第",i,"列和第",j,"列交換  G=",G:rowswap(G,i,j)),
         print("U=",U,"  第",i,"行和第",j,"行交換  U=",U:columnswap(U,i,j)),
         End:false
        )
     )
    ),
   if End=true then
     (print("G=",G,",",vi.vj/vi.vi,"=",genmatrix(lambda([i,j],if i<j then G[i,j]/G[i,i] else "*"),n,n),
             ",向量長度=",genmatrix(lambda([i,j],sqrt(G[i,i])),n,1)),
      print("所有向量符合(1)|vi.vj/vi.vi|≦1/2，(2)∥vi∥≦∥vj∥，1≦i<j≦n兩個條件，程式結束"),
      print("化簡後向量V=V.U=",V,U,"=",V.U),
      return(V.U)
     ),
    print("------------------------")
  )
)$[/color]

[color=green]行向量的lattice[/color]
[color=red](%i2)[/color]
[color=blue]V:matrix([1,-1,3],
             [1,0,5],
             [1,2,6]);[/color]
[color=red](%o2)[/color]　\( \left[ \matrix{1&-1&3\cr 1&0&5\cr 1&2&6} \right] \)

[color=red](%i3)[/color]　[color=blue]JacobibyColumn(V);[/color]
\( \displaystyle G(1,3)/G(1,1)=\frac{14}{3}>\frac{1}{2} \)  ,  \( \displaystyle round(14/3)=5 \)
\( G=\left[ \matrix{3&1&14\cr 1&5&9\cr 14&9&70} \right] \)  第3行-5*第1行  \( G=\left[ \matrix{3&1&-1\cr 1&5&4\cr 14&9&0} \right] \)
\( G=\left[ \matrix{3&1&-1\cr 1&5&4\cr 14&9&0} \right] \)  第3列-5*第1列  \( G=\left[ \matrix{3&1&-1\cr 1&5&4\cr -1&4&5} \right] \)
\( U=\left[ \matrix{1&0&0\cr 0&1&0\cr 0&0&1} \right] \)  第3行-5*第1行  \( U=\left[ \matrix{1&0&-5\cr 0&1&0\cr 0&0&1} \right] \)
\( \displaystyle G(2,3)/G(2,2)=\frac{4}{5}>\frac{1}{2} \)  ,  \( \displaystyle round(4/5)=1\)
\( G=\left[ \matrix{3&1&-1\cr 1&5&4\cr -1&4&5} \right] \)  第3行-1*第2行  \( G=\left[ \matrix{3&1&-2\cr 1&5&-1\cr -1&4&1} \right] \)
\( G=\left[ \matrix{3&1&-2\cr 1&5&-1\cr -1&4&1} \right] \)  第3列-1*第2列  \( G=\left[ \matrix{3&1&-2\cr 1&5&-1\cr -2&-1&2} \right] \)
\( U=\left[ \matrix{1&0&-5\cr 0&1&0\cr 0&0&1} \right] \)  第3行-1*第2行  \( U=\left[ \matrix{1&0&-5\cr 0&1&-1\cr 0&0&1} \right] \)
\( G(2,2)=5>G(3,3)=2\)
\( G=\left[ \matrix{3&1&-2\cr 1&5&-1\cr -2&-1&2} \right] \)  第2行和第3行交換  \( G=\left[ \matrix{3&-2&1\cr 1&-1&5\cr -2&2&-1} \right] \)
\( G=\left[ \matrix{3&-2&1\cr 1&-1&5\cr -2&2&-1} \right] \)  第2列和第3列交換  \( G=\left[ \matrix{3&-2&1\cr -2&2&-1\cr 1&-1&5} \right] \)
\( U=\left[ \matrix{1&0&-5\cr 0&1&-1\cr 0&0&1} \right] \)  第2行和第3行交換  \( U=\left[ \matrix{
1&-5&0\cr 0&-1&1\cr 0&1&0} \right] \)
------------------------
\( \displaystyle G(1,2)/G(1,1)=-\frac{2}{3}>\frac{1}{2} \)  ,  \( \displaystyle round(-\frac{2}{3})=-1\)
\( G=\left[ \matrix{3&-2&1\cr -2&2&-1\cr 1&-1&5} \right] \)  第2行--1*第1行  \( G=\left[ \matrix{3&1&1\cr -2&0&-1\cr 1&0&5} \right] \)
\( G=\left[ \matrix{3&1&1\cr -2&0&-1\cr 1&0&5} \right] \)  第2列--1*第1列  \( G=\left[ \matrix{3&1&1\cr 1&1&0\cr 1&0&5} \right] \)
\( U=\left[ \matrix{1&-5&0\cr 0&-1&1\cr 0&1&0} \right] \)  第2行--1*第1行  \( U=\left[ \matrix{1&-4&0\cr 0&-1&1\cr 0&1&0} \right] \)
\( G(1,1)=3>G(2,2)=1\)
\( G=\left[ \matrix{3&1&1\cr 1&1&0\cr 1&0&5} \right] \)  第1行和第2行交換  \( G=\left[ \matrix{1&3&1\cr 1&1&0\cr 0&1&5} \right] \)
\( G=\left[ \matrix{1&3&1\cr 1&1&0\cr 0&1&5} \right] \)  第1列和第2列交換  \( G=\left[ \matrix{
1&1&0\cr 1&3&1\cr 0&1&5} \right] \)
\( U=\left[ \matrix{1&-4&0\cr 0&-1&1\cr 0&1&0} \right] \)  第1行和第2行交換  \( U=\left[ \matrix{
-4&1&0\cr -1&0&1\cr 1&0&0} \right] \)
------------------------
\( \displaystyle G(1,2)/G(1,1)=1>\frac{1}{2} \)  ,  \( round(1)=1\)
\( G=\left[ \matrix{1&1&0\cr 1&3&1\cr 0&1&5} \right] \)  第2行-1*第1行  \( G=\left[ \matrix{1&0&0\cr 1&2&1\cr 0&1&5} \right] \)
\( G=\left[ \matrix{1&0&0\cr 1&2&1\cr 0&1&5} \right] \)  第2列-1*第1列  \( G=\left[ \matrix{1&0&0\cr 0&2&1\cr 0&1&5} \right] \)
\( U=\left[ \matrix{-4&1&0\cr -1&0&1\cr 1&0&0} \right] \)  第2行-1*第1行  \( U=\left[ \matrix{-4&5&0\cr -1&1&1\cr 1&-1&0} \right] \)
------------------------
\( G=\left[ \matrix{1&0&0\cr 0&2&1\cr 0&1&5}\right],\frac{vi.vj}{vi^2}=\left[ \matrix{*&0&0\cr *&*&\frac{1}{2}\cr *&*&*}\right] \),向量長度\( =\left[ \matrix{1\cr \sqrt{2}\cr \sqrt{5}} \right] \)
所有向量符合(1)|vi.vj/vi.vi|≦1/2，(2)∥vi∥≦∥vj∥，1≦i<j≦n兩個條件，程式結束
化簡後向量\( V=V.U=\left[ \matrix{1&-1&3\cr 1&0&5\cr 1&2&6} \right] \left[ \matrix{-4&5&0\cr -1&1&1\cr 1&-1&0} \right]=\left[ \matrix{0&1&-1\cr 1&0&0\cr 0&1&2} \right]\)
[color=red](%o3)[/color]　\( \left[ \matrix{0&1&-1\cr 1&0&0\cr 0&1&2} \right] \)

[[i] 本帖最後由 bugmens 於 2017-12-31 13:54 編輯 [/i]]

查看完整版本: 用maxima學密碼學－Lattice Reduction