LoginSignup
1
0
@satoshin_astonish

Risa/Asir上でのLLL-reduction

Last updated at Posted at 2024-03-05

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

目次

1.準備
2.Lenstra-Lenstra-Lovász-reduction
3.Risa/Asirでの実装
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}$とは

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}

\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}$なるような基底をいう。このとき

\|\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)されているとは

\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

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0