Lenstra-Lenstra-Lovász 格子基底縮小アルゴリズム

レンストラ・レンストラ・ロヴァース（LLL）格子基底簡約アルゴリズムは、1982 年にArjen Lenstra、Hendrik LenstraおよびLászló Lovászによって発明された多項式時間の 格子簡約 アルゴリズムです。 ^[1] n次元整数座標を持つ基底が与えられた場合、 の格子L（ R ⁿの離散部分群 ）に対して、LLL アルゴリズムは、 の時間でLLL 簡約（短く、ほぼ直交する）格子基底を計算します。ここで、 はユークリッドノルムの下での最大の長さ、つまり です。^{[2] [3]} ${\displaystyle \mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}}$${\displaystyle d\leq n}$$${\displaystyle {\mathcal {O}}(d^{5}n\log ^{3}B)}$$${\displaystyle B}$${\displaystyle \mathbf {b} _{i}}$${\displaystyle B=\max \left(\|\mathbf {b} _{1}\|_{2},\|\mathbf {b} _{2}\|_{2},\dots ,\|\mathbf {b} _{d}\|_{2}\right)}$

元々の用途は、有理係数を持つ多項式を因数分解し、実数を同時に有理近似し、固定次元で整数線形計画問題を解くための多項式時間アルゴリズムを提供することでした。

LLL 縮小の正確な定義は次のとおりです。基底 が与えられた場合、 そのグラム・シュミット過程の直交基底 と任意の グラム・シュミット係数を 定義します。 $${\displaystyle \mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{n}\},}$$$${\displaystyle \mathbf {B} ^{*}=\{\mathbf {b} _{1}^{*},\mathbf {b} _{2}^{*},\dots ,\mathbf {b} _{n}^{*}\},}$$$${\displaystyle \mu _{i,j}={\frac {\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }},}$$${\displaystyle 1\leq j<i\leq n}$

このとき、 (0.25, 1]に次の式が成り立つような パラメータが存在する場合、基底は LLL 簡約化されます。${\displaystyle B}$${\displaystyle \delta }$

1. (サイズ縮小) の場合。定義により、このプロパティは順序付き基底の長さの縮小を保証します。${\displaystyle 1\leq j<i\leq n\colon \left|\mu _{i,j}\right|\leq 0.5}$
2. (Lovász 条件) k = 2,3,..,n の場合。${\displaystyle \colon \delta \Vert \mathbf {b} _{k-1}^{*}\Vert ^{2}\leq \Vert \mathbf {b} _{k}^{*}\Vert ^{2}+\mu _{k,k-1}^{2}\Vert \mathbf {b} _{k-1}^{*}\Vert ^{2}}$

ここで、パラメータの値を推定することで、基底がどの程度簡約されているかを結論付けることができます。 の値が大きいほど、基底の簡約は強くなります。最初に、A. Lenstra、H. Lenstra、および L. Lovász は、 に対する LLL 簡約アルゴリズムを実証しました。LLL 簡約は に対して明確に定義されていますが、多項式時間の計算量は では に対してのみ保証されることに注意してください。 ${\displaystyle \delta }$${\displaystyle \delta }$${\displaystyle \delta ={\frac {3}{4}}}$${\displaystyle \delta =1}$${\displaystyle \delta }$${\displaystyle (0.25,1)}$

LLL アルゴリズムは、LLL 縮小基底を計算します。4 次元を超える格子に対して基底ベクトルが可能な限り短くなるように基底を計算する効率的なアルゴリズムは知られていません。^[4]ただし、LLL 縮小基底は、最初の基底ベクトルが格子内の最短ベクトルの倍以下であり、2 番目の基底ベクトルも同様に2 番目に連続する最小値以内である、などの絶対的な境界があるという意味で、ほぼ可能な限り短くなります。 ${\displaystyle c_{i}>1}$${\displaystyle c_{1}}$${\displaystyle c_{2}}$

LLLアルゴリズムの初期の成功した応用は、アンドリュー・オドリツコとヘルマン・テ・リーレがメルテンス予想を反証するために使用したことである。^[5]

