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)} $

圖出自https://en.wikipedia.org/wiki/Lattice_reduction

這兩組基底我們比較偏好$ 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);

註：$ \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) $。

要化簡的向量
(%i1)
v1:[47,9];
v2:[26,4];
(%o1)　[47,9]
(%o2)　[26,4]

(%i3)
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])
      )
   )
  )$
(%i4)　[u1,u2]:GaussianReduction(v1,v2);
(%o4)　[ [-5,1],[1,9] ]

化簡後的向量
(%i5)
u1;
u2;
(%o5)　[-5,1]
(%o6)　[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 $　　　　　註：這本書採用$ \lceil\; -0.5 \rfloor\;=-1 $的定義
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才對。

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

作者: bugmens 時間: 2014-5-7 21:03

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

附加檔案：2DimensionLatticeReduction.ggb

作者: 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);

以下兩個證明取自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正交化
http://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process
設$ \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 $。都是拿大數字去減掉某個倍數的小數字，減完的結果會比原本的小數字還小。

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

令$ 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^* $向量會彼此互相垂直。
http://en.wikipedia.org/wiki/Gram-Schmidt

若$ 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 $。
可到http://perso.ens-lyon.fr/damien.stehle/fplll/fplll-doc.html　搜尋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
http://home.ie.cuhk.edu.hk/~wkshum/wordpress/?p=442

我再將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] $

(%i1)
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)
)$

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

(%i3)　LLL(v);
(%o3)　$ \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，再執行
(%i4)
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]);
(%o4)　$ \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] $

(%i5)　LLL(v);
(%o5)　$ \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] $

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

作者: bugmens 時間: 2014-6-2 18:10

上一篇程式碼我再加入許多print指令，將中間運算的過程印出來，整個演算法簡單講就是檢查有沒有符合Size condition，沒有符合的就向量相減，讓向量長度更短一點，再檢查有沒有符合Lovász condition，沒有符合的就將較短的向量上移一列，就像氣泡排序法會將數字小的往上移，而LLL演算法執行結果第一列就是整個lattice中長度較短的向量。
此次三維lattice的範例我取自wiki，維度較小所需要的步驟比較少，另外四維lattice你可以執行看看，執行的步驟就多很多。
http://en.wikipedia.org/wiki/Len ... reduction_algorithm
$ \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} $)。

(%i1)
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)
)$
(%i2)
LLL(matrix([1,1,1],
         [-1,0,2],
         [3,5,6]));
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] $
(%o2)　$ \left[ \matrix{0 & 1 & 0 \cr 1 & 0 & 1 \cr -1 & 0 & 2} \right] $

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

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

作者: 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 $

(%i1)
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))
  )$

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

(%i3)　HadamardRatio(B);
(%o3)　0.45238570005998

(%i4)
B:matrix([0,1,0],
      [1,0,1],
      [-1,0,2]);
(%o4)　$ \left[ \matrix{0 & 1 & 0 \cr 1 & 0 & 1 \cr -1 & 0 & 2} \right] $

(%i5)　HadamardRatio(B);
(%o5)　0.98259319385269

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

(%i7)　HadamardRatio(B);
(%o7)　0.57976460724516

(%i8)
B:matrix([2,3,1,1],
      [3,-1,1,3],
      [-2,2,6,-1],
      [-4,1,-4,3]);
(%o8)　$ \left[ \matrix{2 & 3 & 1 & 1 \cr 3 & -1 & 1 & 3 \cr -2 & 2 & 6 & -1 \cr -4 & 1 & -4 & 3} \right] $

(%i9)　HadamardRatio(B);
(%o9)　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 $

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

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

(%i3)　OrthogonalityDefect(B):
(%o3)　10.80123449734644

(%i4)
B:matrix([0,1,0],
      [1,0,1],
      [-1,0,2]);
(%o4)　$ \left[ \matrix{0 & 1 & 0 \cr 1 & 0 & 1 \cr -1 & 0 & 2} \right] $

(%i5)　OrthogonalityDefect(B);
(%o5)　1.05409255338946

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

(%i7)　OrthogonalityDefect(B);
(%o7)　8.851017548063775

(%i8)
B:matrix([2,3,1,1],
      [3,-1,1,3],
      [-2,2,6,-1],
      [-4,1,-4,3]);
(%o8)　$ \left[ \matrix{2 & 3 & 1 & 1 \cr 3 & -1 & 1 & 3 \cr -2 & 2 & 6 & -1 \cr -4 & 1 & -4 & 3} \right] $

(%i9)　OrthogonalityDefect(B);
(%o9)　1.402223508157669

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

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

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

有介紹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
https://www.youtube.com/watch?v=4ulHOV8iLls

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

作者: 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方法差不多，只有一些小地方略有修改。

修改的部分	原本的LLL	integral LLL
Gram–Schmidt正交化	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^ $ 　　} 　}	$ 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}} $　//計算下一個分母　}
Size condition	$ \displaystyle \|\; u_{ij} \|\; \le \frac{1}{2} $　$ 1 \le j<i \le n $	$ \displaystyle \Bigg\vert\; \frac{u_{ij}}{d_j} \Bigg\vert\; \le \frac{1}{2} $　$ 1 \le j<i \le n $
Lovász condition	$ \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 $	$ 4d_{i-2}\cdot d_{i} \ge 3d_{i-1}^2-4u_{i,i-1}^2 $　$ 1<i \le n $

maxima程式碼有修改的地方我用紅色標示出來。
(%i1)
integralLLL(v):=block
  (vstar:copymatrix(v),
m:length(v),
mu:zeromatrix(m,m),
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])
   ),
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 ]/d[ i ]),
      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)
         )
      ),
   if 4*d[k-2]*d[k]>=3*d[k-1]^2-4*mu[k][k-1]^2 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-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])
         ),
      print("更新μ=",mu," v*=",vstar),
      if k>2 then
         (print("退回上一列  k值",k,"=>",k-1),
         k:k-1
         )
      )
   ),
  print("結束,結果v=",v)
)$

(%i2)
integralLLL(matrix([1,1,1],
         [-1,0,2],
         [3,5,6]));
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] $
(%o2)　$ \left[ \matrix{0 & 1 & 0\cr 1 & 0 & 1\cr -1 & 0 & 2} \right] $

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

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

Number-theoretic Algorithms in Cryptography第140頁
7.4. The Schnorr-Euchner algorithm and an integral LLL algorithm
原論文有的證明，這裡也有。
http://books.google.com.tw/books ... e&q&f=false

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

作者: 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程式碼有修改的地方我用紅色標示出來。
(%i1)
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)
         )
      ),
   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),

         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)
)$

書上第一個例子
(%i2)
DeepInsertionLLL(matrix([9,2,7],
                     [8,6,1],
                     [3,2,6]));
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
(%o2)　$ \left[ \matrix{3 & -2 & -5 \cr 6 & 0 & 1 \cr 2 & 6 & 0} \right] $

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

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

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

書上第一個例子：$ \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程式碼一直有錯誤，而我找不出錯誤在哪裡，所以我將我目前所寫的程式碼公布出來，看有沒有網友能幫我除錯。

115.6.19補充，利用claude修正程式碼

