? ? LLL格約減算法由Arjen Lenstra膜廊，Hendrik Lenstra以及László Lovász三人于1982年提出的一種在多項式時間內(nèi)求解格中的近似正交基的算法啸驯。由于格的性質(zhì)，如果能夠通過某種方式求得一個格的正交基法牲，那么求解最近向量問題（CVP）與最短向量問題（SVP）都將是十分容易的慎陵。
? ? 事實上腥刹，在某種情況下，我們可以把LLL算法看作是對Gauss約減算法的一種拓展宴卖，因為Gauss約減算法解決了求解二維格中的一個近似正交基問題滋将，而LLL算法則將這個維度拓展到了維。
LLL格約減算法的定義
? 其中要注意的一點是症昏，對于羅瓦茲條件随闽，其可以有多種表達形式，其另一種同樣常見且正確的表達方式為齿兔。?
? ? 對于LLL約減算法的定義橱脸，用更直白的語言來說，給定一個格的一組基
分苇，
是其經(jīng)過施密特正交化后的一組基添诉，那么我們說，如果對于基
医寿，其滿足以上兩個條件（尺度條件與羅瓦茲條件）栏赴，那么便認為基
是經(jīng)LLL約減后的一組基。
? ? 經(jīng)過LLL格約減算法后得到的一組基有著一些良好的性質(zhì)靖秩，利用這些性質(zhì)我們可以很容易地求解某些問題须眷，例如，通過使用LLL格約減算法可以在一個令密鑰持有者十分不安的時間內(nèi)沟突，破解那些使用基于背包密碼體制問題的密碼系統(tǒng)密鑰花颗。
LLL格約減算法的計算
? ? LLL格約減算法的偽代碼如下所示：
? ? 該算法沒有什么難點，只要按照步驟走惠拭，就可以得到一組LLL的近似正交基扩劝。但是需要注意的是Gram-Shimidt正交化的時機。在實際使用該算法時职辅，并不是在一開始計算一次Gram-Schimidt就可以了棒呛，而是在每一次步驟（這里的步驟指的是k的循環(huán)）的開始，需要重新計算一次當(dāng)前基(v1,v2,v3,...,vn)的Gram-Schimidt正交化基域携。
? ? 考慮到在許多寫LLL算法的博客都沒有給出LLL算法的例子簇秒，我這里便給出一個使用LLL算法的例子，供大家參考秀鞭，該例子來源于Youtube鏈接趋观。
? 問題：給定格扛禽，其一組基
，利用LLL算法求其約減后的一組基皱坛。