LLLアルゴリズムは、MIMO検出アルゴリズム^[6]や公開鍵暗号方式の暗号解読（ナップザック暗号、特定の設定によるRSA 、 NTRUEncryptなど）など、数多くの応用が見出されています。このアルゴリズムは、多くの問題の整数解を見つけるために使用できます。^[7]

特に、LLL アルゴリズムは整数関係アルゴリズムの 1 つの中核を形成します。たとえば、 r =1.618034 が整数係数を持つ未知の2 次方程式の (わずかに丸められた)根であると考えられる場合、およびで張られるの格子に LLL 縮約を適用できます。縮約された基底の最初のベクトルは、これら 3 つの整数線形結合になるため、必然的に の形式になります。ただし、このようなベクトルが「短い」のは、 a、b、cが小さく、さらに小さい場合のみです。したがって、この短いベクトルの最初の 3 つの要素は、r を根とする積分 2 次多項式の係数である可能性があります。この例では、LLL アルゴリズムは最短のベクトルを [1, -1, -1, 0.00025] と判定し、実際に根は黄金比、1.6180339887... に等しくなります。${\displaystyle \mathbf {R} ^{4}}$${\displaystyle [1,0,0,10000r^{2}],[0,1,0,10000r],}$${\displaystyle [0,0,1,10000]}$${\displaystyle [a,b,c,10000(ar^{2}+br+c)]}$${\displaystyle ar^{2}+br+c}$${\displaystyle x^{2}-x-1}$

を格子の -LLL 縮小基底とします。LLL 縮小基底の定義から、 に関する他のいくつかの有用な特性を導出できます。 ${\displaystyle \mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{n}\}}$${\displaystyle \delta }$ ${\displaystyle {\mathcal {L}}}$${\displaystyle \mathbf {B} }$

1. 基底の最初のベクトルは最短の非ゼロベクトル:より大きくすることはできません。特に、 の場合、 となります。^[8]${\displaystyle \Vert \mathbf {b} _{1}\Vert \leq (2/({\sqrt {4\delta -1}}))^{n-1}\cdot \lambda _{1}({\mathcal {L}})}$${\displaystyle \delta =3/4}$${\displaystyle \Vert \mathbf {b} _{1}\Vert \leq 2^{(n-1)/2}\cdot \lambda _{1}({\mathcal {L}})}$
2. 基底の最初のベクトルも格子の行列式によって制限されます: 。特に、 の場合、 となります。${\displaystyle \Vert \mathbf {b} _{1}\Vert \leq (2/({\sqrt {4\delta -1}}))^{(n-1)/2}\cdot (\det({\mathcal {L}}))^{1/n}}$${\displaystyle \delta =3/4}$${\displaystyle \Vert \mathbf {b} _{1}\Vert \leq 2^{(n-1)/4}\cdot (\det({\mathcal {L}}))^{1/n}}$
3. 基底のベクトルのノルムの積は、格子の行列式よりもそれほど大きくなることはできません。 とすると、 となります 。${\displaystyle \delta =3/4}$${\textstyle \prod _{i=1}^{n}\Vert \mathbf {b} _{i}\Vert \leq 2^{n(n-1)/4}\cdot \det({\mathcal {L}})}$

以下の説明は、(Hoffstein、Pipher、Silverman 2008、定理6.68)に基づいており、正誤表からの修正が加えられています。^[9]

入力Z mの
    格子基底b 1、b 2、...、b n
    パラメーターδ (1/4 < δ < 1、最も一般的にはδ = 3/4)
