格子縮小

数学において、格子基底削減の目標は、整数格子基底を入力として与えられたときに、短くほぼ直交するベクトルを持つ基底を見つけることです。これは、実行時間は通常、格子の次元の少なく​​とも指数関数であるさまざまなアルゴリズムを使用して実現されます。

ほぼ直交しているかどうかの尺度として、直交性欠陥があります。これは、基底ベクトルの長さの積と、基底ベクトルが定義する平行六面体の体積を比較します。完全に直交する基底ベクトルの場合、これらの量は同じになります。

ベクトルの任意の特定の基底は、列が基底ベクトルである行列で表すことができます。基底ベクトルの数がそれらが占める空間の次元に等しい完全次元の場合、この行列は正方行列であり、基本的な平行六面体の体積は、単にこの行列 の行列式の絶対値です。ベクトルの数が基底空間の次元より少ない場合、体積は です。与えられた格子 に対して、この体積はどの基底でも同じ (符号を除いて) であり、そのため格子の行列式または格子定数と呼ばれます。 ${\displaystyle n}$ ${\displaystyle B}$${\displaystyle b_{i},i=1,\ldots ,n}$${\displaystyle \det(B)}$${\displaystyle {\sqrt {\det(B^{T}B)}}}$${\displaystyle \Lambda}$${\displaystyle \det(\Lambda )}$ ${\displaystyle d(\Lambda )}$

直交性欠陥は、基底ベクトルの長さを平行六面体の体積で割った積です。

${\displaystyle \delta (B)={\frac {\Pi _{i=1}^{n}\|b_{i}\|}{\sqrt {\det(B^{T}B)}}}={\frac {\Pi _{i=1}^{n}\|b_{i}\|}{d(\Lambda )}}}$

幾何学的定義から、基底が直交する場合に限り、等しいこと がわかります。${\displaystyle \delta (B)\geq 1}$

格子縮約問題が、可能な限り最小の欠陥を持つ基底を見つけることであると定義される場合、問題はNP 困難です ^{[引用が必要]} 。ただし、欠陥を持つ基底を見つける多項式時間アルゴリズムが存在します。ここで cは、基底ベクトルの数と基礎となる空間の次元 (異なる場合) のみに依存する定数です^{[引用が必要]}。これは、多くの実際のアプリケーションで十分なソリューションです^{[引用が必要]}。 ${\displaystyle \delta (B)\leq c}$

2 つのベクトルのみで構成される基底の場合、 2 つの整数の最大公約数を求めるユークリッドの互除法に非常に類似した、単純で効率的な縮約方法があります。ユークリッドの互除法と同様に、この方法は反復的です。各ステップで、2 つのベクトルのうち大きい方のベクトルに、小さい方のベクトルの整数倍を加算または減算して縮約します。

ラグランジュのアルゴリズムまたはラグランジュ・ガウス アルゴリズムとも呼ばれるこのアルゴリズムの疑似コードは次のとおりです。

    入力:格子 の基底。 と仮定し、そうでない場合はそれらを交換します。${\textstyle (u,v)}$${\textstyle L}$${\textstyle ||v||\leq ||u||}$出力:を持つ
    基底。
${\textstyle (u,v)}$${\textstyle ||u||=\lambda _{1}(L),||v||=\lambda _{2}(L)}$

    While :
          # 最も近い整数に丸める
         ${\textstyle ||v||<||u||}$${\textstyle q:=\lfloor {\langle u,{\frac {v}{||v||^{2}}}\rangle }\rceil }$${\textstyle r:=u-qv}$
         ${\textstyle u:=v}$
         ${\textstyle v:=r}$

詳細については ^[1] のラグランジュのアルゴリズムのセクションを参照してください。

格子簡約アルゴリズムは、のスピゴットアルゴリズムの発見など、多くの現代の数論アプリケーションで使用されています。最短基底を決定することはおそらくNP完全問題ですが、LLLアルゴリズム^[2]などのアルゴリズムは、最悪の場合のパフォーマンスを保証しながら、多項式時間で短い（必ずしも最短ではない）基底を見つけることができます。LLL は、公開鍵暗号システムの暗号解読に広く使用されています。 ${\displaystyle \pi}$

整数関係を見つけるために使用される場合、アルゴリズムへの典型的な入力は、関係が求められる要素 (合計がゼロにならないベクトルにペナルティを課すために 大きな正の定数で乗算される) で構成される最後の列のエントリを持つ拡張単位行列で構成されます。${\displaystyle n\times n}$${\displaystyle n}$${\displaystyle w}$

ほぼ直交基底を計算するLLLアルゴリズムは、任意の固定次元での整数計画法が多項式時間で実行できることを示すために使用されました。^[3]

以下のアルゴリズムは格子基底を縮小します。これらのアルゴリズムのいくつかの公開実装もリストされています。