maxima的go無法跳出while do迴圈	maxima和c/c++的round執行結果不一致
虛擬碼的Goto 99雖然maxima也有對應的go指令但實際使用時go無法從while do跳出來(出現do loop: 'go' not within 'block': 99錯誤訊息) MLLL():=block( x:1, 99, while x<5 do (x:x+1, if x=3 then (go(99)) else (print("x=",x)) ) )$ MLLL(); $x=2$ do loop: 'go' not within 'block': 99 #0: MLLL() -- an error. To debug this try: debugmode(true);	maxima的$round(-2.5)=-2$ c/c++的$round(-2.5)=-3$ 在第二個範例$\left[\matrix{4&-1\cr5&4\cr-2&-4}\right]$ 以maxima的round執行結果$\left[\matrix{-1&1\cr2&1\cr0&0}\right]$ 和書上執行結果不一致$\left[\matrix{-1&1\cr1&2\cr0&0}\right]$

當時我使用startagain變數取代Goto 99，但程式沒寫好導致無法得到正確結果，改用claude修正程式碼如下。

Example 7.2. If $n=1$ in MLLL, then MLLL performs the version of the Euclidean algorithm in which remainders under division are chosen to have minimum absolute value. For example, suppose that $c_1=36,c_2=84,$ and $c_3=100$. Table 8.7.1 summarizes the changes in the values of $b_1,b_2,$ and $b_3$ during the execution of MLLL$(c_1,c_2,c_3;b_1,b_2,b_3)$. The fourth column indicates the "places" in the procedure at which the changes occur.

Table 8.7.1

$b_1$	$b_2$	$b_3$	Place
$\matrix{36\cr36\cr12\cr12\cr12\cr12\cr4\cr4}$	$\matrix{84\cr12\cr36\cr0\cr100\cr4\cr12\cr0}$	$\matrix{100\cr100\cr100\cr100\cr0\cr0\cr0\cr0}$	$\matrix{　\cr2\cr5\cr2\cr4\cr2\cr5\cr4}$

Example 7.3. Now let us consider an example in $\mathbb{Z}^2$. Let $c_1=(4,-1),c_2=(5,4),$ and $c_3=(-2,-4)$. Table 8.7.2 shows the changes in the values of $b_1,b_2,$ and $b_3$ in the execution of MLLL.

Table 8.7.2

$b_1$	$b_2$	$b_3$	Place
$\matrix{(4, -1)\cr(4, -1)\cr(4, -1)\cr(4, -1)\cr(-1, 1)\cr(-1, 1)\cr(-1, 1)\cr(-1, 1)\cr(-1, 1)\cr(-1, 1)}$	$\matrix{(5, 4)\cr(1, 5)\cr(1, 5)\cr(-1, 1)\cr(4, -1)\cr(1, 2)\cr(1, 2)\cr(-1, 1)\cr(0, 0)\cr(1, 2)}$	$\matrix{(-2, -4)\cr(-2, -4)\cr(-1, 1)\cr(1, 5)\cr(1, 5)\cr(1, 5)\cr(-1, 1)\cr(1, 2)\cr(1, 2)\cr(0, 0)}$	$\matrix{　\cr2\cr2\cr5\cr5\cr2\cr2\cr5\cr2\cr4}$

Example 7.4. Our last example is in $\mathbb{Z}^3$. Suppose the input to MLLL consists of the rows of the matrix $\begin{bmatrix} 48 & -124 & 292 \\ 171 & -142 & 141 \\ -291 & 254 & -277 \end{bmatrix}$.
Then the computation proceeds as shown in Table 8.7.3.

Table 8.7.3

$b_1$	$b_2$	$b_3$	Place
$\matrix{(48, -124, 292)\cr(48, -124, 292)\cr(123, -18, -151)\cr(123, -18, -151)\cr(123, -18, -151)\cr(123, -18, -151)\cr(51, -30, 5)\cr(51, -30, 5)\cr(51, -30, 5)\cr(51, -30, 5)\cr(51, -30, 5)\cr(-12, 20, -40)\cr(-12, 20, -40)\cr(-12, 20, -40)\cr(-12, 20, -40)\cr(-12, 20, -40)\cr(18, -8, -6)\cr(18, -8, -6)\cr(18, -8, -6)\cr(18, -8, -6)\cr(18, -8, -6)\cr(18, -8, -6)\cr(18, -8, -6)}$	$\matrix{(171, -142, 141)\cr(123, -18, -151)\cr(48, -124, 292)\cr(171, -142, 141)\cr(171, -142, 141)\cr(51, -30, 5)\cr(123, -18, -151)\cr(21, 42, -161)\cr(21, 42, -161)\cr(192, -100, -20)\cr(-12, 20, -40)\cr(51, -30, 5)\cr(39, -10, -35)\cr(39, -10, -35)\cr(-18, 52, -126)\cr(18, -8, -6)\cr(-12, 20, -40)\cr(39, -10, -35)\cr(3, 6, -23)\cr(3, 6, -23)\cr(-18, 8, 6)\cr(0, 0, 0)\cr(3, 6, -23)}$	$\matrix{(-291, 254, -277)\cr(-291, 254, -277)\cr(-291, 254, -277)\cr(-291, 254, -277)\cr(51, -30, 5)\cr(171, -142, 141)\cr(171, -142, 141)\cr(171, -142, 141)\cr(192, -100, -20)\cr(21, 42, -161)\cr(21, 42, -161)\cr(21, 42, -161)\cr(21, 42, -161)\cr(-18, 52, -126)\cr(39, -10, -35)\cr(39, -10, -35)\cr(39, -10, -35)\cr(-12, 20, -40)\cr(-12, 20, -40)\cr(-18, 8, 6)\cr(3, 6, -23)\cr(3, 6, -23)\cr(0, 0, 0)}$	$\matrix{　\cr2\cr5\cr2\cr2\cr5\cr5\cr2\cr2\cr5\cr2\cr5\cr2\cr2\cr5\cr2\cr5\cr5\cr2\cr2\cr5\cr2\cr4}$

不使用maxima內建指令round(-5/2)=-2，書上需要round(-5/2)=-3，所以另外寫ROUND指令
(%i1)　ROUND(x):=if x>=0 then floor(x+1/2) else ceiling(x-1/2)$

(%i2)
ADJUST_MU(m,p):=block
(if abs(mu[m,p])>1/2 then
(r:ROUND(mu[m,p]),/*r:round(mu[m,p]),*/
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])
)
)$

(%i3)
MLLL(c):=block
([bstar,s,h,k,mu,b,ZeroVector,H,i,t,m,nu,B,C,restart],
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,
/* 修正3: 外層while不再用startagain=false限制，改用restart局部旗標 */
while i<=s 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 ],
   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]),
   B[ i ]:bstar[ i ].bstar[ i ],
   if i=1 then
      (i:2)
   else  /*i>1*/
      (t:i,       m:i,
      restart:false,  /* 修正3: 每次進入i>1區塊重設restart */
      while m<=t and restart=false do  /* 修正1+2: P4後立即退出內層while */
         (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  /* 修正1: P4與P5互斥 */
               (if m<s then
                  ([b[m],b[s]]:[b[s],b[m]],  print("P 4",b)),
               s:s-1,                i:m,
               restart:true  /* 修正2: 設旗標讓內層while退出 */
               )
            else  /*b[m]不為零向量，才執行Lovász交換(P5)*/
               (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),
               if B[m-1]=0 then  (t:m-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])
                  ),
               if m>2 then (m:m-1)
               )
            )/*C<3/4B[m-1]*/
         ),/*While m<=t and restart=false*/
      /* 修正3: restart=true時不遞增i，讓外層while從i=m重新開始(模擬Goto 99) */
      if restart=false then (i:i+1)
      )/* i>1 */
   )/* b[ i ]#0 */
),
return(b)
)$

