格子縮小

数学演算

2次元の格子縮約：黒ベクトルは格子の与えられた基底（青い点で表されている）、赤ベクトルは縮約された基底である。

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

ほぼ直交

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

ベクトルの任意の基底は、列が基底ベクトルである行列で表すことができます。基底ベクトルの数がそれらが占める空間の次元に等しい完全次元の場合、この行列は正方行列であり、基本平行六面体の体積は、この行列 の行列式の絶対値に相当します。ベクトルの数が基底空間の次元より小さい場合、体積は です。与えられた格子 に対して、この体積はどの基底でも同じ（符号は別として）であるため、格子の行列式または格子定数と呼ばれます。 ${\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完全である。^[1]しかし、欠陥を持つ基底を求める多項式時間アルゴリズムが存在する。 ここでcは基底ベクトルの数と基底空間の次元（異なる場合）のみに依存する定数である^[要出典]。これは多くの実用的な応用において十分な解である^[要出典]。 ${\displaystyle \delta (B)\leq c}$

2次元では

たった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:=\left\lfloor {\left\langle u,{\dfrac {v}{||v||^{2}}}\right\rangle }\right\rceil }$ ${\textstyle r:=u-qv}$  ${\textstyle u:=v}$  ${\textstyle v:=r}$

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

アプリケーション

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

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

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

アルゴリズム

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

年	アルゴリズム	実装
1773	2次元格子のラグランジュ縮小
1801	2次元格子のガウス縮約
1850	高次元における格子縮約の基礎を築いたエルミート
1851	ニグリの基礎を築いたエイゼンシュタインの論文
1873	コルキンとゾロタレフがエルミート法を改良 (HKZ)
1874	結晶学における3D格子の販売削減
1896	最短連続ベクトルによるミンコフスキー還元（最大4D）
1928	結晶学における3次元格子のニグリ縮約
1933	セリング法（結晶学）を最適化するドロネー（ドロネ）還元
1982	レンストラ・レンストラ・ロヴァシュの削減	NTL、fplll
1987	ブロック・コルキネ・ゾロタレフ[5]	NTL、fplll
1993	セイセン還元[6]

参考文献

1. Yap, Chee Keng (2000). 「9: 格子縮約とその応用」.アルゴリズム代数の基礎問題. ニューヨーク、オックスフォード: オックスフォード大学出版局. p. 238. ISBN 0-19-512516-9。
2. Nguyen, Phong Q. (2009). 「エルミート定数と格子アルゴリズム」. LLLアルゴリズム. 情報セキュリティと暗号化. ベルリン、ハイデルベルク: Springer Berlin Heidelberg. pp.  19– 69. doi :10.1007/978-3-642-02295-1_2. ISBN 978-3-642-02294-4. ISSN  1619-7100.
3. レンストラ、アラスカ州;レンストラ、HWジュニア;ロヴァシュ、L. (1982)。 「有理係数による多項式の因数分解」。数学アンナレン。261 (4 ) : 515–534。CiteSeerX 10.1.1.310.318 。土井：10.1007/BF01457454。hdl :1887/3810。MR  0682664。S2CID 5701340  。 
4. Lenstra, Jr., HW (1983). 「固定数の変数を持つ整数計画法」.オペレーションズ・リサーチ数学. 8 (4): 538– 548. CiteSeerX 10.1.1.431.5444 . doi :10.1287/moor.8.4.538. 
5. ギョーム・ハンロット;ダミアン・シュテーレ (2008)。 「最悪の場合のエルミート・コルカイン・ゾロタレフ還元格子基底」。arXiv : 0801.3331 [math.NT]。
6. Seysen, Martin (1993年9月). 「格子基底とその逆基底の同時縮約」. Combinatorica . 13 (3): 363– 376. doi :10.1007/BF01202355. S2CID  206791637.

「https://en.wikipedia.org/w/index.php?title=Lattice_reduction&oldid=1320918391」より取得