手順B * <- GramSchmidt({ b 1、...、b n }) = { b 1 *、...、b n * };  正規化しませんμ i、j <- InnerProduct( b i、b j * )/InnerProduct( b j *、b j * );   最新のb iおよびb j *の値を使用しますk <- 2;
     k <= nの間、jに対してk −1から1までを実行します| μ k、j | > 1/2の場合、b k <- b k − ⌊ μ k、j ⌉ b j ;
               必要に応じてB *および関連するμ i、jを更新します。(素朴な方法では、b i が変わるたびにB * を再計算します: B * <- GramSchmidt({ b 1 , ..., b n }) = { b 1 * , ..., b n * })
             end if end for if InnerProduct( b k * , b k * ) > ( δ − μ 2 k , k −1 ) InnerProduct( b k −1 * , b k −1 * ) then k <- k + 1;
         else 
            Swap b kと  b k −1
    
     
      
           
            
                   
                   
                
        
        
            ;
            必要に応じてB *と関連するμ i、jを更新します 。k <- max( k −1, 2);
         end if end while return B the LLL compacted basis of {b 1 , ..., b n }
 OUTPUT 
    the compacted basis b 1 , b 2 , ..., b n in Z m  
            
    
     

格子基底 がの列で与えられるとすると、 縮小基底は となり 、これはサイズ縮小され、Lovász条件を満たし、したがって上で説明したようにLLL縮小されます。縮小プロセスの詳細についてはW. Bosma. ^[10]を参照してください。 ${\displaystyle \mathbf {b} _{1},\mathbf {b} _{2},\mathbf {b} _{3}\in \mathbf {Z} ^{3}}$$${\displaystyle {\begin{bmatrix}1&-1&3\\1&0&5\\1&2&6\end{bmatrix}}}$$$${\displaystyle {\begin{bmatrix}0&1&-1\\1&0&0\\0&1&2\end{bmatrix}},}$$

同様に、以下の行列の列によって与えられる複素整数上の基底に対して、 以下の行列の列は LLL 縮小基底を与えます。 $${\displaystyle {\begin{bmatrix}-2+2i&7+3i&7+3i&-5+4i\\3+3i&-2+4i&6+2i&-1+4i\\2+2i&-8+0i&-9+1i&-7+5i\\8+2i&-9+0i&6+3i&-4+4i\end{bmatrix}},}$$$${\displaystyle {\begin{bmatrix}-6+3i&-2+2i&2-2i&-3+6i\\6-1i&3+3i&5-5i&2+1i\\2-2i&2+2i&-3-1i&-5+3i\\-2+1i&8+2i&7+1i&-2-4i\\\end{bmatrix}}.}$$

LLLは、

• 機能としてのアラゲリlll_reduction_int
• スタンドアロン実装としてのfpLLL
• FLINT関数fmpz_lll
• 機能としてのGAPLLLReducedBasis
• LLLパッケージ内の関数としてのMacaulay2LLLBases
• マグマは関数としてLLL（LLLGramグラム行列をとる）
• 関数としてのMapleIntegerRelations[LLL]
• Mathematicaの関数としてLatticeReduce
• 数論ライブラリ（NTL）関数としてLLL
• PARI/GPの機能qflll
• 関数としてのピマトゲンanalysis.get_lll_reduced_lattice
• LLLfpLLLとNTLによって駆動されるSageMath
• Isabelle/HOLの「形式証明アーカイブ」エントリLLL_Basis_Reduction。このコードは効率的に実行可能なHaskellにエクスポートされます。^[11]

• 銅細工師の方法

• ネピアス、ユゲット (1996)。 「ユークリッド環または次数に対する LLL アルゴリズムの一般化」。ボルドーの貴族ジャーナル。8 (2): 387–396。土井：10.5802/jtnb.176。
• コーエン、アンリ（2000）。計算代数的数論のコース。GTM。第138巻。シュプリンガー。ISBN 3-540-55640-0。
• ボルウェイン、ピーター（ 2002）。解析と数論における計算エクスカーション。ISBN 0-387-95444-9。
• ルーク、フランクリン・T.喬三正 (2011) 「ピボットされた LLL アルゴリズム」。線形代数とその応用。434 (11): 2296–2307。土井：10.1016/j.laa.2010.04.003。
• ホフスタイン、ジェフリー、ピファー、ジル、シルバーマン、JH (2008)。数学的暗号入門。シュプリンガー。ISBN 978-0-387-77993-5。