(%i5)
c:matrix([36],
            [84],
            [100])$
MLLL(c);
$P2\left[\matrix{36\cr12\cr100}\right]$
$P5\left[\matrix{12\cr36\cr100}\right]$
$P2\left[\matrix{12\cr0\cr100}\right]$
$P4\left[\matrix{12\cr100\cr0}\right]$
$P2\left[\matrix{12\cr4\cr0}\right]$
$P5\left[\matrix{4\cr12\cr0}\right]$
$P2\left[\matrix{4\cr0\cr0}\right]$
(%o5)　$\left[\matrix{4\cr0\cr0}\right]$

(%i7)
c:matrix([4,-1],
         [5,4],
         [-2,-4])$
MLLL(c);
$P2$ $\left[\matrix{4&-1\cr 1&5\cr -2&-4}\right]$
$P2$ $\left[\matrix{4&-1\cr 1&5\cr -1&1}\right]$
$P5$ $\left[\matrix{4&-1\cr -1&1\cr 1&5}\right]$
$P2$ $\left[\matrix{4&-1\cr -1&1\cr 1&5}\right]$
$P5$ $\left[\matrix{-1&1\cr 4&-1\cr 1&5}\right]$
$P2$ $\left[\matrix{-1&1\cr 1&2\cr 1&5}\right]$
$P2$ $\left[\matrix{-1&1\cr 1&2\cr -1&1}\right]$
$P5$ $\left[\matrix{-1&1\cr -1&1\cr 1&2}\right]$
$P2$ $\left[\matrix{-1&1\cr 0&0\cr 1&2}\right]$
$P4$ $\left[\matrix{-1&1\cr 1&2\cr 0&0}\right]$
$P2$ $\left[\matrix{-1&1\cr 1&2\cr 0&0}\right]$
(%o7)　$\left[\matrix{-1&1\cr 1&2\cr 0&0}\right]$

(%i9)
c:matrix([48,-124,292],
         [171,-142,141],
         [-291,254,-277])$
MLLL(c);
$P2 \begin{bmatrix} 48 & -124 & 292 \\ 123 & -18 & -151 \\ -291 & 254 & -277 \end{bmatrix}$
$P5 \begin{bmatrix} 123 & -18 & -151 \\ 48 & -124 & 292 \\ -291 & 254 & -277 \end{bmatrix}$
$P2 \begin{bmatrix} 123 & -18 & -151 \\ 171 & -142 & 141 \\ -291 & 254 & -277 \end{bmatrix}$
$P2 \begin{bmatrix} 123 & -18 & -151 \\ 171 & -142 & 141 \\ 51 & -30 & 5 \end{bmatrix}$
$P5 \begin{bmatrix} 123 & -18 & -151 \\ 51 & -30 & 5 \\ 171 & -142 & 141 \end{bmatrix}$
$P2 \begin{bmatrix} 123 & -18 & -151 \\ 51 & -30 & 5 \\ 171 & -142 & 141 \end{bmatrix}$
$P5 \begin{bmatrix} 51 & -30 & 5 \\ 123 & -18 & -151 \\ 171 & -142 & 141 \end{bmatrix}$
$P2 \begin{bmatrix} 51 & -30 & 5 \\ 21 & 42 & -161 \\ 171 & -142 & 141 \end{bmatrix}$
$P2 \begin{bmatrix} 51 & -30 & 5 \\ 21 & 42 & -161 \\ 192 & -100 & -20 \end{bmatrix}$
$P5 \begin{bmatrix} 51 & -30 & 5 \\ 192 & -100 & -20 \\ 21 & 42 & -161 \end{bmatrix}$
$P2 \begin{bmatrix} 51 & -30 & 5 \\ -12 & 20 & -40 \\ 21 & 42 & -161 \end{bmatrix}$
$P5 \begin{bmatrix} -12 & 20 & -40 \\ 51 & -30 & 5 \\ 21 & 42 & -161 \end{bmatrix}$
$P2 \begin{bmatrix} -12 & 20 & -40 \\ 39 & -10 & -35 \\ 21 & 42 & -161 \end{bmatrix}$
$P2 \begin{bmatrix} -12 & 20 & -40 \\ 39 & -10 & -35 \\ -18 & 52 & -126 \end{bmatrix}$
$P5 \begin{bmatrix} -12 & 20 & -40 \\ -18 & 52 & -126 \\ 39 & -10 & -35 \end{bmatrix}$
$P2 \begin{bmatrix} -12 & 20 & -40 \\ 18 & -8 & -6 \\ 39 & -10 & -35 \end{bmatrix}$
$P5 \begin{bmatrix} 18 & -8 & -6 \\ -12 & 20 & -40 \\ 39 & -10 & -35 \end{bmatrix}$
$P2 \begin{bmatrix} 18 & -8 & -6 \\ -12 & 20 & -40 \\ 39 & -10 & -35 \end{bmatrix}$
$P2 \begin{bmatrix} 18 & -8 & -6 \\ -12 & 20 & -40 \\ 39 & -10 & -35 \end{bmatrix}$
$P5 \begin{bmatrix} 18 & -8 & -6 \\ 39 & -10 & -35 \\ -12 & 20 & -40 \end{bmatrix}$
$P2 \begin{bmatrix} 18 & -8 & -6 \\ 3 & 6 & -23 \\ -12 & 20 & -40 \end{bmatrix}$
$P2 \begin{bmatrix} 18 & -8 & -6 \\ 3 & 6 & -23 \\ -18 & 8 & 6 \end{bmatrix}$
$P5 \begin{bmatrix} 18 & -8 & -6 \\ -18 & 8 & 6 \\ 3 & 6 & -23 \end{bmatrix}$
$P2 \begin{bmatrix} 18 & -8 & -6 \\ 0 & 0 & 0 \\ 3 & 6 & -23 \end{bmatrix}$
$P4 \begin{bmatrix} 18 & -8 & -6 \\ 3 & 6 & -23 \\ 0 & 0 & 0 \end{bmatrix}$
$P2 \begin{bmatrix} 18 & -8 & -6 \\ 3 & 6 & -23 \\ 0 & 0 & 0 \end{bmatrix}$
(%o9)　$\left[\matrix{18&-8&-6\cr 3&6&-23\cr 0&0&0}\right]$
－－－－－－－－－－－－－－－－－－－－
另外http://www.numbertheory.org/calc/krm_calc.html有calc的數學軟體
在http://www.numbertheory.org/calc/下載calc_win32.exe，輸入以下指令(紅色文字)

                     CALC

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

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

4 -1
5  4
-2 -4
VERBOSE? (Y/N)
Enter y or n : n
enter the parameters m1 and n1 (normally 1 and 1) :1 1
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) $結果是正確的但對除錯沒有太大的幫助。

參考資料
MLLL原始的論文
http://www.researchgate.net/prof ... 73c47f645000000.pdf

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

－－－－－－－－－－－－－－－－－－－－
115.7.15新增
在MLLL運算過程中，再加上一個轉換矩陣$H$，$H$是從單位矩陣$I$開始，隨著MLLL化簡,同步記錄了所有列運算。

操作1：大小約化(Size Reduction)	操作2：兩列交換(Swap)	操作3：遇到零向量
將某一列減去另一列的整數倍($b_i\leftarrow b_i-r\cdot b_j$)。將$H$對應的某一列減去另一列的整數倍($H_i\leftarrow H_i-r\cdot H_j$)	當不滿足Lovász條件時，交換相鄰的兩列。將$H$交換對應相鄰的兩列。	將零向量推至矩陣底部，$H$對應的列也推至矩陣底部。

