浮動小数点演算を使用しない新しいLLLアルゴリズムfracLLLの提案
はじめに
格子基底簡約の一つにLLL基底簡約(Lenstra, Lenstra and Lovász, 1982)というものがあります．これを実際にC言語などで実装する際は，普通浮動小数点演算が必要になり，皆さんもご存じの通り浮動小数点演算には必ず誤差が発生してしまいます．そこで，浮動小数点演算による誤差も考慮した数値的に安定したLLL簡約基底を計算するアルゴリズムとしてNguyen and Stehlé，2005による$L^2$アルゴリズムというものが知られています．しかしながら，この$L^2$アルゴリズムも浮動小数点演算を使っているので，数値的に安定しているとは言え高い次元では小さくない誤差が出るかもしれません．
そこで，LLL簡約基底を計算する際に必要となるGram-Schmidtの直交化情報を分母と分子に分けることで整数として情報を持つことで浮動小数点演算を必要としない新しいLLL簡約基底を計算するアルゴリズム，fracLLLアルゴリズムを本記事で提案してみます．
準備
※ 以前の記事 でも少し触れた内容と重複しているものもあります．
記号の準備
本記事で使用する記号は以下の表に従います．
| 記号 | 意味 |
|---|---|
| $\mathbb{Z}$ | 整数全体の集合 |
| $\mathbb{Q}$ | 有理数全体の集合 |
| $\mathbb{R}$ | 実数全体の集合 |
| $\mathrm{M}_n(R)$ | 環$R$上の$n\times n$行列全体の集合 |
| $\boldsymbol{O}_{n, m}$ | $n\times m$の零行列 |
| $\boldsymbol{E}_n$ | $n$次単位行列 |
| $q^{(\text{num})}$, $q^{(\text{den})}$ | $q\in\mathbb{Q}$の分子，及び分母（必ずしも既約分数とは限らない） |
| $\round{\bullet}$ | 実数の四捨五入 |
格子
一次独立な$n$本のベクトル$\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\in\mathbb{R}^n$（これを基底ベクトルと呼ぶ）の整数係数の一次結合全体の集合
$$L=\mathcal{L}(\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n):=\left\lbrace \left.\sum_{i=1}^na_i\boldsymbol{b}_i~\right|~a_1,\ldots.a_n\in\mathbb{Z}\right\rbrace$$
を(完全階数な)格子と呼び，基底ベクトルの組$\{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\}$を基底と呼ぶ．
また，基底ベクトルが全て整数ベクトルであるとき，$L$を整数格子と呼び，本記事では整数格子のみ扱う．
Gram-Schmidtの直交化法
$\{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\}$を$n$次元格子$L$の基底とする．このとき
$$\left\{\begin{aligned}\boldsymbol{b}_1^\star &:= \boldsymbol{b}_1, \\\boldsymbol{b}_i^\star &:= \boldsymbol{b}_i - \sum_{j=1}^{i-1} \mu_{i, j} \boldsymbol{b}_j^\star,~\mu_{i, j}:=\frac{\langle \boldsymbol{b}_i, \boldsymbol{b}_j^\star\rangle}{\| \boldsymbol{b}_j^\star \|^2}~(1 \!\leq\! j \!<\! i \!\leq\! n).\end{aligned}\right.$$
で定義される$\boldsymbol{b}_1^\star,\ldots,\boldsymbol{b}_n^\star$をGram-Schmidtの直交化ベクトル，$\boldsymbol{U}\coloneqq (\mu_{i, j})_{i, j}$をGram-Schmidtの直交化係数行列と呼ぶ．
B1やB2の線形代数学で習うようなGram-Schmidtの直交化法そのものです．
fracLLLの理論的な部分
fracLLLは，LLL格子基底を計算する際に必ず必要となるGram-Schmidtの直交化ベクトルの二乗ノルムやGram-Schmidtの直交化係数行列（この2つをまとめてGram-Schmidtの直交化情報と呼ぶことにします）を分母と分子に分けて整数として扱うことで，浮動小数点演算を一切必要としない新しいアルゴリズムです．
まず，Gram-Schmidtの直交化情報を分母分子に分けるために，次の補題を証明します．
Gram-Schmidtの直交化情報について
$n$次元格子の基底$\{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\}$のGram-Schmidtの直交化ベクトルは，
$$
\boldsymbol{b}_i^\star=\sum_{j=1}^i(-1)^{j+i}\frac{d_{i, j}}{d_{i, i}}\boldsymbol{b}_j
$$
と表すことができる．ただし，$G_{i, j}\coloneqq \langle\boldsymbol{b}_i, \boldsymbol{b}_j\rangle$（これを並べた行列を基底のGram行列と呼ぶ）に対して
$$
d_{i, j}=\det\mqty[
G_{1, 1}\ & \cdots & G_{1, i-1}\\
\vdots & \ddots & \vdots\\
G_{j-1, 1} & \cdots & G_{j-1, i-1}\\
G_{j+1, 1} & \cdots & G_{j+1, i-1}\\
\vdots & \ddots & \vdots\\
G_{i, 1} & \cdots & G_{i, i-1}
]
$$
と定義される整数である．
$\widetilde{\boldsymbol{b}}_i\coloneqq \sum_{j=1}^i(-1)^{j+i}\frac{d_{i, j}}{d_{i, i}}\boldsymbol{b}_j$と置く．$i$に関する数学的帰納法によって証明します．
- $i=1$のときは，
$$ \widetilde{\boldsymbol{b}}_1=(-1)^{1+1}\frac{d_{1, 1}}{d_{1, 1}}\boldsymbol{b}_1=\boldsymbol{b}_1 $$
であるのでok． - $i-1$のときまで$\widetilde{\boldsymbol{b}}_\ell=\boldsymbol{b}_\ell^\star~(1\le \ell\le i-1)$を仮定します．このとき，
$$ \begin{aligned} \langle \widetilde{\boldsymbol{b}}_i, \boldsymbol{b}_k\rangle&=\left\langle \sum_{j=1}^i(-1)^{i+j}\frac{d_{i, j}}{d_{i, i}}\boldsymbol{b}_j, \boldsymbol{b}_k\right\rangle\\ &=\frac{1}{d_{i, i}}\sum_{j=1}^i(-1)^{i+j}d_{i, j}\langle\boldsymbol{b}_j, \boldsymbol{b}_k\rangle\\ &=\frac{1}{d_{i, i}}\sum_{j=1}^i(-1)^{i+j}G_{j, k}\det\mqty[ G_{1, 1}\ & \cdots & G_{1, i-1}\\ \vdots & \ddots & \vdots\\ G_{j-1, 1} & \cdots & G_{j-1, i-1}\\ G_{j+1, 1} & \cdots & G_{j+1, i-1}\\ \vdots & \ddots & \vdots\\ G_{i, 1} & \cdots & G_{i, i-1} ]\\ &=\frac{1}{d_{i, i}}\det\mqty[ G_{1, k} & G_{1, 1} & \cdots & G_{1, i-1}\\ \vdots & \vdots & \ddots & \vdots\\ G_{i, k} & G_{i, 1} & \cdots & G_{i, i-1} ] \end{aligned} $$
が成立するので，$1\le k\le i-1$のとき，$\langle \widetilde{\boldsymbol{b}}_i, \boldsymbol{b}_k\rangle=0$です．更に，定義から，$\widetilde{\boldsymbol{b}}_i$の$\boldsymbol{b}_i$の係数は$(-1)^{i+i}\frac{d_{i, i}}{d_{i, i}}=1$です．
他方で，
$$ \begin{aligned} \langle \boldsymbol{b}_i^\star, \boldsymbol{b}_k\rangle&=\left\langle\boldsymbol{b}_i^\star, \boldsymbol{b}_k^\star+\sum_{j=1}^{k-1}\frac{\langle \boldsymbol{b}_i, \boldsymbol{b}_j^\star\rangle}{\norm{\boldsymbol{b}_j^\star}^2}\boldsymbol{b}_j^\star\right\rangle\\ &=\langle\boldsymbol{b}_i^\star, \boldsymbol{b}_k^\star\rangle+\sum_{j=1}^{k-1}\frac{\langle \boldsymbol{b}_i, \boldsymbol{b}_j^\star\rangle}{\norm{\boldsymbol{b}_j^\star}^2}\langle\boldsymbol{b}_i^\star, \boldsymbol{b}_j^\star\rangle \end{aligned} $$
より，$1\le k\le i-1$のとき，
$$ \langle\boldsymbol{b}_i^\star, \boldsymbol{b}_k^\star\rangle+\sum_{j=1}^{k-1}\frac{\langle \boldsymbol{b}_i, \boldsymbol{b}_j^\star\rangle}{\norm{\boldsymbol{b}_j^\star}^2}\langle\boldsymbol{b}_i^\star, \boldsymbol{b}_j^\star\rangle=0\quad(\because i\ne j\implies \langle \boldsymbol{b}_i, \boldsymbol{b}_j\rangle=0) $$
です．更に，$\boldsymbol{b}_i^\star$の$\boldsymbol{b}_i$の係数も明らかに$1$です．ここで，
$$ \boldsymbol{d}\coloneqq \boldsymbol{b}_i^\star-\widetilde{\boldsymbol{b}}_i $$
とベクトル$\boldsymbol{d}\in\langle\boldsymbol{b}_1, \ldots, \boldsymbol{b}_i\rangle_\mathbb{R}$を定めると$1\le k\le i-1$に対して$\langle\boldsymbol{d}, \boldsymbol{b}_k\rangle=0$であり，$\boldsymbol{d}$の$\boldsymbol{b}_i$の係数は$1-1=0$です．従って，
$$ \boldsymbol{d}=\sum_{j=1}^{i-1}d_j\boldsymbol{b}_j\quad({}^\exists d_1,\ldots, d_{i-1}\in\mathbb{R}) $$
と書くことができます．この$d_1,\ldots, d_{i-1}\in\mathbb{R}$は次の方程式を満足します：
$$ \begin{aligned} &1\le{}^\forall k\le i-1,~\sum_{j=1}^{i-1}d_j\langle \boldsymbol{b}_j, \boldsymbol{b}_k\rangle=0\\ \iff& (d_1,\ldots, d_{i-1})\underbrace{\mqty[ G_{1, 1} & \cdots & G_{1, i-1}\\ \vdots & \ddots & \vdots\\ G_{i-1, 1} & \cdots & G_{i-1, i-1} ]}_{\quad\quad~~\coloneqq \boldsymbol{G}}=\boldsymbol{0}. \end{aligned} $$
ここで，行列$\boldsymbol{G}\in\mathrm{M}_{i-1}(\mathbb{Z})$は，$\boldsymbol{b}_1, \ldots, \boldsymbol{b}_{i-1}$が一次独立であることから正則であることがわかります．従って，$d_1=\cdots=d_{i-1}=0$です．よって$\boldsymbol{d}=\boldsymbol{0}$です．従って，$\widetilde{\boldsymbol{b}}_i=\boldsymbol{b}_i^\star$が成立します．
以上より，数学的帰納法により，ok．$\square$
補題1から，次の命題が成立します．
$n$次元格子の基底$\{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\}$のGram-Schmidtの直交化ベクトルの二乗ノルムを$B_i\coloneqq \norm{\boldsymbol{b}_i^\star}^2~(i=1,\ldots, n)$，Gram-Schmidtの直交化係数行列を$\boldsymbol{U}\coloneqq(\mu_{i, j})$とすると，次が成立する．
$$
B_i=\frac{\sum_{j=1}^i\sum_{k=1}^i(-1)^{j+k}d_{i, j}d_{i, k}\langle\boldsymbol{b}_j, \boldsymbol{b}_k\rangle}{d_{i, i}^2},
$$
$$
\mu_{i, j}=\left\{
\begin{array}{ll}
&\!\!\!\!\!\frac{d_{j, j}\sum_{k=1}^j(-1)^{j+k}d_{j, k}G_{i, k}}{\sum_{k=1}^i\sum_{\ell=1}^j(-1)^{k+\ell}d_{j, k}d_{j, \ell}G_{k, \ell}}&\text{if}~~1\le j< i\le n\\
&\!\!\!\!\!1&\text{if}~~i=j\\
&\!\!\!\!\!0&\text{else}
\end{array}
\right.
$$
補題1より，
$$
\begin{aligned}
B_i&=\norm{\boldsymbol{b}_i^\star}^2\\
&=\norm{\sum_{j=1}^i(-1)^{j+i}\frac{d_{i, j}}{d_{i, i}}\boldsymbol{b}_j}^2\\
&=\left\langle \sum_{j=1}^i(-1)^{j+i}\frac{d_{i, j}}{d_{i, i}}\boldsymbol{b}_j, ~\sum_{k=1}^i(-1)^{k+i}\frac{d_{i, k}}{d_{i, i}}\boldsymbol{b}_k\right\rangle\\
&=\sum_{j=1}^i\sum_{k=1}^i(-1)^{j+k}\frac{d_{i, j}d_{i, k}}{d_{i, i}^2}\langle\boldsymbol{b}_j, \boldsymbol{b}_k\rangle\\
&=\frac{\sum_{j=1}^i\sum_{k=1}^i(-1)^{j+k}d_{i, j}d_{i, k}\langle\boldsymbol{b}_j, \boldsymbol{b}_k\rangle}{d_{i, i}^2},\\
\mu_{i, j}&=\frac{\langle\boldsymbol{b}_i, \boldsymbol{b}_j^\star\rangle}{\norm{\boldsymbol{b}_j^\star}^2}\\
&=\frac{\left\langle \boldsymbol{b}_i, \sum_{k=1}^j(-1)^{j+k}\frac{d_{j, k}}{d_{j, j}}\boldsymbol{b}_k\right\rangle}{\frac{\sum_{k=1}^j\sum_{\ell=1}^j(-1)^{k+\ell}d_{j, k}d_{j, \ell}\langle\boldsymbol{b}_k, \boldsymbol{b}_\ell\rangle}{d_{j, j}^2}}\\
&=\frac{d_{j, j}^2\sum_{k=1}^j(-1)^{j+k}d_{j, k}G_{i, k}}{d_{j, j}\sum_{k=1}^j\sum_{\ell=1}^j(-1)^{k+\ell}d_{j, k}d_{j, \ell}G_{k, \ell}}\\
&=\frac{d_{j, j}\sum_{k=1}^j(-1)^{j+k}d_{j, k}G_{i, k}}{\sum_{k=1}^j\sum_{\ell=1}^j(-1)^{k+\ell}d_{j, k}d_{j, \ell}G_{k, \ell}}.\quad \square
\end{aligned}
$$
また，命題2における$B_i$，$\mu_{i, j}$の分母分子は明らかに双方ともに整数です．
また，$B_i$の分数表示を$B_i=\frac{B_i^{(\text{num})}}{B_i^{(\text{den})}}$，$\mu_{i, j}$の分数表示を$\mu_{i, j}=\frac{\mu_{i, j}^{(\text{num})}}{\mu_{i, j}^{(\text{den})}}$とすると，サイズ簡約条件，並びにLovász条件は次のように書き換えることができる．
$$ \begin{array}{ll} &\text{サイズ簡約条件}&\iff 2\abs{\mu_{i, j}^{(\mathrm{num})}}\le \abs{\mu_{i, j}^{(\mathrm{den})}}\\ &\text{Lovász条件}&\iff B_{k}^{(\mathrm{num})}B_{k-1}^{(\mathrm{den})}b\left(\mu_{k, k-1}^{(\mathrm{den})}\right)^2\ge \left(a\left(\mu_{k, k-1}^{(\mathrm{den})}\right)^2-\left(\mu_{k, k-1}^{(\mathrm{num})}\right)^2b\right)B_{k-1}^{(\mathrm{num})}B_{k}^{(\mathrm{den})} \end{array} $$
Gram-Schmidtの直交化情報の更新公式について
LLLアルゴリズムの中では，サイズ基底簡約とLovász条件を満たさない隣り合う基底ベクトルの入れ替えを繰り返し行っています．基底簡約をするたびにいちいち命題2を用いて再計算していたのではあまりに非効率です．そこで，ここではGram-Schmidtの直交化情報を効率的に更新する公式について述べていきます．
まず，サイズ簡約を行った基底のGram-Schmidtの直交化情報について次の定理が成立します．
$\{\boldsymbol{b}_1, \ldots, \boldsymbol{b}_n\}$を$n$次元格子$L$の基底とし，$L$の別の基底$\{\boldsymbol{c}_1,\ldots, \boldsymbol{c}_n\}$を
$$
\boldsymbol{c}_i\coloneqq\left\{
\begin{aligned}
&\boldsymbol{b}_i-\round{\mu_{i, j}}\boldsymbol{b}_j & \text{if}~~i=k\\
&\boldsymbol{b}_i & \text{if}~~i\ne k
\end{aligned}
\right.
$$
と定めると，$\{\boldsymbol{c}_1,\ldots, \boldsymbol{c}_n\}$のGram-Schmidtの直交化ベクトルの二乗ノルム$(C_i)$，Gram-Schmidtの直交化係数行列$(\nu_{i, j})$は
$$
\begin{aligned}
C_i&=B_i & (1\le {}^\forall i\le n)\\
\nu_{i, \ell}&=\mu_{i, \ell}-\round{\mu_{i, j}}\mu_{j, \ell} & (1\le{}^\forall \ell \le j)
\end{aligned}
$$
と書くことができる．
隣合う基底ベクトルの交換後のGram-Schmidtの直交化情報については，次の定理が成立します．
$\{\boldsymbol{b}_1, \ldots, \boldsymbol{b}_n\}$を$n$次元格子$L$の基底とし，$L$の別の基底$\{\boldsymbol{c}_1,\ldots, \boldsymbol{c}_n\}$を
$$
\boldsymbol{c}_i\coloneqq\left\{
\!\!\!\!\!\begin{array}{ll}
&\boldsymbol{b}_{k}& \text{if}~~i=k-1\\
&\boldsymbol{b}_{k-1} & \text{if}~~i=k\\
&\boldsymbol{b}_i & \text{else}
\end{array}
\right.
$$
と定めると，$\{\boldsymbol{c}_1,\ldots, \boldsymbol{c}_n\}$のGram-Schmidtの直交化ベクトルの二乗ノルム$(C_i)$，Gram-Schmidtの直交化係数行列$(\nu_{i, j})$は
$$
C_i=\left\{
\!\!\!\!\!\begin{array}{ll}
& B_k+\mu_{k, k-1}^2B_{k-1} & \text{if}~~i=k-1\\
& \frac{B_{k-1}B_k}{B_k+\mu_{k, k-1}^2B_{k-1}} & \text{if}~~i=k\\
& B_i & \text{else}
\end{array}
\right.
$$
$$
\nu_{i, j}=\left\{
\!\!\!\!\!\begin{array}{ll}
& \frac{\mu_{k, k-1}B_{k-1}}{B_k+\mu_{k, k-1}^2B_{k-1}} & \text{if}~~(i, j)=(k, k-1)\\
& \mu_{k, j} & \text{if}~~i=k-1,~1\le j\le k-2\\
& \mu_{k-1, j} & \text{if}~~i=k,~1\le j\le k-2\\
& \mu_{i, k}+\frac{\mu_{k, k-1}B_{k-1}(\mu_{i, k-1}-\mu_{k, k-1}\mu_{i, k})}{B_k+\mu_{k, k-1}^2B_{k-1}} & \text{if}~~k+1\le i\le n,~j=k-1\\
& \mu_{i, k-1}-\mu_{k, k-1}\mu_{i, k} & \text{if}~~k+1\le i\le n,~j=k\\
& \mu_{i, j} & \text{else}
\end{array}
\right.
$$
と書くことができる．
定理4を用いると，$C_i$及び$\nu_{i, j}$は，整数の分数として次の様に表すことができる．
$\{\boldsymbol{b}_1, \ldots, \boldsymbol{b}_n\}$を$n$次元格子$L$の基底とし，$L$の別の基底$\{\boldsymbol{c}_1,\ldots, \boldsymbol{c}_n\}$を
$$
\boldsymbol{c}_i\coloneqq\left\{
\begin{aligned}
&\boldsymbol{b}_i-\round{\mu_{i, j}}\boldsymbol{b}_j & \text{if}~~i=k\\
&\boldsymbol{b}_i & \text{if}~~i\ne k
\end{aligned}
\right.
$$
と定めると，$\{\boldsymbol{c}_1,\ldots, \boldsymbol{c}_n\}$のGram-Schmidtの直交化ベクトルの二乗ノルム$(C_i)$，Gram-Schmidtの直交化係数行列$(\nu_{i, j})$は
$$
\begin{aligned}
C_i&=B_i & (1\le {}^\forall i\le n)\\
\nu_{i, \ell}&=\frac{\mu_{i, \ell}^{(\text{num})}\mu_{j, \ell}^{(\text{den})}-\round{\mu_{i, j}}\mu_{i, \ell}^{(\text{den})}\mu_{j, \ell}^{(\text{num})}}{\mu_{i, \ell}^{(\text{den})}\mu_{j, \ell}^{(\text{den})}} & (1\le{}^\forall \ell \le j)
\end{aligned}
$$
と書くことができる．
$\{\boldsymbol{b}_1, \ldots, \boldsymbol{b}_n\}$を$n$次元格子$L$の基底とし，$L$の別の基底$\{\boldsymbol{c}_1,\ldots, \boldsymbol{c}_n\}$を
$$
\boldsymbol{c}_i\coloneqq\left\{
\!\!\!\!\!\begin{array}{ll}
&\boldsymbol{b}_{k}& \text{if}~~i=k-1\\
&\boldsymbol{b}_{k-1} & \text{if}~~i=k\\
&\boldsymbol{b}_i & \text{else}
\end{array}
\right.
$$
と定めると，$\{\boldsymbol{c}_1,\ldots, \boldsymbol{c}_n\}$のGram-Schmidtの直交化ベクトルの二乗ノルム$(C_i)$，Gram-Schmidtの直交化係数行列$(\nu_{i, j})$は
$$
C_i=\left\{
\!\!\!\!\!\begin{array}{ll}
& \frac{B_k^{(\text{num})}B_{k-1}^{(\text{den})}\left(\mu_{k, k-1}^{(\text{den})}\right)^2+\left(\mu_{k, k-1}^{(\text{num})}\right)^2 B_k^{(\text{den})}B_{k-1}^{(\text{num})}}{B_k^{(\text{den})}B_{k-1}^{(\text{den})}\left(\mu_{k, k-1}^{(\text{den})}\right)^2} & \text{if}~~i=k-1\\
& \frac{B_{k-1}^{(\text{num})}B_k^{(\text{num})}C_{k-1}^{(\text{den})}}{B_{k-1}^{(\text{den})}B_k^{(\text{den})}C_{k-1}^{(\text{num})}} & \text{if}~~i=k\\
& B_i & \text{else}
\end{array}
\right.
$$
$$
\nu_{i, j}=\left\{
\!\!\!\!\!\begin{array}{ll}
& \frac{\mu_{k, k-1}^{\text{(num)}}B_{k-1}^{\text{(num)}}C_{k-1}^{\text{(den)}}}{\mu_{k, k-1}^{\text{(den)}}B_{k-1}^{\text{(den)}}C_{k-1}^{\text{(num)}}} & \text{if}~~(i, j)=(k, k-1)\\
& \mu_{k, j} & \text{if}~~i=k-1,~1\le j\le k-2\\
& \mu_{k-1, j} & \text{if}~~i=k,~1\le j\le k-2\\
& \frac{\mu_{i, k-1}^{\text{(num)}}\mu_{k, k-1}^{\text{(den)}}\mu_{i, k}^{\text{(den)}}-\mu_{k, k-1}^{\text{(num)}}\mu_{i, k}^{\text{(num)}}\mu_{i, k-1}^{\text{(den)}}}{\mu_{i, k-1}^{\text{(den)}}\mu_{k, k-1}^{\text{(den)}}\mu_{i, k}^{\text{(den)}}} & \text{if}~~k+1\le i\le n,~j=k\\
& \frac{\mu_{i, k}^{\text{(num)}}\nu_{k, k-1}^{\text{(den)}}\nu_{i, k}^{\text{(den)}}+\mu_{i, k}^{\text{(den)}}\nu_{k, k-1}^{\text{(num)}}\nu_{i, k}^{\text{(num)}}}{\mu_{i, k}^{\text{(den)}}\nu_{k, k-1}^{\text{(den)}}\nu_{i, k}^{\text{(den)}}} & \text{if}~~k+1\le i\le n,~j=k-1\\
& \mu_{i, j} & \text{else}
\end{array}
\right.
$$
と書くことができる．
通分すれば良い．$\square$
fracLLLを実装してみた
実際に，前節にて証明した命題らを利用してfracLLLを組んでみました．まずは，疑似コードです．
$$
\begin{array}{l}
& \!\!\!\!\!\!\!\!\!\!\!\!\textbf{Algorithm~1}~\text{frac\_gso(): 有理数によるGram-Schmidtの直交化情報の計算}\\
& \!\!\!\!\!\!\!\!\!\!\!\!\textbf{Input}:~\text{基底ベクトルを並べた行列}\boldsymbol{B}\\
& \!\!\!\!\!\!\!\!\!\!\!\!\textbf{Output}:~\text{入力基底のGram-Schmidtの直交化情報}\\
1 & G\gets \boldsymbol{BB}^\top\\
2 & B^{(\text{num})}\gets\boldsymbol{0}_n;~B^{(\text{den})}\gets\boldsymbol{0}_n\\
3 & \mu^{(\text{num})}\gets \boldsymbol{E}_{n};~\mu^{(\text{den})}\gets (1)_{1\le i, j\le n}; D\gets \boldsymbol{O}_{n, n}\\
4 & \textbf{for}~i=1~\text{to}~n~\textbf{do}\\
5 & \quad\textbf{for}~j=1~\text{to}~n~\textbf{do}\\
6 & \quad\quad\textbf{if}~i=j=1~\textbf{then}\\
7 & \quad\quad\quad D_{i, j}\gets 1\\
8 & \quad\quad \textbf{else}\\
9 & \quad\quad\quad d\gets \boldsymbol{O}_{i-1, i-1}\\
10 & \quad\quad\quad \textbf{for}~k=1~\text{to}~i-1~\textbf{do}\\
11 & \quad\quad\quad\quad \textbf{for}~\ell=1~\text{to}~{i-1}~\textbf{then}\\
12 & \quad\quad\quad\quad\quad \textbf{if}~k< j~\textbf{then}~d_{k, \ell}=G_{k, \ell}~\textbf{else}~d_{k, \ell}=G_{k+1, \ell}\\
13 & \quad\quad\quad D_{i, j}\gets \det d\\
14 & \textbf{for}~i=1~\text{to}~n~\textbf{do}\\
15 & \quad B_{i}^{(\text{num})}\gets \sum_{j=1}^i\sum_{k=1}^i(-1)^{j+k}D_{i, j}D_{i, k}G_{j, k}\\
16 & \quad B_i^{(\text{den})}\gets D_{i, i}^2\\
17 & \quad\textbf{for}~j=1~\text{to}~i-1~\textbf{do}\\
18 & \quad\quad \mu_{i, j}^{(\text{num})}\gets D_{j, j}\sum_{k=1}^j(-1)^{j+k}D_{j, k}G_{i, k}\\
19 & \quad\quad \mu_{i, j}^{(\text{den})}\gets \sum_{k=1}^i\sum_{\ell=1}^j(-1)^{k+\ell}D_{j, k}D_{j, \ell}G_{k, \ell}\\
\end{array}
$$
$$ \begin{array}{ll} &\!\!\!\!\!\!\!\textbf{Algorithm~2}~\text{frac\_size(i, j): 有理数による部分サイズ基底簡約}\\ & \!\!\!\!\!\!\!\textbf{Input}:~\text{格子の基底}\{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\},\text{Gram-Schmditの直交化係数行列}\left(\frac{\mu_{i, j}^{(\text{num})}}{\mu_{i, j}^{(\text{den})}}\right)\\ & \!\!\!\!\!\!\!\textbf{Output}:~\text{簡約された基底}\{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\}\\ 1 & \textbf{if}~2\abs{\mu_{i, j}^{(\text{num})}}>\abs{\mu_{i, j}^{(\text{den})}}~\textbf{then}\\ 2 & \quad q\gets \round{\frac{\mu_{i, j}^{(\text{num})}}{\mu_{i, j}^{(\text{den})}}}\\ 3 & \quad\boldsymbol{b}_{i}\gets \boldsymbol{b}_i-q\boldsymbol{b}_j\\ 4 & \quad \textbf{for}~\ell=1~\text{to}~j~\textbf{do}\\ 5 & \quad\quad \mu_{i, \ell}^{(\text{num})}\gets \mu_{i, \ell}^{(\text{num})}\mu_{j, \ell}^{(\text{den})}-q\mu_{i, \ell}^{(\text{den})}\mu_{j, \ell}^{(\text{num})}\\ 6 & \quad\quad \mu_{i, \ell}^{(\text{den})}\gets \mu_{i, \ell}^{(\text{den})}\mu_{j, \ell}^{(\text{den})} \end{array} $$
$$
\begin{array}{ll}
&\!\!\!\!\!\!\!\!\!\!\!\!\textbf{Algorithm~3}~\text{frac\_lll(a, b): 有理数によるLLL簡約}\\
& \!\!\!\!\!\!\!\!\!\!\!\!\textbf{Input}:~\text{格子基底}\{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\},\text{簡約パラメタ}\frac{a}{b}\\
& \!\!\!\!\!\!\!\!\!\!\!\!\textbf{Output}:~\text{簡約された基底}\{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\}\\
1 & B^{(\text{num})}, B^{(\text{den})}, \mu^{(\text{num})}, \mu^{(\text{den})}\gets \texttt{frac\_gso}()\\
2 & k\gets 2\\
3 & \textbf{while}~k\le n~\textbf{do}\\
4 & \quad \textbf{for}~j=k-1~\text{downto}~1\\
5 & \quad\quad \texttt{frac\_size}(k, j)\\
6 & \quad \textbf{if}~B_{k}^{(\mathrm{num})}B_{k-1}^{(\mathrm{den})}b\left(\mu_{k, k-1}^{(\mathrm{den})}\right)^2\ge \left(a\left(\mu_{k, k-1}^{(\mathrm{den})}\right)^2-\left(\mu_{k, k-1}^{(\mathrm{num})}\right)^2b\right)B_{k-1}^{(\mathrm{num})}B_{k}^{(\mathrm{den})}~\textbf{then}\\
7 & \quad\quad k\gets k+1\\
8 & \quad \textbf{else}\\
9 &\quad\quad \text{swap}(\boldsymbol{b}_{k-1},\boldsymbol{b}_k)\\
10 & \quad\quad \texttt{update\_gso\_swap}(k)\\
11 & \quad\quad k\gets \max\{k-1, 2\}
\end{array}
$$
$$ \begin{array}{ll} &\!\!\!\!\!\!\!\!\!\!\!\!\textbf{Algorithm~4}~\text{update\_gso\_swap(k): 隣り合う基底ベクトル}\boldsymbol{b}_{k-1},\boldsymbol{b}_k\text{の交換後のGram-Schmidtの直交化情報の更新}\\ & \!\!\!\!\!\!\!\!\!\!\!\!\textbf{Input}:~\text{Gram-Schmditの直交化情報}\left(\frac{\mu_{i, j}^{(\text{num})}}{\mu_{i, j}^{(\text{den})}}\right), \left(\frac{B_{i}^{(\text{num})}}{B_{i}^{(\text{den})}}\right)\\ & \!\!\!\!\!\!\!\!\!\!\!\!\textbf{Output}:~\text{更新されたGram-Schmidt情報}\left(\frac{\nu_{i, j}^{(\text{num})}}{\nu_{i, j}^{(\text{den})}}\right), \left(\frac{C_{i}^{(\text{num})}}{C_{i}^{(\text{den})}}\right)\\ 1 & C^{(\text{num})}\gets B^{(\text{num})};~C^{(\text{den})}\gets B^{(\text{den})}\\ 2 & \nu^{(\text{num})}\gets \mu^{(\text{num})};~\nu^{(\text{den})}\gets \mu^{(\text{den})}\\ 3 & C^{(\text{num})}_{k-1}\gets B_k^{(\text{num})}B_{k-1}^{(\text{den})}\left(\mu_{k, k-1}^{(\text{den})}\right)^2+\left(\mu_{k, k-1}^{(\text{num})}\right)^2 B_k^{(\text{den})}B_{k-1}^{(\text{num})}\\ 4 & C^{(\text{den})}_{k-1}\gets B_k^{(\text{den})}B_{k-1}^{(\text{den})}\left(\mu_{k, k-1}^{(\text{den})}\right)^2\\ 5 & C^{(\text{num})}_{k}\gets B_{k-1}^{(\text{num})}B_k^{(\text{num})}C_{k-1}^{(\text{den})}\\ 6 & C^{(\text{den})}_{k}\gets B_{k-1}^{(\text{den})}B_k^{(\text{den})}C_{k-1}^{(\text{num})}\\ 7 & \nu_{k, k-1}^{(\text{num})}\gets \mu_{k, k-1}^{\text{(num)}}B_{k-1}^{\text{(num)}}C_{k-1}^{\text{(den)}}\\ 8 & \nu_{k, k-1}^{(\text{den})}\gets\mu_{k, k-1}^{\text{(den)}}B_{k-1}^{\text{(den)}}C_{k-1}^{\text{(num)}}\\ 9 & \textbf{for}~j=1~\text{to}~k-2~\textbf{do}\\ 10 & \quad \nu_{k-1, j}^{(\text{num})}\gets \mu_{k, j}^{(\text{num})};~\nu_{k-1, j}^{(\text{den})}\gets \mu_{k, j}^{(\text{den})}\\ 11 & \quad \nu_{k, j}^{(\text{num})}\gets \mu_{k-1, j}^{(\text{num})};~\nu_{k, j}^{(\text{den})}\gets \mu_{k-1, j}^{(\text{den})}\\ 12 & \textbf{for}~i=k+1~\text{to}~n\\ 13 & \quad \mu_{i, k}^{(\text{num})}\gets \mu_{i, k-1}^{\text{(num)}}\mu_{k, k-1}^{\text{(den)}}\mu_{i, k}^{\text{(den)}}-\mu_{k, k-1}^{\text{(num)}}\mu_{i, k}^{\text{(num)}}\mu_{i, k-1}^{\text{(den)}}\\ 14 & \quad \mu_{i, k}^{(\text{den})}\gets \mu_{i, k-1}^{\text{(den)}}\mu_{k, k-1}^{\text{(den)}}\mu_{i, k}^{\text{(den)}}\\ 15 & \quad \mu_{i, k-1}^{(\text{num})}\gets \mu_{i, k}^{\text{(num)}}\nu_{k, k-1}^{\text{(den)}}\nu_{i, k}^{\text{(den)}}+\mu_{i, k}^{\text{(den)}}\nu_{k, k-1}^{\text{(num)}}\nu_{i, k}^{\text{(num)}}\\ 16 & \quad \mu_{i, k-1}^{(\text{den})}\gets \mu_{i, k}^{\text{(den)}}\nu_{k, k-1}^{\text{(den)}}\nu_{i, k}^{\text{(den)}} \end{array} $$
実装には，言語は$\texttt{C++}$を使ってもよかったのですが，$\texttt{int}$型はもちろん$\texttt{long int}$型や$\texttt{long long int}$型に収まる保証もありませんし，NTLライブラリを利用するのも面倒だったので$\texttt{SageMath v.10.6}$で実装を行いました．また，最新の$\texttt{SageMath}$は$\texttt{Ubuntu}$などにinstallしなくとも， SageMath Cell から利用できます．
実際に実装したSageMathのコードは以下のGitHubから確認することができます．
ランダムに生成した格子基底に対して，frac_lll関数と，$\texttt{SageMath}$の組み込み関数LLLとで実行時間などの比較を行いました．
![!FORMULA[138][334861356][0]関数と!FORMULA[139][1191276253][0]関数の実行時間の比較](https://firebasestorage.googleapis.com/v0/b/mathlog-361213.appspot.com/o/uploads%2Fmathdown%2FeL4GfIu1OjgLN9Pr1FZK.png?alt=media)
$\texttt{frac\_lll}$関数と$\texttt{LLL}$関数の実行時間の比較
精度は従来のLLLと比較して非常に向上していると考えられますが，実行時間がかなりかかってしまっています．
frac_lllに入力する基底$\{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\}$とし，$X=\max\{\norm{\boldsymbol{b}_1}^2,\ldots,\norm{\boldsymbol{b}_n}^2\}$とすると，frac_lllの計算量は$\mathcal{O}\left(n^5+\frac{5}{2}n^4\log X\right)$以下である．（但し，$\gcd$演算は行わないとする．）
以下，関数fの計算量を$T(\texttt{f})$と書く．
まず
$$
\begin{aligned}
T(\texttt{frac\_gso})&=\mathcal{O}\left(n^2+\sum_{i=1}^{n}\sum_{j=1}^n \left(\sum_{k=1}^i i+i^3\right)+\sum_{i=1}^n\left[(i+1)^2+\sum_{j=1}^i \left\{(j+1)+(j+1)^2\right\}\right]\right)\\
&=\mathcal{O}\left(n^2+n\times n^4+n^3+\sum_{i=1}^ni^3\right)\\
&=\mathcal{O}(n^5+n^4)=\mathcal{O}(n^5)
\end{aligned}
$$
であり，
$$
\begin{aligned}
T(\texttt{frac\_size}(i, j))=\mathcal{O}(n+j),
\end{aligned}
$$
$$
\begin{aligned}
T(\texttt{update\_gso\_swap})&=\mathcal{O}(n^2+n+n)=\mathcal{O}(n^2)
\end{aligned}
$$
より，
$$
\begin{aligned}
T(\texttt{frac\_lll})&<\mathcal{O}\left(n^{5}+n^2\log(X)\left(\sum_{j=1}^{n-1}(n+j)+n+n^2\right)\right)\\
&=\mathcal{O}\left(n^5+n^2\log(X)\left((n-1)n+\frac{n(n-1)}{2}+n+n^2\right)\right)\\
&=\mathcal{O}\left(n^5+n^2\log(X)\left(\frac{5}{2}n^2-\frac{1}{2}n\right)\right)\\
&=\mathcal{O}\left(n^5+\frac{5}{2}n^4\log X\right)
\end{aligned}
$$
となります．
実際には，整数が大きくなりすぎるのを防ぐために逐次$\gcd$計算が入るので，これよりは遅くなると考えられます．
