基于Seysen算法的新型同步格基規約算法研究

孫全超

(青島科技大學，山東 青島 266000)

格基規約的算法及其應用，是幾何數論及組合數學領域的核心分支。基本研究對象是格點空間，因此也被稱為格點理論。該理論自創立之初就與若干重要數學分支如組合數學、泛函分析等有緊密聯系。尤其是L.Lovász提出著名的Lenstra-Lenstra-Lovász (LLL)算法[1]以來，格基規約在當前很多熱門領域均得到了廣泛而深入的應用。

LLL 算法是首個具有多項式時間復雜度的規約算法，實用價值較高。同時，為進一步滿足各類實際應用需要，一系列高效格基規約算法，如BKZ算法、Seysen算法、Brun算法、對角規約算法[2,10]等也于近年被相繼提出。

當前以LLL算法為代表的主流格基規約算法均以最大限度改進格基矩陣或其對偶格基矩陣的基向量長度為目標。它們的缺點是僅單純考慮給定格基矩陣的性態，并未考慮格基矩陣與其對偶基矩陣的關聯。所以，本文提出來一類基于Seysen算法的新型同步格基規約算法，該算法與傳統LLL算法有本質的區別。而且在一定情況下還要優于傳統的LLL算法。

1 LLL算法與Seysen算法

1.1 LLL算法

1.1.1 LLL算法的思想

Lovasz，Lenstra和Lenstra三人最早提出LLL算法，現在它被應用到整數規劃、密碼學、數論等領域，并起到了許多重要的應用。它用到的是格矩陣A的一種QRZ分解：

A=QRZ-1

(1)

其中Q是正交矩陣，R是上三角陣，Z是單模陣。關于單模陣的定義如下：

定義1 如果對于任意非奇異整數矩陣M，有det(M)=1或det(M)=-1則M被稱為單模陣。

由定義，我們可以很容易地得出，非奇異整數矩陣Z是單模陣的充要條件是Z-1也是一個整數矩陣。傳統的LLL算法以DU的形式來計算 ，其中D是一個正定的對角矩陣，而U是單位上三角矩陣。而且R=DU的列構成一組約減基(reducedbasis)關于約減基的定義如下：

定義2 上三角矩陣R=DU的列被稱為一組約減基，若

其中w是一個滿足1/4≤w≤1的參數

把(1)里的R代入，則我們可以得到：

由于Q是正交矩陣，不改變矩陣2-范數；而Z是單模陣，即整數向量間F的雙射，因此上面的問題就等價于

1)條件(1)：矩陣R的對角元素的絕對值是要相對比較大的，在一定意義下對角元比較占優，這樣的性質可以讓矩陣更加穩定，也更接近于一個對角陣。

2)條件(2)：對角線上的元素不會減小得太快，也可以認為是某種意義下的遞增。眾所周知，矩陣末尾的元素越大，需要列舉的次數就越少，因此在作矩陣變換的時候,要盡量把大的元素往矩陣的右下方進行置換。

1.1.2 傳統LLL算法

傳統的LLL算法采用向量及子空間投影的方式表述，形式太過復雜。為便于理解，本文給出和傳統LLL算法數學等價的矩陣形式描述。

設待約減矩陣為A∈Rm×n，則該算法首先運用Gram-Schmidt正交化將A分解如下：

A=QD1/2U

(4)

這里Q∈Rm×n為列正交矩陣，D=diag(d1,d2,…dn)為正對角陣，U=[ui,j]為對角元素全為1的上三角陣。若A的分解(4)滿足下列條件，則A的所有列向量構成L(A)的一組LLL約減基，或等價的把A稱為為一個LLL約減陣。

子過程2(SwapRestore) 對于分解式中的矩陣D和U，按下式更新D中元素并計算ξ：

因此

由上式可知，若當前矩陣U不滿足條件(6)則可通過調用子過程2，使其滿足條件(6)。

分析易知，若算法在有限步內結束，則最終獲得的基矩陣一定滿足LLL約減定義。文獻同時給出了LLL算法的計算復雜度：若初始基矩陣A為整數矩陣，則該算法的復雜度為O(mn3logD)，其中D為A的所有列向量中最長向量的長度。

原始LLL 算法的主要優點為：當初始矩陣為整數或有理數矩陣時，算法的所有操作都是有理數間的四則運算，可實現無誤差運算。因此該算法適用于經典數學理論中的內容，如有理多項式的有理分解等。但對實數或復數型初始基矩陣，由于Gram-Schmidt 正交化及子過程2，均數值計算不穩定，該算法在實際執行過程中會產生較大的計算誤差，不僅計算結果可能不是LLL 的，而且在最壞情況下算法甚至無法終止。

1.2 Seysen算法

1.2.1 對偶格點空間

設L為一個n維實數格點空間，則L的對偶空間L*定義如下：

格點空間與其對偶格點空間有緊密聯系。如下給出兩個基本性質：

(L*)*=L,det(L*)=1/det(L)

給定原格點空間上的一個基矩陣B，則所謂對偶格點基約減算法即為將格點基約減算法作用于對偶基矩陣B*。與前文作用于原格點空間的約減算法類似，利用對偶格點約減算法同樣可以獲得原格點空間中一組約減質量較高的基。設Z*為約法作用于對偶基矩陣B*求得的相應單模變換矩陣，則原格點空間中的對應約減基由下式給出：

1.2.2 Seysen規約

上述優化問題求解十分困難，而Seysen算法提供了一個近似求解的方法。

不難證明相應對偶基矩陣

注意到，B和C其余列向量不變。因此，執行規約操作后，有：

Seysen 算法的核心是：在每次迭代中使S(B) 得以最大程度下降，即求解如下優化問題