當MLLL執行結束後所得到的化簡矩陣$R$和轉換矩陣$H$，符合$HM=R$且$|\;det(H)|\;=1$。

而這個轉換矩陣$H$可以用來解線性方程組$Ax=b$。關鍵在於將「線性方程組」的問題，轉換為「尋找一組向量之間的整數線性關係（Integer Linear Relation）」。

方法	範例
問題敘述
假設$A$是一個$m\times n$矩陣，$b$則是一個$m \times 1$的行向量，要找出$n\times 1$整數解$x$，滿足$Ax=b$。	$A=\left[\matrix{-8&5&7&-7&3&-7&4&9&-6\cr 1&-2&0&-10&-4&3&8&5&2\cr -7&3&6&5&1&2&5&0&-6\cr -9&-3&4&9&-2&6&1&-10&-9\cr -2&1&-5&-4&3&7&-8&-8&-5\cr -1&1&-8&4&-8&-1&-9&8&6}\right]$，$b=\left[\matrix{3\cr-1\cr-1\cr-7\cr9\cr8}\right]$ 求整數解$x$滿足$Ax=b$。
步驟1：將原問題轉換成求整數線性關係，計算$[A\|b]^T$
$A$矩陣由$n$個長度為$m$的行向量$A_1,A_2,\ldots,A_n$組成，$b$則是一個$m \times 1$的行向量。方程組$Ax=b$可以展開寫成行向量的線性組合形式$x_1 A_1+x_2 A_2+\ldots+x_n A_n=b$ 移項後可得$x_1 A_1+x_2 A_2+\ldots+x_n A_n-1 \cdot b = 0$，求解$Ax=b$其實等同於去尋找一組係數$(x_1,x_2,\ldots,x_n,-1)$，使得這$n+1$個向量的線性組合結果為零向量。將矩陣$A$和矩陣$b$結合在一起，新矩陣大小為$m\times (n+1)$，其中前$n$行是$A$的行向量，最後一行是$b$。 MLLL是以列運算進行Lattice化簡，所以要將新矩陣轉置，就是在對$A_1,A_2,\ldots,A_n$和$b$進行線性組合。	$[A\|b]^T=\left[\matrix{-8&1&-7&-9&-2&-1\cr 5&-2&3&-3&1&1\cr 7&0&6&4&-5&-8\cr -7&-10&5&9&-4&4\cr 3&-4&1&-2&3&-8\cr -7&3&2&6&7&-1\cr 4&8&5&1&-8&-9\cr 9&5&0&-10&-8&8\cr -6&2&-6&-9&-5&6\cr 3&-1&-1&-7&9&8}\right]$
步驟2：將$[A\|b]^T$利用MLLL化簡，得到轉換矩陣$H$
MLLL執行完後產生化簡矩陣$R$和轉換矩陣$H$，滿足$H\cdot [A\|b]^T=R$，其中$H$記錄了所有列變換步驟。	$[R,H]$ :MLLL_H$([A\|b]^T)$ $R=\left[\matrix{0&0&-1&0&0&0\cr 1&0&0&0&0&0\cr 0&0&0&-1&0&0\cr 0&1&0&0&0&0\cr 0&0&0&0&0&1\cr 0&0&0&0&1&0\cr 0&0&0&0&0&0\cr 0&0&0&0&0&0\cr 0&0&0&0&0&0\cr 0&0&0&0&0&0}\right]$
$H=\left[\matrix{-37818&-19676&-85649&14204&43543&-24334&48460&0&0&0\cr -189557&-98622&-429305&71196&218253&-121971&242900&0&-1&0\cr 214507&111603&485811&-80567&-246980&138025&-274871&0&1&0\cr -438519&-228151&-993149&164704&504904&-282166&561922&0&-2&0\cr 440143&228996&996827&-165314&-506774&283211&-564003&0&2&0\cr 622969&324116&1410888&-233982&-717277&400851&-798278&0&3&0\cr 3216146&1673283&7283868&-1207958&-3703021&2069439&-4121200&1&17&0\cr -1489972&-775197&-3374459&559621&1715531&-958726&1909263&0&-7&0\cr -31640&-16463&-71657&11884&36430&-20359&40544&0&0&1\cr -86456&-44981&-195803&32472&99544&-55630&110785&0&0&0}\right]$
步驟3：求得整數解$x$
如果$Ax=b$存在整數解，在化簡矩陣$R$中，必然會出現某一列全為0(因為$x_1A_1+x_2A_2+\ldots+x_nA_n-b=0$)。從$R$矩陣最後一列開始，符合第$i$列全為$0$，$H$矩陣第$i$列第$n+1$行為$\pm1$ (1)該值為$+1$，則整數解$x$為$H$矩陣第$i$行前$n$個數字加上負號。 (2)該值為$-1$，則整數解$x$為$H$矩陣第$i$行前$n$個數字。	$R$矩陣第9行全為$0$，$H$矩陣第9行第$10$行為$+1$ $H[9]=\left[\matrix{-31640&-16463&-71657&11884&36430&-20359&40544&0&0&1}\right]$ 整數解$x$為$H$矩陣第$9$行前$9$個數字加上負號 $x=\left[\matrix{31640&16463&71657&-11884&-36430&20359&-40544&0&0}\right]$

參考資料
Computational Algebraic Number Theory
作者：Michael Pohst
https://books.google.com.tw/book ... 20reduction&f=false
因為程式關係計算出來的轉換矩陣$H$和整數解$x$和書上不同，但都是符合$Ax=b$的解。
$H^t=\begin{pmatrix}
-37818 & -19676 & -85649 & 14204 & 43543 & -24334 & 48460 & 0 & 0 & 0 \\
-386767 & -201227 & -875938 & 145266 & 445318 & -248864 & 495604 & 1 & 0 & 0 \\
-1221509 & -635526 & -2766436 & 458787 & 1406428 & -785976 & 1565244 & 3 & 0 & 0 \\
-1219885 & -634681 & -2762758 & 458177 & 1404558 & -784931 & 1563163 & 3 & 0 & 0 \\
828011 & 430797 & 1875254 & -310993 & -953360 & 532781 & -1061015 & -2 & 0 & 0 \\
-803061 & -417816 & -1818748 & 301622 & 924633 & -516727 & 1029044 & 2 & 0 & 0 \\
-86456 & -44981 & -195803 & 32472 & 99544 & -55630 & 110785 & 0 & 0 & 0 \\
2816502 & 1465368 & 6378727 & -1057851 & -3242880 & 1812269 & -3609071 & -7 & 0 & 0 \\
9467074 & 4925523 & 21440740 & -3555742 & -10900253 & 6091559 & -12131128 & -23 & 1 & 0 \\
-11297648 & -5877935 & -25586565 & 4243288 & 13007950 & -7269435 & 14476828 & 28 & 0 & 1
\end{pmatrix}$，$x=\begin{pmatrix}11297648 \\5877935 \\25586565 \\-4243288 \\-13007950 \\7269435 \\-14476828 \\-28 \\0\end{pmatrix}$

(%i1)　ROUND(x):=if x>=0 then floor(x+1/2) else ceiling(x-1/2)$

