令v1v2vnRn是n個線性獨立的向量，由這些向量所組成的lattice定義為L=a1v1+a2v2++anvna1a2anZ。

這些線性獨立的向量又稱為lattice L的基底(basis)，而生成lattice L的基底不只一個。例如：
v1=(479)v2=(264)，L1=a1(479)+a2(264)a1a2Z
由v1v2這兩個基底所生成的latticeL1為圖中的格子點。
也可以取u1=(−51)u2=(19)，L2=a1(−51)+a2(19)a1a2Z
由u1u2這兩個基底所生成的latticeL2就和latticeL1一模一樣
因為每一個向量都是另一組基底的線性組合。
(479)=−9(−51)+2(19)(264)=−5(−51)+1(19) 　，　(−51)=1(479)−2(264)(19)=5(479)−9(264) 

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

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

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

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


do{
　if(v1的長度>v2的長度)
　　{v1和v2兩個向量交換}
　t=v1v1v1v2 ;
　if(t!=0)
　　{v2=v2−tv1;}
　}
while(t!=0);

註：x代表離x最接近的整數，例如03=0，08=1，05=0，maxima的指令為round()。


以前面的例子計算v1=(479)，v2=(264)
第1輪
v1=472+92=2290 ，v2=262+42=692 
v1的長度大於v2的長度，將兩個向量交換，v1=(264)，v2=(479)
計算(264)(264)(264)(479)=2626+442647+49=6921258≈181
t=181=2
t不等於0，v2=(479)−2(264)=(−51)

第2輪
v1=262+42=692 ，v2=(−5)2+12=26 
v1的長度大於v2的長度，將兩個向量交換，v1=(−51)，v2=(264)
計算(−51)(264)(−51)(−51)=−526+14(−5)(−5)+11=26−126≈−484
t=−484=−5
t不等於0，v2=(264)−(−5)(−51)=(19)

第3輪
v1=(−5)2+12=26 ，v2=12+92=82 
v1的長度小於v2的長度，兩個向量不交換。
計算(−51)(19)(−51)(−51)=(−5)1+19(−5)(−5)+11=426≈015
t=015=0
t等於0程式結束，化簡後的向量為u1=(−51)，u2=(19)。



要化簡的向量
(%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
v1=(3159)，v2=(3770)
第1輪
v1=312+592=4442 ，v2=372+702=6269 
v1的長度小於v2的長度，兩個向量不交換
計算(3159)(3159)(3159)(3770)=3131+59593137+5970=44425277≈118
\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 編輯 ]