Risa/Asir上でのLLL-reduction

Risa/Asir上でLLL-reductionを行うプログラムを実装したので、適当においておく。

# 目次
[1.準備](#準備とか)
[2.Lenstra-Lenstra-Lovász-reduction](#lll-reduction)
[3.Risa/Asirでの実装](#risaasir上での実装)
[4.動かす](#実際に動かしてみる)
[5.参考文献](#参考文献)

# 準備とか

LLL-reductionについて書くに当たって、本記事で必要そうなものとかをここで準備しておく。格子については詳しいところは省く。何か適当な参考書などを読んでほしい。
## みんな大好きGram-Schmidtの直交化法
Gram-Schmidtの直交化は、よくGSOとかと略されるので、ここでもこの略語を使う。
### 定義: GSO
$n$次元格子$L=\mathcal{L}(\boldsymbol{B})$の基底 $\{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\}$のGSOベクトル$\boldsymbol{b}_i^*$とGSO係数$\mu _ {i,j}$とは

```math:LLL-reduce
\begin{aligned}
\left\{
\begin{aligned}
\boldsymbol{b}_1^*&:=\boldsymbol{b}_1\\
\boldsymbol{b}_i^*&:=\boldsymbol{b}_i-\sum _ {j=1} ^ {i-1} \frac{\langle\boldsymbol{b}_i,\boldsymbol{b}_j^*\rangle}{\left\|\boldsymbol{b}_j^*\right\|^2}\boldsymbol{b}_j^*~~(2\le i\le n)
\end{aligned}
\right.
\end{aligned}
```

```math
\mu_{i,j}:=\frac{\langle\boldsymbol{b}_i,\boldsymbol{b}_j^*\rangle}{\left\|\boldsymbol{b}_j^*\right\|^2}~~(1\le j < i \le n)
```

と定義されるベクトルの組とかである。
LLL-reductionを行う上でGSOは必ずと言っていいほど必要なので、GSOを行う函数もRisa/Asir上で作っておく。尚、```dot```函数は引数として二つのベクトルをとり、その内積を計算する自作函数である。

```:gram_schmidt.rr
/*inner product*/
def dot(X, Y){
	N = size(X);
	S = 0;
	for(I = 0; I < N[0]; I += 1){S += X[I] * Y[I];}
	return S;
}

/*Gram-Schmidt process*/
def gram_schmidt_squared(B){
	M = size(B); N = M[0]; M = M[1];
	BB = newvect(N); MU = newmat(N, N); GSOB = newmat(N, M);
	for(I = 0; I < N; I += 1){
		MU[I][I] = 1.0;
		for(J = 0; J < M; J += 1){GSOB[I][J] = B[I][J];}
		for(J = 0; J < I; J += 1){
			MU[I][J] = dot(B[I], GSOB[J]) / dot(GSOB[J], GSOB[J]);
			for(K = 0; K < M; K += 1){GSOB[I][K] -= MU[I][J] * GSOB[J][K];}
		}
		BB[I] = dot(GSOB[I], GSOB[I]);
	}
	return [BB, MU];
}
end$
```

このプログラムでは、GSOベクトルとGSO係数を出力するのではなく、GSOベクトルの二乗ノルム```BB```とGSO係数```MU```を出力していることに注意されたい。

## size-reduction
size-reductionは格子の基底ベクトルのGSO係数$|\mu _ {i,j}|\le\frac{1}{2}$なるような基底をいう。このとき

```math
\|\boldsymbol{b}_i\|^2=\left\|\sum _{j=1} ^{i} \mu _{i,j}\boldsymbol{b}_j^*\right\|^2=\sum _{j=1} ^{i} \mu _{i,j}^2\|\boldsymbol{b}_j^*\|^2\le\|\boldsymbol{b}_i^*\|^2+\frac{1}{4}\sum _{j=1} ^{i-1}\|\boldsymbol{b}_j^*\|^2
```

が上のように、簡単に確かめられる。下のソースコードは$|\mu _{i,j}|>\frac{1}{2}$であるときに、$|\mu _{i,j}|\le\frac{1}{2}$となるように基底を変換し、新しい基底行列```B```とGSO係数行列```MU```を出力するものである。
また、GSOベクトルはsize-reductionの前後で変化しないことが知られている。

```:size_reduce.rr
def size_reduce(B, MU, I, J){
	M = size(B); N = M[0]; M = M[1];
	if(MU[I][J] > 0.5 || MU[I][J] < -0.5){
		Q = rint(MU[I][J]);
		for(K = 0; K < M; K += 1){B[I][K] -= Q * B[J][K];}
		for(K = 0; K <= J; K += 1){MU[I][K] -= MU[J][K] * Q;}
	}
	return [B, MU];
}
end$
```

# LLL-reduction

## LLL-reductionの定義
まず、$n$次元格子$L=\mathcal{L}(\boldsymbol{B})$の基底 $\{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\}$がLLL-reduceされていることの定義を確認しておく。
### 定義: LLL-reduce
$L$の基底がパラメータ$\delta\in\left(\frac{1}{4}, 1\right)$についてLLL-reduce (Lenstra-Lenstra-Lovász-reduce)されているとは

```math
\begin{aligned}
&\text{(size-reduced)}~~1\le^\forall j<^\forall i \le n,~~|\mu_{i,j}|\le\frac{1}{2}\\
&\text{(Lovász条件)}~~2\le^\forall k\le n,~~\left\|\boldsymbol{b}_k^*\right\|^2\ge(\delta-\mu_{k, k-1})\left\|\boldsymbol{b}_{k-1}^*\right\|^2
\end{aligned}

```

の二条件を満足するときをいう。
後ほど紹介するRisa/Asirのソースコードは、与えられた格子の基底に対して、その基底に基本変形を施していき、LLL-reducedの条件を満たすようにした基底を出力するものである。そのアルゴリズムの詳細は、[1]などの手頃な参考書を見てほしいが、大雑把には任意の$2\le k\le n$に対して以下のような操作を行う。

>任意の$1\le j\le k - 1$に対して、$\boldsymbol{b}_k←\boldsymbol{b}_k-\lfloor\mu _{k,j} \rceil$とする
>$\boldsymbol{b}_k$と$\boldsymbol{b} _{k-1}$がLovász条件を満足しない場合は$\boldsymbol{b}_k$と$\boldsymbol{b} _{k-1}$を交換する。

# Risa/Asir上での実装

```:LLL_reduce.rr
def lll(B, D){
	M = size(B); N = M[0]; M = M[1];
	MU = gram_schmidt_squared(B); BB = MU[0]; MU = MU[1];
	for(K = 1; K < N;){
        /*size-reduction*/
		for(J = K - 1; J > -1; J -= 1){
			MU = size_reduce(B, MU, K, J); B = MU[0]; MU = MU[1];
		}

		if(K > 0 && BB[K] < (D - MU[K][K - 1] * MU[K][K - 1]) * BB[K - 1]){
			for(I = 0; I < M; I += 1){
				TMP = B[K - 1][I]; B[K - 1][I] = B[K][I]; B[K][I] = TMP;
			}
            /*updates GSO-informations*/
			NU = MU[K][K - 1]; C = BB[K] + NU * NU * BB[K - 1]; C_INV = 1.0 / C; 
			MU[K][K - 1] = NU * BB[K - 1] * C_INV;
			BB[K] *= BB[K - 1] * C_INV; BB[K - 1] = C;
			for(J = 0; J < K - 1; J += 1){
				T = MU[K - 1][J]; MU[K - 1][J] = MU[K][J]; MU[K][J] = T;
			}
			for(I = K + 1; I < N; I += 1){
				T = MU[I][K]; MU[I][K] = MU[I][K - 1] - NU * T;
				MU[I][K - 1] = T + MU[K][K - 1] * MU[I][K];
			}
			K -= 1;
		}else{K += 1;}
	}
	return B;
}
end$
```

# 実際に動かしてみる
ここでの実験ではランダムに格子基底を生成しているが、その格子基底行列は次のソースコードによって生成している。

```:gen_lattice.rr
def gen_lattice(N){
	A = newmat(N, N);
	for(I = 0; I < N; I += 1){
		A[I][I] = 1;
		A[I][0] = random();
	}
	return A;
}
end$
```

```:入力
[ 1131385020 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 3697612515 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 4264844916 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1364828348 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 2863894246 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1109863328 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 3066937191 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 2778683115 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 3989613953 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 859474495 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 167522376 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1094225558 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1963711766 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1257324636 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1729949323 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 125753755 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1068698284 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1761594045 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 2106609220 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1033190229 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 946183933 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1100436279 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 489306665 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 2385045156 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 658699819 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 3308017340 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 2385997510 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 105622857 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1976233741 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1535497010 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 ]
[ 314176889 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 ]
[ 1247500738 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 ]
[ 2138106664 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 ]
[ 2757078771 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 ]
[ 2433460811 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 ]
[ 3970906471 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 ]
[ 1944201130 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 ]
[ 2366336502 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 ]
[ 2541539915 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 ]
[ 4284982935 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 ]
```

この格子基底に対して、出力は次のようになる
```:出力
[ 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 -1 0 0 0 0 0 1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1 1 0 0 0 0 0 0 0 0 0 0 1 1 -2 0 1 0 1 0 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1 1 1 0 -1 0 -1 1 0 0 -1 0 0 1 0 1 0 0 1 0 -1 1 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 0 1 1 -1 0 -1 1 -1 -1 -1 1 0 1 0 -1 0 1 1 0 0 0 0 1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1 0 0 1 -1 -1 -1 0 -1 0 -1 0 1 1 -1 0 0 0 0 0 0 1 1 -1 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 0 0 1 0 1 0 0 0 -1 0 2 1 0 0 0 -2 1 0 0 0 -1 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1 0 -1 -1 -1 0 2 0 0 1 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1 0 0 0 -1 1 0 0 0 0 0 0 1 0 0 0 -2 0 0 0 -1 1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1 0 1 0 0 -1 -1 0 -1 -1 -1 0 -1 1 1 0 1 0 1 0 -1 1 1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ -1 0 -1 0 1 1 0 0 1 1 1 -1 0 0 0 0 -1 1 0 0 1 0 0 0 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ -1 1 1 -1 0 1 0 -1 0 0 1 0 1 1 -1 0 0 1 1 0 -1 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1 0 0 -1 -1 0 -1 0 -1 0 -1 -1 1 1 0 0 -1 0 -1 1 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 0 0 -1 0 0 0 -1 0 0 0 -1 -1 0 0 0 1 1 0 -1 -1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 0 1 -1 0 0 0 1 -1 1 0 0 0 0 -1 0 0 0 -1 1 1 -1 0 0 1 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 0 0 0 0 1 1 0 2 0 0 -1 0 -1 0 0 0 1 0 0 0 -1 0 -1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 0 0 0 1 0 1 0 0 0 0 0 0 -1 -1 1 0 -1 0 1 0 0 0 -1 1 -1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 ]
[ -1 1 0 1 -1 0 0 0 1 0 -2 0 0 0 0 0 -1 1 -1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 0 0 0 0 0 1 0 -1 0 1 1 1 0 0 -1 -1 1 0 0 0 1 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 0 0 0 0 0 0 -1 -1 -1 -1 1 0 0 0 2 1 0 0 0 0 0 -1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ -1 -1 -1 1 0 -1 0 0 0 0 0 1 -1 -1 0 -1 0 -1 -1 1 0 -1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 ]
[ 0 -1 -1 0 1 1 1 1 1 1 0 0 -1 0 1 -1 1 0 0 0 1 0 1 0 0 1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1 1 0 0 0 0 0 0 -1 1 1 -1 0 0 1 0 1 1 0 0 0 0 0 1 0 -1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 ]
[ 0 0 0 0 1 0 -1 1 -1 -1 0 0 -1 0 0 0 -1 0 -1 -1 0 0 -1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 ]
[ 0 1 0 1 0 -1 0 1 0 0 -1 0 0 1 0 1 0 0 1 0 0 -1 0 0 0 -1 0 -1 1 1 0 0 0 0 0 0 0 0 0 0 ]
[ 0 -1 0 0 2 0 -1 0 0 0 0 0 -1 1 1 -1 1 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 ]
[ 0 0 0 0 1 0 0 1 0 0 0 0 0 0 -1 0 1 0 1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 ]
[ 0 0 0 0 -1 1 -1 0 0 0 -1 0 0 1 -2 1 0 0 -1 0 0 1 -1 0 1 0 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 1 1 0 1 -1 -1 1 1 0 0 0 0 1 0 1 0 -1 0 -1 0 -1 0 0 -1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 ]
[ 0 0 -1 0 0 0 0 0 -1 0 1 0 0 -1 0 0 1 -1 0 1 -1 0 1 0 0 0 1 0 -1 0 0 0 0 0 0 0 0 0 0 0 ]
[ 0 -1 0 0 -1 -1 -1 1 0 1 0 0 0 -1 0 0 0 0 0 1 0 -1 0 1 -1 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 0 ]
[ 0 0 -1 0 0 -1 -1 1 0 0 0 0 0 0 0 0 0 -1 0 1 -2 0 -1 1 0 1 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 ]
[ -1 0 0 0 0 1 -2 -1 0 0 0 0 -1 0 -1 0 -1 0 0 -1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 ]
[ 0 -1 0 -1 0 0 0 0 0 0 0 0 0 0 1 1 0 -1 0 0 0 -1 -1 1 1 1 0 0 0 -1 0 1 0 1 0 0 0 0 0 0 ]
[ 0 0 0 -1 -1 1 0 1 0 0 -1 1 0 1 0 0 1 0 1 0 -1 0 -1 0 0 0 0 0 0 0 -1 0 -1 0 0 0 0 0 0 0 ]
[ 0 -1 -1 1 -1 0 0 0 0 1 0 0 1 1 1 0 -1 0 -1 0 0 -1 0 0 0 0 1 0 0 0 0 -1 0 0 0 0 0 0 0 0 ]
[ 0 0 0 1 1 0 -1 0 0 1 0 0 0 0 -1 0 1 0 0 0 1 0 0 0 -1 1 0 0 0 0 0 0 -1 0 0 1 0 0 0 0 ]
[ 0 0 1 0 -1 0 0 2 -1 0 1 0 0 0 2 0 0 0 -1 0 -1 0 -1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 ]
[ 1 0 -1 -1 0 1 0 1 0 -1 -1 0 0 0 0 1 0 0 0 0 -1 1 -1 0 1 2 0 0 0 0 0 0 -1 0 0 0 0 1 0 0 ]
[ 1 1 0 0 0 -1 0 0 0 0 0 -1 1 -1 0 0 1 0 0 0 0 1 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 ]
[ -1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 -1 1 0 0 0 -1 1 0 -1 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 1 ]
```

特に第一ベクトルのノルムを```D = 0.99```に関して```lll_reduce```する前後で比較してみると$1131385020$から$3$に大幅に削減された。

# 参考文献
[1] 安田雅哉 and 青野良範. 格子暗号解読のための数学的基礎─格子基底簡約アルゴリズム入門─. 近代科学社. 2019
[2] Masayuki Noro, Takeshi Shimoyama, Taku Takeshima, et. al. _Asir_ _User's_ _Manual_. https://www2.rikkyo.ac.jp/web/noro/html-ja/man_toc.html
[3]Ralph Bottesch, Max M. Haslbeck, and René Thiemann. _A_ _Verified_ _Efficient_ _Implementation_ _of_ _the_ _LLL_ _Basis_ _Reduction_ _Algorithm_. LPAR-22. 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning. volume 57. 2018. pp.164-180. https://easychair.org/publications/paper/spJt