不難求出，上述問題最優解為：

算法執行到S(B)無法繼續下降為止。

易知，若Seysen算法終止，則得到的基矩陣滿足：

Seysen 算法在大量數值仿真中的表現優于基于 LLL 迭代策略的傳統格基規約算法，但對 Seysen 算法的理論分析目前尚無進展。特殊例子表明，算法在最差情形下具有指數時間復雜度。如何對該算法進行松弛變形，在盡量不犧牲規約強度的條件下將計算復雜度改進至多項式時間是對該算法改進的關鍵。

2 基于Seysen算法的新型同步格基規約算法

2.1 對Seysen 算法的改進及分析

當前以 LLL 算法為代表的主流格基規約算法均以最大限度改進格基矩陣或其對偶格基矩陣的基向量長度為目標。它們的缺點是僅單純考慮給定格基矩陣的性態，并未考慮格基矩陣與其對偶基矩陣的關聯。Seysen 算法是當前僅有的一類同步格基規約算法。然而盡管Seysen數值表現優異，但其計算復雜度方面的分析目前尚無任何理論結果。大部分情形下該算法表現優異，但個別情形下該算法效率較低。在最壞情況下，具有指數階時間復雜度。

Seysen算法是基于正交測量，S(B)盡管基本矩陣和其雙重基礎矩陣,注意兼顧但它不是直觀的幾何意義。新算法打算采用更明顯的幾何意義類型向量正交測量：

作為新型格基規約算法的計算依據。新算法的設計思路為：在每次迭代初始時，設計一類貪婪策略選擇基矩陣 B 的列向量bi,bj并選擇合理整數步長λ對bj作尺度規約將其更新為bj=bj-λbi，以使得該次迭代結束后正交度量W1(B)或W2(B)得以最大程度下降。新算法期望具有多項式計算復雜度。首先給出新型規約基定義如下：

2.2 改進型Seysen 規約算法的計算復雜度分析

由Cauchy-Schwarz不等式而知：

因此，在算法迭代過程中，上式始終成立。

接下來，給出程序最外層while循環的執行次數上界當同步規約條件不滿足，即

時，執行規約操作，并進入下次while循環。不難得出，當執行完一次規約操作后，得到新的基矩陣B′滿足：

3 數值結果比較

本節，我們通過數值實驗比較LLL算法、原Seysen算法和本文提出的改進Seysen算法的規約質量和執行效率，使用軟件為MATLAB 2012b。

在多天線系統中，信道矩陣通常為方陣，其元素服從獨立同分布的標準正態分布。為了求解各類算法的平均規約質量和執行效率，先利用MATLAB生成一系列隨機矩陣，其階數范圍為1～50階。對每個階數，生成1000個測試用隨機矩陣，再分別將LLL算法(w=0.99)，原始Seysen算法、改進Seysen算法(w分別取0.99，0.95，0.9)得到對應的LLL和Seysen規約矩陣。最后，通過統計規約矩陣平均正交度和算法平均cpu執行時間，比較各算法的規約質量和執行效率。

對于各階信道矩陣，經LLL算法、原始Seysen算法和改進Seysen算法作用得到的規約矩陣的平均正交度如圖1。

圖1表明，隨著矩陣階數的增大，各類算法求得的規約矩陣的Seysen正交度S(B)的值越來越高。對各階矩陣，原Seysen算法規約質量最高，改進Seysen算法次之，而LLL算法對格基正交度的改善效果最差。當規約參數w取為0.99時，改進Seysen算法與原Seysen算法規約質量相當，隨著w的減小，改進Seysen算法的對格基正交度的改善效果降低。

圖2比較了各類算法的平均運行時間。該圖表明，隨著矩陣階數的增加，各類算法的平均運行時間逐漸增加。對各階矩陣，LLL算法運行速度最快，改進Seysen算法次之，原Seysen算法最慢。當規約參數w取為0.99時，改進Seysen算法與原Seysen算法運行時間相當，隨著w的減小，改進Seysen算法需要的運行時間逐漸降低。

圖1 LLL算法(w=0.99)、原Seysen算法、改進Seysen算法(w分別取0.99，0.95，0.9)規約矩陣的平均正交度Fig.1 LLL algorithm (w = 0.99),the original Seysen algorithm, improved Seysen algorithm (w,respectively,take 0.99,0.95,0.9) protocol matrix of the average degree of orthogonality

圖2 LLL算法(w=0.99)、原Seysen算法、改進Seysen算法(w分別取0.99，0.95，0.9)的平均運行時間Fig.2 LLL algorithm (w = 0.99),the original Seysen algorithm, improved Seysen algorithm (w,respectively,take 0.99,0.95,0.9) the average run time

數值結果表明，當w=0.99時，改進Seysen算法與原Seysen算法數值表現一致，其規約質量優于LLL算法，但需要的運行時間LLL算法多。隨著規約參數w的減少，改進Seysen算法的運行時間得以改善，但會導致規約質量降低。在實際應用中，應根據實際需要選擇合適的規約參數w。

4 總結

本文首先論述了傳統LLL算法和Seysen算法，其次提出了一種基于Seysen算法的改進型Seysen算法，爾后對比傳統LLL算法、Seysen算法與改進型Seysen算法得出結論：這種改進型Seysen算法不論在算法復雜度，還是在其約減能力方面都要優于傳統LLL算法。既然傳統的LLL算法可以應用到密碼學、信號處理等實際應用中，那么本文提出的新算法也可以勝任。

現在的基于Seysen算法的新型格基約減算法雖然已經給出，但仍存在一定的缺陷。在普通的正交度量檢驗中，本文提出的改進型Seysen算法的規約質量遜于Seysen算法。需要進一步的優化。