LLLアルゴリズム(LLL algorithm)とは、格子の基底を、Gram–Schmidt の係数の絶対値が $\frac12$ 以下で隣り合う射影の長さが急に減らない基底(LLL 簡約基底)に取り替えるアルゴリズムで、1982 年に Lenstra・Lenstra・Lovász が多項式の因数分解のために導入した。階数 $n$ の格子の簡約基底の最初のベクトル $b_1$ は、最短の $0$ でない格子の点の長さ $\lambda_1$ について $\|b_1\|\le2^{(n-1)/2}\lambda_1$ をみたす。整数の基底で長さの 2 乗が $B$ 以下なら、基底の入れ替えは $\frac{n(n-1)}{2}\log_{4/3}B$ 回以下で、全体は多項式時間で終わる。最小多項式の推定、連立の Diophantus 近似、格子暗号の解析に使われる。
前提知識: 格子(群), Gram–Schmidtの直交化, 行列式
LLLアルゴリズム(LLL algorithm)は、格子の基底を、短くて直交に近い基底(LLL 簡約基底)に取り替える多項式時間のアルゴリズムである。1982 年に A. K. Lenstra、H. W. Lenstra, Jr.、L. Lovász が有理数係数の多項式の因数分解のために導入した(LLL82)。得られる基底の最初のベクトルは、最短の $0$ でない格子の点の長さの $2^{(n-1)/2}$ 倍以内に収まる。
格子の最短ベクトルを正確に求める問題は(乱択の帰着のもとで)NP 困難であることが知られているが(Pei16 p. 8)、多くの応用では「指数関数的な定数倍以内の短いベクトル」で足りる。代数的数の最小多項式の推定、連立の Diophantus 近似、多項式の因数分解、ナップサック型の暗号の解読、格子暗号 の安全性の評価などがその例である。
この記事では簡約基底を定義し、その性質(thm-lll-props)と、アルゴリズムが整数の基底について多項式回の算術演算で止まること(thm-lll-time)を証明する。途中に現れる整数の桁数の評価のうち分子の部分は証明しない。
$\mathbb{R}^m$ の 1 次独立なベクトル $b_1,\dots,b_n$ について
$$
L=\mathcal{L}(b_1,\dots,b_n)=\{z_1b_1+\dots+z_nb_n:z_i\in\mathbb{Z}\}
$$
を 格子、$(b_1,\dots,b_n)$ をその 基底、$n$ を 階数 という。$\lambda_1(L)$ で $L$ の $0$ でない点の長さ(Euclid ノルム $\|x\|$)の最小値を表す。同じ格子の 2 つの基底は、行列式が $\pm1$ の整数行列で互いに移り合う。
Gram–Schmidt のデータ:$b_1^*=b_1$、
$$
b_i^*=b_i-\sum_{j< i}\mu_{ij}b_j^*,\qquad \mu_{ij}=\frac{b_i\cdot b_j^*}{b_j^*\cdot b_j^*}\quad(1\le j< i\le n)
$$
とおき、$B_i=\|b_i^*\|^2$ と書く(Gram–Schmidtの直交化)。$b_i^*$ は $b_i$ を $b_1,\dots,b_{i-1}$ の張る空間の直交補空間へ射影したもので、$b_1^*,\dots,b_n^*$ は直交し、$b_1,\dots,b_i$ と同じ空間を張る。
$d_i=\det(b_j\cdot b_l)_{1\le j,l\le i}$($d_0=1$)とおく。$b_1,\dots,b_i$ を行とする行列は、対角成分が $1$ の下三角行列と $b_1^*,\dots,b_i^*$ を行とする行列の積なので
$$
d_i=B_1B_2\cdots B_i>0
$$
である。$d(L)=\sqrt{d_n}=\|b_1^*\|\cdots\|b_n^*\|$ を $L$ の 行列式 という。基底を取り替えても Gram 行列は $P^{\mathsf T}GP$($\det P=\pm1$)に変わるだけなので、$d(L)$ は基底によらない。$m=n$ なら $d(L)=\lvert\det(b_1,\dots,b_n)\rvert$ である。
格子の基底 $(b_1,\dots,b_n)$ が LLL 簡約されている(LLL 簡約基底 である)とは、次の 2 条件が成り立つことをいう。
$b_i^*+\mu_{i,i-1}b_{i-1}^*$ と $b_{i-1}^*$ は、$b_i$ と $b_{i-1}$ を $b_1,\dots,b_{i-2}$ の張る空間の直交補空間へ射影したものである。Lovász 条件は「$b_{i-1}$ と $b_i$ を入れ替えても、射影の長さが $\frac34$ 倍より短くはならない」ことを表す。定数 $\frac34$ は $\frac14<\delta<1$ をみたす任意の $\delta$ に替えてよい(rem-lll-delta)。
この記事の主張が使える条件をまとめる。
$n$ は階数、$d(L)$ は行列式、$(b_1,\dots,b_n)$ は LLL 簡約基底とする(最後の 3 行は入力の整数の基底について)。
| 主張 | 条件 | 結論 | 根拠 |
|---|---|---|---|
| Hadamard の不等式 | 任意の基底 | $d(L)\le\prod_i\|b_i\|$ | prf-lll-props |
| 長さの比較 | 簡約基底、$j\le i$ | $\|b_j\|^2\le2^{i-1}B_i$ | thm-lll-props |
| 長さの積 | 簡約基底 | $\prod_i\|b_i\|\le2^{n(n-1)/4}d(L)$ | thm-lll-props |
| 第 1 ベクトルと行列式 | 簡約基底 | $\|b_1\|\le2^{(n-1)/4}d(L)^{1/n}$ | thm-lll-props |
| 第 1 ベクトルと最短ベクトル | 簡約基底 | $\|b_1\|\le2^{(n-1)/2}\lambda_1(L)$ | thm-lll-props |
| 1 次独立な短いベクトル | 簡約基底、$x_1,\dots,x_t\in L$ が 1 次独立 | $\|b_j\|^2\le2^{n-1}\max_i\|x_i\|^2$($j\le t$) | 証明しない:LLL82 (1.12)(p. 518) |
| 一般の $\delta$ | $\frac34$ を $\delta\in(\frac14,1)$ に替える | 上の 5 行の $2$ のべきを同じ指数の $\frac{4}{4\delta-1}$ のべきに替える | 証明しない:長さの比較・長さの積・第 1 ベクトルと行列式の 3 行は LLL82 (1.6) の後の注意(p. 517)、残りの 2 行は LLL82 (1.11)・(1.12) の証明で $2$ を同じく替えて得られる |
| 交換の回数 | 整数の基底、$\|b_i\|^2\le B$ | $\frac{n(n-1)}2\log_{4/3}B$ 以下 | thm-lll-time |
| 算術演算の回数 | 同上、$m=n$ | $O(n^4\log B)$ 回 | thm-lll-time |
| 途中の整数の長さ | 同上 | $O(n\log B)$ ビット | 分母は thm-lll-time、分子は証明しない:LLL82 (1.26)(p. 522) |
ビット演算の回数は、通常の掛け算・割り算を使えば $O(n^6(\log B)^3)$ である(LLL82 (1.26) の後の注意、p. 522。この記事では証明しない)。
$(b_1,\dots,b_n)$ を格子 $L\subset\mathbb{R}^m$ の LLL 簡約基底とする。
1. Lovász 条件とサイズ条件 $\mu_{i,i-1}^2\le\frac14$ から
$$
B_i\ge\Bigl(\tfrac34-\mu_{i,i-1}^2\Bigr)B_{i-1}\ge\tfrac12B_{i-1}\qquad(2\le i\le n)
$$
で、これを繰り返すと $B_j\le2^{i-j}B_i$($j\le i$)を得る。$b_i=b_i^*+\sum_{j< i}\mu_{ij}b_j^*$ で $b_j^*$ は直交するので、サイズ条件から
$$
\|b_i\|^2=B_i+\sum_{j< i}\mu_{ij}^2B_j\le B_i+\frac14\sum_{j=1}^{i-1}2^{i-j}B_i=\frac{2^i+2}{4}B_i\le2^{i-1}B_i
$$
である(最後は $2\le2^i$ による)。よって $j\le i$ なら $\|b_j\|^2\le2^{j-1}B_j\le2^{j-1}2^{i-j}B_i=2^{i-1}B_i$。
2. $b_i^*$ は $b_i$ の直交射影なので $\|b_i^*\|\le\|b_i\|$ で、$d(L)=\prod\|b_i^*\|\le\prod\|b_i\|$(Hadamard の不等式。簡約は使わない)。1 で $j=i$ とすると $\|b_i\|\le2^{(i-1)/2}\|b_i^*\|$ で、掛け合わせると $\prod\|b_i\|\le2^{\sum_i(i-1)/2}d(L)=2^{n(n-1)/4}d(L)$。
3. 1 で $j=1$ とすると $\|b_1\|^2\le2^{i-1}B_i$($1\le i\le n$)。$i=1,\dots,n$ について掛け合わせると $\|b_1\|^{2n}\le2^{n(n-1)/2}d(L)^2$ となり、$2n$ 乗根をとればよい。
4. $x=\sum_ir_ib_i$($r_i\in\mathbb{Z}$)とし、$r_i\ne0$ となる最大の $i$ をとる。$b_l$($l< i$)は $b_1^*,\dots,b_l^*$ の 1 次結合で、$b_i$ の $b_i^*$ の係数は $1$ なので、$x$ を $b_1^*,\dots,b_n^*$ で展開したときの $b_i^*$ の係数は $r_i$ である。直交性から
$$
\|x\|^2\ge r_i^2B_i\ge B_i\ge2^{-(i-1)}\|b_1\|^2\ge2^{-(n-1)}\|b_1\|^2
$$
である(3 つ目は 1 で $j=1$ とした式)。$\square$
4 の論法から、どの基底についても $\lambda_1(L)\ge\min_iB_i^{1/2}$ が分かる。簡約基底では $B_i$ が $i$ とともに急に減らないので、この下界が $\|b_1\|$ と比べられる。
Lovász 条件の $\frac34$ を $\delta\in(\frac14,1)$ に替えると、1 の証明の $\frac12$ は $\delta-\frac14=\frac{4\delta-1}4$ になり、定理の $2$ のべきはすべて同じ指数の $\frac4{4\delta-1}$ のべきに替わる(1〜3 は LLL82 p. 517 の注意にあり、4 は同じ証明で得られる)。$\delta$ を $1$ に近づけると近似の定数は $(\frac43)^{(n-1)/2}$ に近づくが、計算量の評価の $\log_{4/3}$ は $\log_{1/\delta}$ に替わって大きくなる。
入力は基底 $b_1,\dots,b_n$ である。$\lfloor x\rceil$ で $x$ に最も近い整数を表す($x$ が半整数のときはどちらでもよい)。「$b_k$ を $b_l$ で簡約する」とは、$\lvert\mu_{kl}\rvert>\frac12$ のとき $r=\lfloor\mu_{kl}\rceil$ として $b_k\leftarrow b_k-rb_l$ とし、$\mu_{kj}\leftarrow\mu_{kj}-r\mu_{lj}$($j< l$)、$\mu_{kl}\leftarrow\mu_{kl}-r$ と書き換えることをいう。
新しい値に $'$ を付ける。$B_{k-1}'=C$、$B_k'=B_{k-1}B_k/C$、$\mu_{k,k-1}'=\mu B_{k-1}/C$。$j< k-1$ について $\mu_{k-1,j}'=\mu_{kj}$、$\mu_{kj}'=\mu_{k-1,j}$。$i>k$ について $\mu_{i,k-1}'=\mu_{i,k-1}\mu_{k,k-1}'+\mu_{ik}B_k/C$、$\mu_{ik}'=\mu_{i,k-1}-\mu_{ik}\mu$。それ以外の $B_i$、$\mu_{ij}$ は変わらない。新しい $b_{k-1}^*$ は元の $b_k$ を $b_1,\dots,b_{k-2}$ の直交補空間へ射影した $b_k^*+\mu b_{k-1}^*$ なので $B_{k-1}'=C$ で、$d_{k-1}=B_{k-1}'\,d_{k-2}$ と $d_k$ が変わらないことから $B_k'$ が出る。
手順のどの時点でも $(b_1,\dots,b_n)$ は $L$ の基底であり、段 2 に入るときには $(b_1,\dots,b_{k-1})$ が(それが張る格子の)LLL 簡約基底になっている。したがって手順が止まれば、出力は $L$ の LLL 簡約基底である。
基底の取り替えは「ある $b_k$ から別の $b_l$ の整数倍を引く」「隣り合う 2 つを入れ替える」の 2 種類で、どちらも行列式 $\pm1$ の整数行列による取り替えなので、$L$ の基底のままである。
$b_k$ を $b_l$($l< k$)で簡約しても、$b_k$ の変化は $b_1,\dots,b_{k-1}$ の張る空間に入るので $b_k^*$ は変わらず、ほかの $b_i$ と、$b_1,\dots,b_{i-1}$ の張る空間も変わらないので、すべての $b_i^*$ と $B_i$ は変わらない。$\mu_{ij}$($i\ne k$)も変わらない。$b_l\cdot b_j^*$ は $j< l$ で $\mu_{lj}B_j$、$j=l$ で $B_l$、$j>l$ で $0$ なので、$\mu_{kj}$ の書き換えは手順の式のとおりで、$\mu_{kj}$($j>l$)は変わらない。とくに $b_l$ での簡約の後 $\lvert\mu_{kl}\rvert\le\frac12$ となり、その後の $l'< l$ での簡約でもこれは保たれる。
段 2 に入るときの主張を、手順を進める回数についての帰納法で示す。$k=2$ では $(b_1)$ は自明に簡約されている。段 3 で入れ替えたとき:$b_1,\dots,b_{k-2}$ と $b_1^*,\dots,b_{k-2}^*$ は変わらないので、$(b_1,\dots,b_{k-2})$ は簡約されたままで、新しい $k$ は $k-1$(または $2$)である。段 4 に進んだとき:段 4 の簡約は $\mu_{k,k-1}$ と $B_i$ を変えないので、段 3 で確かめた Lovász 条件 $B_k\ge(\frac34-\mu_{k,k-1}^2)B_{k-1}$ はそのまま成り立ち、段 2・4 の簡約で $\lvert\mu_{kj}\rvert\le\frac12$($j< k$)となる。$(b_1,\dots,b_{k-1})$ の条件は変わらないので、$(b_1,\dots,b_k)$ が簡約されている。$k=n$ で止まるときは $(b_1,\dots,b_n)$ が簡約されている。$\square$
$b_1,\dots,b_n\in\mathbb{Z}^m$ を 1 次独立とし、$B\ge2$ を $\|b_i\|^2\le B$($1\le i\le n$)をみたす数とする。
1. $D=d_1d_2\cdots d_{n-1}$ とおく。$d_i$ は整数の成分をもつ正定値な Gram 行列の行列式なので、正の整数である。最初は $B_j\le\|b_j\|^2\le B$ なので $d_i=B_1\cdots B_i\le B^i$、$D\le B^{n(n-1)/2}$ である。
段 2・4 の簡約はすべての $B_i$ を変えない(prf-lll-correct)ので $D$ を変えない。段 3 で $b_{k-1}$ と $b_k$ を入れ替えると、$i\le k-2$ の $d_i$ は変わらず、$i\ge k$ の $d_i$ は同じベクトルの組の Gram 行列の行列式なので変わらない。$d_{k-1}=d_{k-2}B_{k-1}$ だけが変わり、新しい $B_{k-1}$ は $B_k+\mu_{k,k-1}^2B_{k-1}<\frac34B_{k-1}$(段 3 の条件)である。よって入れ替えのたびに $D$ は $\frac34$ 倍未満になる。$D\ge1$ なので $1\le(\frac34)^sB^{n(n-1)/2}$、すなわち $s\le\frac{n(n-1)}2\log_{4/3}B$ である。
段 3 を通るたびに、入れ替えなら $k$ は $1$ 減るか変わらず、前進なら $1$ 増える。$k$ は $2$ から始まり、$n$ で前進したときに止まるので、前進の回数 $a$ は $a\le(n-1)+s$ をみたす。段 2 を通る回数は $a+s\le2s+n-1$ で有限である。
2. 準備の Gram–Schmidt は $O(n^3)$ 回の演算である。段 2 は $b_k$ の $n$ 成分と $\mu_{kj}$ の書き換えで $O(n)$ 回、段 3 の交換も書き換えの式から $O(n)$ 回、段 4 は高々 $k-2$ 回の簡約で $O(n^2)$ 回である。1 から段 2〜4 を通る回数は $O(n^2\log B)$ なので、全体で $O(n^3+n^2\cdot n^2\log B)=O(n^4\log B)$ 回である。
3. $d_i$ は入れ替えでしか変わらず、そのとき減るので、いつも最初の値 $B^i$ 以下である。$b_i^*=b_i-\sum_{j< i}\lambda_{ij}b_j$ と書くと、$b_i^*\perp b_l$($l< i$)から $\lambda_{ij}$ は連立方程式 $b_i\cdot b_l=\sum_j\lambda_{ij}\,b_j\cdot b_l$($l< i$)の解で、係数行列の行列式は $d_{i-1}$、成分は整数なので Cramer の公式から $d_{i-1}\lambda_{ij}\in\mathbb{Z}$、よって $d_{i-1}b_i^*\in\mathbb{Z}^m$。さらに $d_j\mu_{ij}=d_j\frac{b_i\cdot b_j^*}{B_j}=d_{j-1}\,b_i\cdot b_j^*=b_i\cdot(d_{j-1}b_j^*)\in\mathbb{Z}$ である。$\square$
分子の側、すなわち途中の $\|b_i\|^2$ と $\lvert\mu_{ij}\rvert$ が $n^2(4B)^n$、$2^{n-1}(nB^{n-1})^{1/2}$ 以下に保たれ、すべての整数が $O(n\log B)$ ビットに収まることは LLL82 の (1.26) の証明(pp. 522–524)にある。この記事では証明しない。これと 2・3 を合わせて、整数の基底の LLL 簡約基底が多項式時間で求まる。
整数でない基底でも手順は止まる。$b_1,\dots,b_i$ の張る格子を $i$ 次元の空間の格子とみると、行列式は $\sqrt{d_i}$ である。辺の長さ $2a$、$a>d_i^{1/(2i)}$ の立方体は体積 $(2a)^i>2^i\sqrt{d_i}$ をもつので、Minkowskiの格子点定理 の系「一般の格子に対する凸体定理」から長さ $\sqrt i\,a$ 以下の $0$ でない点を含む。$a\downarrow d_i^{1/(2i)}$ として $\lambda_1(L)^2\le i\,d_i^{1/i}$、すなわち $d_i\ge(\lambda_1(L)^2/i)^i$ を得る。$D$ は正の定数で下から抑えられ、入れ替えの回数は有限である。ただし回数は $B$ だけでは抑えられない(反例の表)。
$b_1=(11,13)$、$b_2=(14,17)$ に手順を施す。
使う公式:手順の段 2〜4、thm-lll-props。
答え:入れ替え 2 回で $b_1=(2,1)$、$b_2=(-1,2)$ を出力する。$\mu_{21}=0$、$B_1=B_2=5$ で、$d(L)=5$、$\|b_1\|=\sqrt5=\lambda_1(L)$。
$\mu_{21}=\frac{11\cdot14+13\cdot17}{11^2+13^2}=\frac{375}{290}\approx1.293$ なので $r=1$、$b_2\leftarrow(3,4)$。$B_2+\mu_{21}^2B_1=\|b_2\|^2=25<\frac34\cdot290$ なので入れ替えて $(3,4),(11,13)$。$\mu_{21}=\frac{85}{25}=3.4$ で $r=3$、$b_2\leftarrow(11,13)-3(3,4)=(2,1)$。$\|b_2\|^2=5<\frac34\cdot25$ なので入れ替えて $(2,1),(3,4)$。$\mu_{21}=\frac{10}5=2$ で $b_2\leftarrow(3,4)-2(2,1)=(-1,2)$。$\|b_2\|^2=5\ge\frac34\cdot5$ なので $k=n=2$ で止まる。2 次元では $b_2^*+\mu_{21}b_1^*=b_2$ なので、Lovász 条件は $\|b_2\|^2\ge\frac34\|b_1\|^2$ である。
図: 行列式 5 の同じ格子(灰色の点)の 3 つの基底。左は入力 (11,13)、(14,17) で、ほぼ同じ向きの長い 2 本。中は 1 回目の入れ替えの後の (3,4)、(11,13)。右は出力 (2,1)、(-1,2) で、直交する短い 2 本。どの段でも基本平行四辺形の面積は 5 である。
この格子は 格子暗号 の例「良い基底と悪い基底」の格子と同じで、そこでの良い基底 $(2,1),(1,3)$ は $\mu_{21}=1$ なのでサイズ条件をみたさない。
$b_1=(1,1,1)$、$b_2=(-1,0,2)$、$b_3=(3,5,6)$($d(L)=3$)に手順を施す。
使う公式:手順、thm-lll-props の 2・3。
答え:入れ替え 2 回で $(0,1,0)$、$(1,0,1)$、$(-1,0,2)$ を出力する。$B_1=1$、$B_2=2$、$B_3=\frac92$(積 $9=d(L)^2$)、$\mu_{32}=\frac12$、ほかの $\mu_{ij}=0$。$\|b_1\|=1=\lambda_1(L)$ は 3 の上界 $2^{1/2}\cdot3^{1/3}\approx2.0396$ 以下で、長さの積は $\sqrt{10}\approx3.1623$(入力では $\approx32.4037$)と 2 の上界 $2^{3/2}\cdot3\approx8.4853$ 以下である。
$k=2$:$\mu_{21}=\frac13$、$B_2=\frac{14}3\ge(\frac34-\frac19)\cdot3$ で前進。$k=3$:$b_3$ を $b_2$ で簡約して $(4,5,4)$。Lovász 条件が破れるので入れ替えて $(1,1,1),(4,5,4),(-1,0,2)$、$k=2$。$b_2$ を $b_1$ で簡約して $(0,1,0)$、入れ替えて $(0,1,0),(1,1,1),(-1,0,2)$。$b_2\leftarrow(1,0,1)$ で前進、$k=3$ で条件をみたして止まる。
$\alpha=\sqrt2+\sqrt3\approx3.146264370$ の 4 次以下の整数係数の関係を探す。$K=10^8$ とし、$i=0,\dots,4$ について $v_i=(e_i,\lfloor K\alpha^i\rceil)\in\mathbb{Z}^6$($e_i$ は $\mathbb{Z}^5$ の基本ベクトル)を基底とする格子に手順を施す。
使う公式:手順、thm-lll-props の 4。
答え:出力の $b_1=(1,0,-10,0,1,-4)$ から $1-10\alpha^2+\alpha^4\approx0$、すなわち $x^4-10x^2+1$ を得る。これは $\alpha$ の最小多項式である。
$\lfloor K\alpha^i\rceil=10^8,\ 314626437,\ 989897949,\ 3114480645,\ 9798979486$。格子の点 $\sum c_iv_i=(c_0,\dots,c_4,\sum c_i\lfloor K\alpha^i\rceil)$ が短いのは、係数 $c_i$ が小さく $\sum c_i\alpha^i$ が $1/K$ 程度に小さいときである。入れ替えは 24 回。最後の成分 $-4$ は丸めの誤差の和で、$\sum c_i\alpha^i=0$ と矛盾しない。$x^4-10x^2+1$ が $\mathbb{Q}$ 上既約であることは、$\mathbb{Q}(\sqrt2,\sqrt3)$ が 4 次の拡大で $\alpha$ がそれを生成することから分かる(最小多項式)。
格子で整数係数の 1 次関係を探すこの方法は LLL82 p. 525 で述べられている。出力から得た多項式が本当に $\alpha$ を根にもつかは、別に確かめる必要がある(よくある誤り)。
$b_1=(5,0)$、$b_2=(2,4)$ は LLL 簡約基底か。$\lambda_1$ はいくらか。
使う公式:def-lll-reduced、thm-lll-props の 4。
答え:$\mu_{21}=\frac25$、$B_2=16\ge(\frac34-\frac4{25})\cdot25=\frac{59}4$ で簡約されている。一方 $\lambda_1=\|b_2\|=\sqrt{20}\approx4.4721<5=\|b_1\|$ で、$b_1$ は最短ではない。4 の評価 $25\le2\cdot20$ は成り立っている。
thm-lll-props の 4($\|b_1\|\le2^{(n-1)/2}\lambda_1$)と thm-lll-time の 1 について、条件を 1 つだけ外した例を挙げる。
| 主張 | 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|---|
| thm-lll-props の 4 | サイズ条件 | $b_1=(10,0)$、$b_2=(9,1)$:$\mu_{21}=\frac9{10}$、Lovász 条件 $\|b_2\|^2=82\ge75$ はみたす | $\lambda_1=\sqrt2$($b_1-b_2=(1,-1)$)で、$\|b_1\|=10>2^{1/2}\sqrt2=2$。不等式そのものが破れる |
| thm-lll-props の 4 | Lovász 条件 | $b_1=(10,0)$、$b_2=(0,1)$:$\mu_{21}=0$、$B_2=1<75$ | $\lambda_1=1$ で、$\|b_1\|=10>\sqrt2$。不等式そのものが破れる |
| thm-lll-time の 1 | 成分が整数 | $b_1=(1,0)$、$b_2=(0.618034,\ 10^{-6})$(有理数)、$\|b_i\|^2\le1$ なので $B=2$ | 入れ替えが 8 回起こり、上界 $\log_{4/3}2\approx2.41$ を超える。出力の $\|b_1\|^2\approx9.197\times10^{-7}$ |
1 行目:$2$ 次元では Lovász 条件は $\|b_2\|^2\ge\frac34\|b_1\|^2$ で、$81+1=82\ge75$。$\lvert\mu_{21}\rvert=0.9>\frac12$ だけが破れている。2 行目:$\mu_{21}=0$ でサイズ条件はみたし、$B_2=1<\frac34\cdot100$。3 行目:$10^6$ 倍した整数の基底でも入れ替えの回数は同じ(相似変換で $\mu_{ij}$ と $B_i$ の比は変わらない)で 8 回。出力は $10^{-6}(-740,-610)$、$10^{-6}(442,-987)$。$10^6$ 倍した整数の基底なら $B=10^{12}$ で上界は $\log_{4/3}10^{12}\approx96.05$ になり、定理と矛盾しない。$D$ の下界が $B$ でなく $\lambda_1$ で決まるためである(rem-lll-real)。
| 誤り | 正しくは | なぜ |
|---|---|---|
| LLL アルゴリズムは最短ベクトルを求める | 最短の $2^{(n-1)/2}$ 倍以内のベクトルを求める | thm-lll-props の 4、ex-lll-not-shortest |
| 簡約基底はただ 1 つに決まる | 順序や符号を変えても簡約されていることがある | $(2,1),(-1,2)$ と $(-1,2),(2,1)$ はどちらも簡約基底 |
| Lovász 条件は $B_i\ge\frac34B_{i-1}$ | $\mu_{i,i-1}^2B_{i-1}$ の項を含めて $B_i+\mu_{i,i-1}^2B_{i-1}\ge\frac34B_{i-1}$ | def-lll-reduced |
| $b_i^*$ も格子の点である | 一般に格子の点ではない | $(2,0),(1,1)$ の $b_2^*=(0,1)$ は格子に入らない |
| 1 次関係の探索の出力は正しい関係である | 近似の関係にすぎず、別に確かめる | ex-lll-minpoly、$K$ が小さいと偽の関係が出る |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する