用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。

二維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 編輯 ]

這次我改用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 編輯 ]

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中長度最短的向量。

高維度的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 編輯 ]

上一篇程式碼我再加入許多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 編輯 ]

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 coefficients, 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 編輯 ]

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 編輯 ]

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一書中則擴展成一章的內容，這篇文章的範例及程式碼就是參考這本書而來的。

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 編輯 ]