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

Algorithm in computational number theory

レンズトラ・レンズトラ・ロヴァース（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削減

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アルゴリズムは整数関係アルゴリズムの中核を成しています。例えば、r =1.618034 が整数係数を持つ未知の二次方程式の（わずかに丸められた）根であると考えられる場合、とで張られる の格子にLLL縮約を適用できます。縮約された基底の最初のベクトルは、これら3つの整数線形結合となり、必然的に の形になります。しかし、このようなベクトルが「短い」のは、a、b、cが小さく、がさらに小さい場合のみです。したがって、この短いベクトルの最初の3つの要素は、を根とする積分二次多項式の係数である可能性が高くなります。この例では、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 縮約基底とする。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}})}$

LLLアルゴリズムの擬似コード

以下の説明は、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 * }; および、最新のb i および b j * 値を使用して、 μ i、j < - InnerProduct( b i、b j * )/InnerProduct( b j *、b j * ); を正規化しません。k < - 2; k <= nの間、jに対してk −1から1までを実行します。if | μ k、j | > 1/2 then 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 base of {b 1 , ..., b n } OUTPUT the compacted base b 1 , b 2 , ..., b n in Z m      

例

Zからの例³

格子基底が の列で与えられるとすると、縮約基底は となり、これはサイズが縮約され、ロヴァース条件を満たし、したがって上述のように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}},}$$

Zからの例[私]⁴

同様に、以下の行列の列によって与えられる複素整数上の基底については、以下の行列の列は 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グラム行列をとる）
• Mapleの機能IntegerRelations[LLL]
• Mathematicaの関数としてLatticeReduce
• 数論ライブラリ（NTL）関数としてLLL
• PARI/GPの機能qflll
• 関数としてのピマトゲンanalysis.get_lll_reduced_lattice
• LLLfpLLLとNTLによって駆動されるSageMath
• Isabelle/HOLは「形式証明アーカイブ」エントリにありますLLL_Basis_Reduction。このコードは効率的に実行可能なHaskellにエクスポートされます。^[11]

参照

• 銅細工師の方法

注記

1. レンストラ、アラスカ州;レンストラ、HWジュニア;ロヴァシュ、L. (1982)。 「有理係数による多項式の因数分解」。数学アンナレン。261 (4 ) : 515–534。CiteSeerX 10.1.1.310.318 。土井：10.1007/BF01457454。hdl :1887/3810。MR  0682664。S2CID 5701340  。 
2. ガルブレイス、スティーブン (2012). 「第17章」.公開鍵暗号の数学.
3. Nguyen, Phong Q.; Stehlè, Damien (2009年9月). 「二次複雑度を持つLLLアルゴリズム」 . SIAM J. Comput . 39 (3): 874– 903. doi :10.1137/070705702 . 2019年6月3日閲覧。
4. Nguyen, Phong Q.; Stehlé, Damien (2009年10月1日). 「低次元格子基底縮約の再考」. ACM Transactions on Algorithms . 5 (4): 1– 48. doi :10.1145/1597036.1597050. S2CID  10583820.
5. オドリズコ、アンドリュー; te Reile、Herman JJ「メルテンス予想の反証」(PDF)。数学に関するジャーナル。357 : 138–160 .土井:10.1515/crll.1985.357.138。S2CID  13016831 。2020 年1 月 27 日に取得。
6. D. Wübben他、「Lattice reduction」、IEEE Signal Processing Magazine、Vol. 28、No. 3、pp. 70-91、2011年4月。
7. D. Simon (2007). 「数論におけるLLLの応用例」(PDF) . LLL+25 会議. カーン, フランス.
8. Regev, Oded. 「コンピュータサイエンスにおける格子：LLLアルゴリズム」（PDF） . ニューヨーク大学. 2019年2月1日閲覧。
9. シルバーマン、ジョセフ. 「数学暗号入門 正誤表」（PDF） .ブラウン大学数学部. 2015年5月5日閲覧。
10. ボスマ、ウィーブ。 「4.LLL」（PDF）。講義ノート。2010 年2 月 28 日に取得。
11. Divasón, Jose (2018). 「LLL基底縮約アルゴリズムの形式化」. Interactive Theorem Proving: 9th International Conference, ITP 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 9–12, 2018, Proceedings . Lecture Notes in Computer Science. Vol. 10895. pp.  160– 177. doi : 10.1007/978-3-319-94821-8_10 . ISBN 978-3-319-94820-1。

参考文献

• ネピアス、ユゲット (1996)。 「ユークリッド環または次数に対する LLL アルゴリズムの一般化」。ボルドーの貴族雑誌。8 (2): 387–396 .土井: 10.5802/jtnb.176。
• コーエン、アンリ (2000).計算代数的数論講座. GTM. 第138巻. Springer. 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。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Lenstra–Lenstra–Lovász_lattice_basis_reduction_algorithm&oldid=1320099903"