(%i2)
ADJUST_MU(m,p):=block
(if abs(mu[m,p])>1/2 then
(/*r:round(mu[m,p]),*/
r:ROUND(mu[m,p]),
b[m]:b[m]-r*b[p],
H[m]:H[m]-r*H[p], /* H 同步更新 */
mu[m,p]:mu[m,p]-r,
for j:1 thru p-1 do
   (mu[m,j]:mu[m,j]-r*mu[p,j])
)
)$

與MLLL完全相同的演算法，新增一個轉換矩陣H
(%i3)
_MLLL_H(c):=block
([bstar,s,h,k,mu,b,ZeroVector,H,i,t,m,nu,B,C,restart],
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,
H:ident(k),/* H 初始化為單位矩陣 */
s:k,
i:1,
/* 修正3: 外層while不再用startagain=false限制，改用restart局部旗標 */
while i<=s do
(if b[ i ]=ZeroVector then
   (if i<s then
      ([b[ i ],b[s]]:[b[s],b[ i ]],
      [H[ i ],H[s]]:[H[s],H[ i ]]    /* H 同步交換 */
      /*,print(" P1",b)*/
      ),
   s:s-1
   )
else  /*b[ i ]不為零向量*/
   (bstar[ i ]:b[ i ],
   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]),
   B[ i ]:bstar[ i ].bstar[ i ],
   if i=1 then
      (i:2)
   else  /*i>1*/
      (t:i,       m:i,
      restart:false,  /* 修正3: 每次進入i>1區塊重設restart */
      while m<=t and restart=false do  /* 修正1+2: P4後立即退出內層while */
         (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  /* 修正1: P4與P5互斥 */
               (if m<s then
                  ([b[m],b[s]]:[b[s],b[m]],
                  [H[m],H[s]]:[H[s],H[m]] /* H 同步交換 */
                  /*print("P 4",b)*/
                  ),
               s:s-1,                i:m,
               restart:true  /* 修正2: 設旗標讓內層while退出 */
               )
            else  /*b[m]不為零向量，才執行Lovász交換(P5)*/
               (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),*/
               [H[m-1],H[m]]:[H[m],H[m-1]], /* H 同步交換(P5也只是換位置) */
               if B[m-1]=0 then  (t:m-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])
                  ),
               if m>2 then (m:m-1)
               )
            )/*C<3/4B[m-1]*/
         ),/*While m<=t and restart=false*/
      /* 修正3: restart=true時不遞增i，讓外層while從i=m重新開始(模擬Goto 99) */
      if restart=false then (i:i+1)
      )/* i>1 */
   )/* b[ i ]#0 */
),
return([b,H])
)$

A.x=b的A矩陣
(%i4)
A:matrix([-8,5,7,-7,3,-7,4,9,-6],
[1,-2,0,-10,-4,3,8,5,2],
[-7,3,6,5,1,2,5,0,-6],
[-9,-3,4,9,-2,6,1,-10,-9],
[-2,1,-5,-4,3,7,-8,-8,-5],
[-1,1,-8,4,-8,-1,-9,8,6]);
(%o4)　$\left[\matrix{-8&5&7&-7&3&-7&4&9&-6\cr
1&-2&0&-10&-4&3&8&5&2\cr
-7&3&6&5&1&2&5&0&-6\cr
-9&-3&4&9&-2&6&1&-10&-9\cr
-2&1&-5&-4&3&7&-8&-8&-5\cr
-1&1&-8&4&-8&-1&-9&8&6}\right]$

A.x=b的b矩陣
(%i5)　b:matrix([3],[-1],[-1],[-7],[9],[8]);
(%o5)　$\left[\matrix{3\cr-1\cr-1\cr-7\cr9\cr8}\right]$

計算[A|b]^T
(%i6)　M:transpose(addcol(A,b));
(%o6)　$\left[\matrix{-8&1&-7&-9&-2&-1\cr
5&-2&3&-3&1&1\cr
7&0&6&4&-5&-8\cr
-7&-10&5&9&-4&4\cr
3&-4&1&-2&3&-8\cr
-7&3&2&6&7&-1\cr
4&8&5&1&-8&-9\cr
9&5&0&-10&-8&8\cr
-6&2&-6&-9&-5&6\cr
3&-1&-1&-7&9&8}\right]$

執行MLLL_H()副程式
(%i7)　[R,H]:MLLL_H(M);
(%o7)　$[\left[\matrix{0&0&-1&0&0&0\cr
1&0&0&0&0&0\cr
0&0&0&-1&0&0\cr
0&1&0&0&0&0\cr
0&0&0&0&0&1\cr
0&0&0&0&1&0\cr
0&0&0&0&0&0\cr
0&0&0&0&0&0\cr
0&0&0&0&0&0\cr
0&0&0&0&0&0}\right]$,$\left[\matrix{-37818&-19676&-85649&14204&43543&-24334&48460&0&0&0\cr
-189557&-98622&-429305&71196&218253&-121971&242900&0&-1&0\cr
214507&111603&485811&-80567&-246980&138025&-274871&0&1&0\cr
-438519&-228151&-993149&164704&504904&-282166&561922&0&-2&0\cr
440143&228996&996827&-165314&-506774&283211&-564003&0&2&0\cr
622969&324116&1410888&-233982&-717277&400851&-798278&0&3&0\cr
3216146&1673283&7283868&-1207958&-3703021&2069439&-4121200&1&17&0\cr
-1489972&-775197&-3374459&559621&1715531&-958726&1909263&0&-7&0\cr
-31640&-16463&-71657&11884&36430&-20359&40544&0&0&1\cr
-86456&-44981&-195803&32472&99544&-55630&110785&0&0&0}\right] ]$

找整數解x
(%i10)
n:length(R)$
ZeroVector:create_list(0,i,1,length(R[1]))$
for i:n thru 1 step -1 do
  (if R[ i ]=ZeroVector and H[i,n]=1 then
   (print("在R[",i,"]全為0，H[",i,",",n,"]=+1，整數解x=",x:-rest(H[ i ],-1))),/*x再加上負號*/
if R[ i ]=ZeroVector and H[i,n]=-1 then
   (print("在R[",i,"]全為0，H",i,",",n,"]=-1，整數解x=",x:rest(H[ i ],-1)))
  )$
在$R[9]$全為$0$，$H[9,10]=+1$，整數解$x=[31640,16463,71657,-11884,-36430,20359,-40544,0,0]$

驗證整數解x是否符合A.x=b
(%i11)　is(A.x=b);
(%o11)　true
－－－－－－－－－－－－－－－－－－－－
115.7.15新增

Example 8.1. Let B be Matrix 8.8.1. This matrix was obtained by forming a product UV, where U was an 18-by-14 matrix, V was a 14-by-18 matrix, and the entries of U and V were chosen randomly from the set ${-2,-1,0,1,2}$. The rank of B is 14.
Matrix 8.8.1
由$18\times14$和$14\times 18$矩陣相乘，可確定矩陣的秩為14。
Matrix 8.8.2
因為當年電腦運算速度較慢，要先將矩陣轉換成Hermite normal form後再執行MLLL加快速度，但Hermite normal form不在本文討論範圍。
Matrix 8.8.3
執行MLLL結果。

