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 於 2015-3-27 09:09 PM 編輯 ]

作者: 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程式碼一直有錯誤，而我找不出錯誤在哪裡，所以我將我目前所寫的程式碼公布出來，看有沒有網友能幫我除錯。

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

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

(%i3)
c:matrix([4,-1],
         [5,4],
         [-2,-4])$
MLLL(c);

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

$ b_1 $	$ b_2 $	$ b_3 $	Place
$ (4,-1) $	$ (5,4) $	$ (-2,-4) $
$ (4,-1) $	$ (1,5) $	$ (-2,-4) $	2
$ (4,-1) $	$ (1,5) $	$ (-1,1) $	2
$ (4,-1) $	$ (-1,1) $	$ (1,5) $	5
$ (-1,1) $	$ (4,-1) $	$ (1,5) $	5
$ (-1,1) $	$ (1,2) $	$ (1,5) $	2
$ (-1,1) $	$ (1,2) $	$ (-1,1) $	2
$ (-1,1) $	$ (-1,1) $	$ (1,2) $	5
$ (-1,1) $	$ (0,0) $	$ (1,2) $	2
$ (-1,1) $	$ (1,2) $	$ (0,0) $	4

另外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) $結果是正確的但對除錯沒有太大的幫助。

參考資料
Computational Algebraic Number Theory
作者：Michael Pohst
https://books.google.com.tw/book ... 20reduction&f=false

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

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

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

作者: 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
\( (4,-1) \)	\( (5,4) \)	\( (-2,-4) \)
\( (4,-1) \)	\( (1,5) \)	\( (-2,-4) \)	2
\( (4,-1) \)	\( (1,5) \)	\( (-1,1) \)	2
\( (4,-1) \)	\( (-1,1) \)	\( (1,5) \)	5
\( (-1,1) \)	\( (4,-1) \)	\( (1,5) \)	5
\( (-1,1) \)	\( (1,2) \)	\( (1,5) \)	2
\( (-1,1) \)	\( (1,2) \)	\( (-1,1) \)	2
\( (-1,1) \)	\( (-1,1) \)	\( (1,2) \)	5
\( (-1,1) \)	\( (0,0) \)	\( (1,2) \)	2
\( (-1,1) \)	\( (1,2) \)	\( (0,0) \)	4