Matrix 8.8.1矩陣
(%i12)
c:matrix([13,-1,14,-6,-10,-11,-1,2,-1,-4,-9,-1,2,8,4,3,-6,-8],
[5,12,15,2,-6,-6,5,-4,-10,-10,-3,7,1,-7,9,4,5,-3],
[-10,-3,5,-2,-5,15,1,-11,-8,-2,-13,-9,9,1,5,5,-4,-16],
[-4,3,1,6,-11,11,3,-8,-8,6,-5,6,15,-2,-1,-1,-6,6],
[-2,-3,13,-3,2,-9,-2,-4,-11,-9,2,-4,-2,1,-7,-12,2,8],
[-4,-3,-10,9,10,5,-6,-2,4,-1,0,-5,-10,-2,3,-1,9,8],
[0,1,7,12,-9,-3,7,5,-4,-15,1,2,-2,-10,-5,2,2,3],
[8,-4,-18,-7,7,-1,-4,-2,21,6,10,3,-7,-3,6,13,8,-19],
[7,-3,3,-6,-2,-8,-6,-1,9,-4,0,-5,-12,7,11,-4,8,-10],
[12,10,-5,-4,21,-18,1,3,9,10,5,-9,-21,2,17,2,11,11],
[6,-12,-2,-5,11,1,-4,-11,-1,6,8,-1,-7,-9,7,-14,8,-4],
[5,9,3,-2,16,-13,7,5,0,1,11,-5,-16,-7,10,-4,9,6],
[2,2,-2,-3,6,0,8,-1,3,3,-5,-9,-7,-7,10,9,6,-12],
[0,2,-5,5,0,3,-7,-5,3,-8,4,17,1,-13,4,7,6,-13],
[14,-1,-5,2,2,0,-1,-1,7,1,2,1,-2,3,8,14,-1,-1],
[-6,-3,7,0,-19,4,-4,-3,-6,1,-13,3,13,9,-9,-10,-6,4],
[5,-10,1,1,7,4,-6,-1,-5,-6,12,4,2,3,-3,-2,-10,6],
[-2,9,-3,-18,-3,-12,6,-5,8,11,-3,-4,-4,5,4,0,10,-6]);
(%o12)　$\left[\matrix{13&-1&14&-6&-10&-11&-1&2&-1&-4&-9&-1&2&8&4&3&-6&-8\cr
5&12&15&2&-6&-6&5&-4&-10&-10&-3&7&1&-7&9&4&5&-3\cr
-10&-3&5&-2&-5&15&1&-11&-8&-2&-13&-9&9&1&5&5&-4&-16\cr
-4&3&1&6&-11&11&3&-8&-8&6&-5&6&15&-2&-1&-1&-6&6\cr
-2&-3&13&-3&2&-9&-2&-4&-11&-9&2&-4&-2&1&-7&-12&2&8\cr
-4&-3&-10&9&10&5&-6&-2&4&-1&0&-5&-10&-2&3&-1&9&8\cr
0&1&7&12&-9&-3&7&5&-4&-15&1&2&-2&-10&-5&2&2&3\cr
8&-4&-18&-7&7&-1&-4&-2&21&6&10&3&-7&-3&6&13&8&-19\cr
7&-3&3&-6&-2&-8&-6&-1&9&-4&0&-5&-12&7&11&-4&8&-10\cr
12&10&-5&-4&21&-18&1&3&9&10&5&-9&-21&2&17&2&11&11\cr
6&-12&-2&-5&11&1&-4&-11&-1&6&8&-1&-7&-9&7&-14&8&-4\cr
5&9&3&-2&16&-13&7&5&0&1&11&-5&-16&-7&10&-4&9&6\cr
2&2&-2&-3&6&0&8&-1&3&3&-5&-9&-7&-7&10&9&6&-12\cr
0&2&-5&5&0&3&-7&-5&3&-8&4&17&1&-13&4&7&6&-13\cr
14&-1&-5&2&2&0&-1&-1&7&1&2&1&-2&3&8&14&-1&-1\cr
-6&-3&7&0&-19&4&-4&-3&-6&1&-13&3&13&9&-9&-10&-6&4\cr
5&-10&1&1&7&4&-6&-1&-5&-6&12&4&2&3&-3&-2&-10&6\cr
-2&9&-3&-18&-3&-12&6&-5&8&11&-3&-4&-4&5&4&0&10&-6}\right]$

經MLLL_H(c)化簡可立即得到Matrix 8.8.3結果，不需要再先化簡Hermite normal form再MLLL來加速了
(%i13)　MLLL_H(c);
(%o13)
$[\left[\matrix{0&-1&0&0&-1&-2&0&1&1&0&0&1&0&-2&-1&-1&-1&-2\cr
0&1&1&0&-3&-2&0&-1&1&1&-2&-1&1&1&1&0&-1&-1\cr
-2&1&0&0&2&1&2&0&-2&2&-1&-2&0&-1&0&-1&0&2\cr
-2&2&-1&1&-2&1&-1&0&1&1&-1&1&1&1&-1&-1&2&1\cr
-1&-2&-3&2&0&0&-1&0&2&-1&-1&-1&-1&0&-1&2&-1&1\cr
0&-2&-1&0&0&2&0&1&0&-1&-1&0&-2&1&3&0&-2&0\cr
-1&-2&0&2&-1&2&0&1&-1&-2&-1&-1&0&1&-1&0&-2&2\cr
-1&3&0&0&-1&0&1&2&0&0&0&3&-1&-1&2&-1&1&0\cr
-2&1&1&0&0&1&0&-2&-2&-2&0&0&1&0&0&1&0&0\cr
1&-2&-3&2&0&0&-1&-1&2&2&1&1&1&-2&-2&0&0&1\cr
0&1&0&2&1&-2&-2&0&1&1&0&-1&0&1&2&0&-3&1\cr
1&-1&-2&1&2&2&-2&0&1&0&-2&0&0&0&-1&3&2&-1\cr
-1&1&0&1&0&-1&-1&-1&-1&-1&0&2&-1&-1&0&-2&2&3\cr
0&0&0&-2&-2&-1&1&0&-1&1&-1&2&2&1&-2&0&-2&2\cr
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\cr
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\cr
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\cr
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0}\right],$
\(\left[\matrix{645790&-2095817&-1739381&2461627&2183923&810421&-1832214&-849278&1462227&-2347825&-1596116&2374546&3067484&1567022&1317684&0&0&0\cr
-5349&17360&14408&-20390&-18090&-6713&15177&7035&-12112&19448&13221&-19669&-25409&-12980&-10915&0&0&0\cr
8612409&-27950310&-23196799&32828842&29125316&10807972&-24434845&-11326173&19500606&-31311157&-21286183&31667513&40908695&20898175&17572950&0&0&1\cr
184332&-598221&-496482&702637&623370&231324&-522980&-242414&417372&-670154&-455589&677781&875570&447284&376114&0&0&0\cr
1312928&-4260918&-3536263&5004631&4440043&1647633&-3724998&-1726632&2972793&-4773265&-3244997&4827590&6236374&3185847&2678929&0&0&0\cr
1134188&-3680846&-3054844&4323311&3835585&1423327&-3217885&-1491573&2568084&-4123443&-2803230&4170372&5387368&2752133&2314226&0&0&0\cr
1422220&-4615609&-3830632&5421231&4809645&1784787&-4035078&-1870362&3220257&-5170606&-3515120&5229453&6755508&3451046&2901931&0&0&0\cr
2665909&-8651820&-7180405&10161935&9015535&3345530&-7563633&-3505937&6036275&-9692146&-6588987&9802453&12662997&6468882&5439582&0&0&0\cr
931364&-3022607&-2508552&3550182&3149675&1168797&-2642437&-1224837&2108838&-3386056&-2301934&3424593&4423955&2259974&1900377&0&0&0\cr
28150667&-91358862&-75821457&107304918&95199509&35327122&-79868154&-37020922&63740017&-102344184&-69576384&103508974&133714865&68308133&57439244&0&1&2\cr
-2150276&6978408&5791591&-8196441&-7271775&-2698447&6100696&2827828&-4868755&7817518&5314563&-7906489&-10213755&-5217688&-4387473&0&0&0\cr
-26812140&87014872&72216249&-102202714&-90672901&-33647364&76070531&35260628&-60709266&97477856&66268121&-98587262&-127356904&-65060174&-54708086&0&-1&-2\cr
27395592&-88908379&-73787728&104426720&92646010&34379556&-77725882&-36027925&62030344&-99599046&-67710164&100732593&130128284&66475931&55898574&0&1&2\cr
28961421&-93990050&-78005159&110395361&97941310&36344562&-82168403&-38087147&65575767&-105291755&-71580224&106490091&137565931&70275447&59093528&0&1&2\cr
-55387255&179751216&149180921&-211125545&-187307801&-69507139&157142915&72839741&-125410337&201365157&136893558&-203656914&-263087884&-134398237&-113013382&1&-2&-4\cr
-57950352&188069374&156084409&-220895579&-195975647&-72723647&164414852&76210469&-131213819&210683520&143228437&-213081331&-275262525&-140617643&-118243184&0&-2&-4\cr
8097896&-26280533&-21811001&30867617&27385343&10162294&-22975085&-10649537&18335622&-29440600&-20014527&29775667&38464772&19649699&16523126&0&0&1\cr
4332703&-14061155&-11669774&16515432&14652274&5437240&-12292606&-5697936&9810305&-15751919&-10708587&15931193&20580220&10513389&8840545&0&0&0}\right] ]\)

作者: bugmens 時間: 2015-6-20 08:24

4.改進LLL方法－遞迴LLL

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

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

這個LLL副程式略有修改，參數$ m $代表將第1~m列向量進行LLL運算。
(%i1)
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)
)$

(%i2)
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]);
(%o2)　$ \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] $

(%i3)
for i:2 thru length(B) do
  (B: LLL(B,i),
print(B)
  );
$ \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] $
(%o3)　done

另一個範例出自http://www1.uwindsor.ca/sac2012/system/files/2a_Plantard.pdf
(%i4)
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]);
(%o4)　$ \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] $

(%i5)
for i:2 thru length(B) do
  (B: LLL(B,i),
print(B)
  );
$ \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] $
(%o5)　done

執行結果第三列向量和pdf檔所寫的不一樣，我還以為我的LLL程式出了問題，我還另外用maple再寫一次來測試，結果是相同的。

maple檔下載遞迴LLL1.rar
$ \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] $

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

這個LLL副程式略有修改，參數$ m1,m2 $代表將第m1~m2列向量進行LLL運算。
(%i1)
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)
)$

(%i2)
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]);
(%o2)　$ \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] $

(%i3)
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)
   )
  );
第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] $
(%o4)　done

紅色數字都是執行結果和pdf檔所寫的不一樣的地方，只是再用maple測試，執行結果和我的相同，或許原作者所使用的LLL程式多了其他的設定($ \delta=0.75 $改為$ \delta=0.99 $)

maple下載遞迴LLL2.rar
$ \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
https://thomas-plantard.github.io/pdf/PlaSus10.pdf
簡報檔
https://thomas-plantard.github.io/pdf/talk10-scn.pdf

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

作者: 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值

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

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

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

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

GramSchmit正交化
(%i1)
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)
   )
  )
)$

檢查是否違反Size condition
(%i2)
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)
)
)$

第l列移動到第k列
(%i3)
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)
)$

PotLLL主程式
(%i4)
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)
)$

(%i6)
v:matrix([9,2,7],
            [8,6,1],
            [3,2,6]);
PotLLL(v);
(%o5)　$ \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
(%o6)　$ \left[ \matrix{2&6&0 \cr -3&-2&-6 \cr 6&0&1} \right] $

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

作者: bugmens 時間: 2017-12-30 13:55

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

之前的Gaussian/Lagrange方法針對兩個向量進行化簡
https://math.pro/db/viewthread.php?tid=1876&page=1#pid10232
化簡後的向量符合(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 $兩個條件

(%i1)
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("------------------------")
  )
)$

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

(%i3)　Jacobi(v);
$ \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兩個條件，程式結束

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

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

(%i5)　Jacobi(v);
$ \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兩個條件，程式結束
(%o5)　$ \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方法

原本的Gauss/Lagrange方法

本論文的Gauss/Lagrange方法

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);$

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$

註：說明論文所用的符號
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$。

Jacobi方法以列計算

Jacobi方法以行計算

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$

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$

註：
論文演算法以行向量運算，本文章卻以列向量運算，所以將兩個演算法並列出來，其中第1,11,16,22行有差異。
論文演算法第7行$q=G(i,j)/G(j,j)$會導致lattice尚未化簡完程式就提早結束，更正為$q=G(i,j)/G(i,i)$。

參考資料：
http://www.cas.mcmaster.ca/~qiao/
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.
http://www.cas.mcmaster.ca/~qiao/publications/JQ14.pdf
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.
http://www.cas.mcmaster.ca/~qiao/publications/JQ13.pdf

以列向量運算的Jacobi方法
(%i1)
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("------------------------")
  )
)$

列向量的lattice
(%i2)
V:matrix([1,1,1],
         [-1,0,2],
         [3,5,6]);

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

(%i3)　JacobibyRow(V);
$ \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]$
(%o3)　$ \left[ \matrix{0&1&0\cr 1&0&1\cr -1&0&2} \right] $

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

以行向量運算的Jacobi方法
(%i1)
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("------------------------")
  )
)$

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

(%i3)　JacobibyColumn(V);
$ \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]$
(%o3)　$ \left[ \matrix{0&1&-1\cr 1&0&0\cr 0&1&2} \right] $

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

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

論壇程式使用 Discuz! 6.1.0

\(b_1\)	\(b_2\)	\(b_3\)	Place
\(\matrix{36\cr36\cr12\cr12\cr12\cr12\cr4\cr4}\)	\(\matrix{84\cr12\cr36\cr0\cr100\cr4\cr12\cr0}\)	\(\matrix{100\cr100\cr100\cr100\cr0\cr0\cr0\cr0}\)	\(\matrix{　\cr2\cr5\cr2\cr4\cr2\cr5\cr4}\)

\(b_1\)	\(b_2\)	\(b_3\)	Place
\(\matrix{(4, -1)\cr(4, -1)\cr(4, -1)\cr(4, -1)\cr(-1, 1)\cr(-1, 1)\cr(-1, 1)\cr(-1, 1)\cr(-1, 1)\cr(-1, 1)}\)	\(\matrix{(5, 4)\cr(1, 5)\cr(1, 5)\cr(-1, 1)\cr(4, -1)\cr(1, 2)\cr(1, 2)\cr(-1, 1)\cr(0, 0)\cr(1, 2)}\)	\(\matrix{(-2, -4)\cr(-2, -4)\cr(-1, 1)\cr(1, 5)\cr(1, 5)\cr(1, 5)\cr(-1, 1)\cr(1, 2)\cr(1, 2)\cr(0, 0)}\)	\(\matrix{　\cr2\cr2\cr5\cr5\cr2\cr2\cr5\cr2\cr4}\)

\(b_1\)	\(b_2\)	\(b_3\)	Place
\(\matrix{(48, -124, 292)\cr(48, -124, 292)\cr(123, -18, -151)\cr(123, -18, -151)\cr(123, -18, -151)\cr(123, -18, -151)\cr(51, -30, 5)\cr(51, -30, 5)\cr(51, -30, 5)\cr(51, -30, 5)\cr(51, -30, 5)\cr(-12, 20, -40)\cr(-12, 20, -40)\cr(-12, 20, -40)\cr(-12, 20, -40)\cr(-12, 20, -40)\cr(18, -8, -6)\cr(18, -8, -6)\cr(18, -8, -6)\cr(18, -8, -6)\cr(18, -8, -6)\cr(18, -8, -6)\cr(18, -8, -6)}\)	\(\matrix{(171, -142, 141)\cr(123, -18, -151)\cr(48, -124, 292)\cr(171, -142, 141)\cr(171, -142, 141)\cr(51, -30, 5)\cr(123, -18, -151)\cr(21, 42, -161)\cr(21, 42, -161)\cr(192, -100, -20)\cr(-12, 20, -40)\cr(51, -30, 5)\cr(39, -10, -35)\cr(39, -10, -35)\cr(-18, 52, -126)\cr(18, -8, -6)\cr(-12, 20, -40)\cr(39, -10, -35)\cr(3, 6, -23)\cr(3, 6, -23)\cr(-18, 8, 6)\cr(0, 0, 0)\cr(3, 6, -23)}\)	\(\matrix{(-291, 254, -277)\cr(-291, 254, -277)\cr(-291, 254, -277)\cr(-291, 254, -277)\cr(51, -30, 5)\cr(171, -142, 141)\cr(171, -142, 141)\cr(171, -142, 141)\cr(192, -100, -20)\cr(21, 42, -161)\cr(21, 42, -161)\cr(21, 42, -161)\cr(21, 42, -161)\cr(-18, 52, -126)\cr(39, -10, -35)\cr(39, -10, -35)\cr(39, -10, -35)\cr(-12, 20, -40)\cr(-12, 20, -40)\cr(-18, 8, 6)\cr(3, 6, -23)\cr(3, 6, -23)\cr(0, 0, 0)}\)	\(\matrix{　\cr2\cr5\cr2\cr2\cr5\cr5\cr2\cr2\cr5\cr2\cr5\cr2\cr2\cr5\cr2\cr5\cr5\cr2\cr2\cr5\cr2\cr4}\)

方法	範例
問題敘述
假設\(A\)是一個\(m\times n\)矩陣，\(b\)則是一個\(m \times 1\)的行向量，要找出\(n\times 1\)整數解\(x\)，滿足\(Ax=b\)。	\(A=\left[\matrix{-8&5&7&-7&3&-7&4&9&-6\cr 1&-2&0&-10&-4&3&8&5&2\cr -7&3&6&5&1&2&5&0&-6\cr -9&-3&4&9&-2&6&1&-10&-9\cr -2&1&-5&-4&3&7&-8&-8&-5\cr -1&1&-8&4&-8&-1&-9&8&6}\right]\)，\(b=\left[\matrix{3\cr-1\cr-1\cr-7\cr9\cr8}\right]\) 求整數解\(x\)滿足\(Ax=b\)。
步驟1：將原問題轉換成求整數線性關係，計算\([A\|b]^T\)
\(A\)矩陣由\(n\)個長度為\(m\)的行向量\(A_1,A_2,\ldots,A_n\)組成，\(b\)則是一個\(m \times 1\)的行向量。方程組\(Ax=b\)可以展開寫成行向量的線性組合形式\(x_1 A_1+x_2 A_2+\ldots+x_n A_n=b\) 移項後可得\(x_1 A_1+x_2 A_2+\ldots+x_n A_n-1 \cdot b = 0\)，求解\(Ax=b\)其實等同於去尋找一組係數\((x_1,x_2,\ldots,x_n,-1)\)，使得這\(n+1\)個向量的線性組合結果為零向量。將矩陣\(A\)和矩陣\(b\)結合在一起，新矩陣大小為\(m\times (n+1)\)，其中前\(n\)行是\(A\)的行向量，最後一行是\(b\)。 MLLL是以列運算進行Lattice化簡，所以要將新矩陣轉置，就是在對\(A_1,A_2,\ldots,A_n\)和\(b\)進行線性組合。	\([A\|b]^T=\left[\matrix{-8&1&-7&-9&-2&-1\cr 5&-2&3&-3&1&1\cr 7&0&6&4&-5&-8\cr -7&-10&5&9&-4&4\cr 3&-4&1&-2&3&-8\cr -7&3&2&6&7&-1\cr 4&8&5&1&-8&-9\cr 9&5&0&-10&-8&8\cr -6&2&-6&-9&-5&6\cr 3&-1&-1&-7&9&8}\right]\)
步驟2：將\([A\|b]^T\)利用MLLL化簡，得到轉換矩陣\(H\)
MLLL執行完後產生化簡矩陣\(R\)和轉換矩陣\(H\)，滿足\(H\cdot [A\|b]^T=R\)，其中\(H\)記錄了所有列變換步驟。	\([R,H]\) :MLLL_H\(([A\|b]^T)\) \(R=\left[\matrix{0&0&-1&0&0&0\cr 1&0&0&0&0&0\cr 0&0&0&-1&0&0\cr 0&1&0&0&0&0\cr 0&0&0&0&0&1\cr 0&0&0&0&1&0\cr 0&0&0&0&0&0\cr 0&0&0&0&0&0\cr 0&0&0&0&0&0\cr 0&0&0&0&0&0}\right]\)
\(H=\left[\matrix{-37818&-19676&-85649&14204&43543&-24334&48460&0&0&0\cr -189557&-98622&-429305&71196&218253&-121971&242900&0&-1&0\cr 214507&111603&485811&-80567&-246980&138025&-274871&0&1&0\cr -438519&-228151&-993149&164704&504904&-282166&561922&0&-2&0\cr 440143&228996&996827&-165314&-506774&283211&-564003&0&2&0\cr 622969&324116&1410888&-233982&-717277&400851&-798278&0&3&0\cr 3216146&1673283&7283868&-1207958&-3703021&2069439&-4121200&1&17&0\cr -1489972&-775197&-3374459&559621&1715531&-958726&1909263&0&-7&0\cr -31640&-16463&-71657&11884&36430&-20359&40544&0&0&1\cr -86456&-44981&-195803&32472&99544&-55630&110785&0&0&0}\right]\)
步驟3：求得整數解\(x\)
如果\(Ax=b\)存在整數解，在化簡矩陣\(R\)中，必然會出現某一列全為0(因為\(x_1A_1+x_2A_2+\ldots+x_nA_n-b=0\))。從\(R\)矩陣最後一列開始，符合第\(i\)列全為\(0\)，\(H\)矩陣第\(i\)列第\(n+1\)行為\(\pm1\) (1)該值為\(+1\)，則整數解\(x\)為\(H\)矩陣第\(i\)行前\(n\)個數字加上負號。 (2)該值為\(-1\)，則整數解\(x\)為\(H\)矩陣第\(i\)行前\(n\)個數字。	\(R\)矩陣第9行全為\(0\)，\(H\)矩陣第9行第\(10\)行為\(+1\) \(H[9]=\left[\matrix{-31640&-16463&-71657&11884&36430&-20359&40544&0&0&1}\right]\) 整數解\(x\)為\(H\)矩陣第\(9\)行前\(9\)個數字加上負號 \(x=\left[\matrix{31640&16463&71657&-11884&-36430&20359&-40544&0&0}\right]\)