格子を用いた素因数分解法のSageMath上での実装

Schnorrによる素因数分解アルゴリズムをYan et al.が改良したのをSageMathで実装してみたので、ここに適当に書いておく。

# 目次
[1.数学的な道具の準備](#格子を用いた素因数分解法について)
[2.格子用いた素因数分解法について](#格子を用いた素因数分解法)
[3.SageMathで実装してみた](#sagemathでの実装)
[4.実装結果](#実装結果)
[5.パラメータを変えてみた](#パラメータを変えて実行)
[6.参考文献](#参考文献)

# 格子を用いた素因数分解法について
まず、格子を用いた素因数分解法のアイデアについて紹介する前に幾つか数学的な道具を定義しておく。

## 数学的な道具たちの紹介

### 因子基底
$p_i$を$i\ge 1$番目に小さな素数、$p_0=-1$として$P_ \ell= \lbrace p_i~|~0\le i\le \ell \rbrace$を**因子基底**と呼ぶ。

### 平滑な関係対
整数$M\in \mathbb{Z}$が$P_\ell$の元だけで素因数分解可能であるとき、$M\in\mathbb{Z}$は$p_\ell$**-平滑**であるという。
また、素因数分解したい自然数$N\in \mathbb{Z} _ {>0}$としたとき、整数の組$(u,v)\in \mathbb{Z} ^ 2$が$p_\ell$**-平滑な関係対**であるとは、$u$と$u-vN$の双方が$p_\ell$-平滑であるときをいう。

また、$u\perp N$であれば、$u,u-vN\in \mathbb{Z}$を
```math
u = \prod_{j=0}^\ell p_j^{e_j}, \quad u - vN = \prod_{j=0}^\ell p_j^{e'_j}
```
というように素因数分解できたとすると、

```math
\prod_{j=0}^\ell p_j^{e_j' - e_j} = (u-vN)u^{-1} \equiv 1 \pmod{N}
```
が成立することにも注意しておく。また、$\gcd(u,N)>1$のとき、既に$N$の素因数分解が終了してしまい、面白くないので$u\perp N$を仮定しておく。

## 平方差法
格子を用いた素因数分解法の基本的なアイデアは平方差法であるので、平方差法についても軽く説明しておく。また、$N$を素因数分解したい合成数とする。このとき、十分な個数の$p_\ell$-平滑な関係対$(u_i, v_i)$を見つけておく。

```math
u_i = \prod_{j = 0}^\ell p_j^{e_{i,j}}, \quad u_i - v_iN = \prod_{j=0}^\ell p_j^{e'_{i, j}}
```

このとき

```math
\sum_i t_i(e'_{i, j} - e_{i, j}) \equiv 0 \pmod{2}
```
の非零な解$\boldsymbol{t}$について
```math
m_j = \frac{1}{2} \sum_i t_i(e'_{i, j} - e_{i, j})\in \mathbb{Z}
```
として$X = \prod_{j = 0}^{\ell} p_j^{m_j}\in\mathbb{Z}$を定めると

```math
X^2 = \prod_{j = 0}^{\ell} p_j^{\sum_i t_i(e'_{i, j} - e_{i, j})} = \prod_i \left( \prod_{j=0}^\ell p_j^{e_{i, j}' - e_{i, j}} \right)^{t_i} \equiv 1 \pmod{N}
```
より$N|X^2-1$なので$\gcd(X\pm 1,N)$が$N$の非自明な素因数を与えることが期待される。
格子を用いた素因数分解法では、$p_\ell$-平滑な関係対$(u_i, v_i)$を集める作業をある格子上の最近ベクトル問題に帰着させている。

# 格子を用いた素因数分解法
## Schnorrによる方法

```math
\boldsymbol{R}_{n, c} = \begin{bmatrix}
\sqrt{\log p_1} & 0 & \cdots & 0 & N^c\log p_1\\
0 & \sqrt{\log p_2} & \cdots & 0 & N^c\log p_2\\
\vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 0 & \cdots & \sqrt{\log p_n} & N^c\log p_n
\end{bmatrix}
```

の各行ベクトルの張る格子$\mathcal{L}(\boldsymbol{R}_{n, c})$を考え、各基底ベクトルを$\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n$とする。また、目標ベクトル$\boldsymbol{t}$を

```math
\boldsymbol{t} = \begin{bmatrix}
0 & \cdots & 0 & N^c\log N
\end{bmatrix}
\in \mathbb{R}^{n+1}
```

で定義する。
この格子と目標ベクトルについて次の命題が成立している。

### 命題（Schnorr, 2021 3.3式）
$\displaystyle \boldsymbol{b}:=\sum_{i=1}^n e_i \boldsymbol{b} _ i $ を格子$\mathcal{L}(\boldsymbol{R}_{n, c})$上の格子ベクトルとし、二つの整数$u,v$を

```math
u = \prod_{e_i > 0} p_i ^ {e_i},~ v=\prod_{e_i<0}p_i ^ {e_i}
```

で定める。このとき、以下の不等式が成立する。

```math
\|\boldsymbol{b} - \boldsymbol{t}\|^2 \geq \ln \left( uv \right) + N^{2c} \left\lvert\ln \frac{u}{vN}\right\rvert^2
```
### 証明

```math
\begin{aligned}
\|\boldsymbol{b} - \boldsymbol{t}\|^2 &= \left\lVert \sum_{i=1}^n e_i \boldsymbol{b} _ i - \boldsymbol{t}\right\rVert ^ 2\\
&= \sum _ {i=1}^ n e_i^2 \log p_i + \left(\sum _ {i=1}^ n e_i  N^{c} \log p_i-N^c\log N \right)^2\\
&\ge \sum_{i=1}^n\lvert e_i \rvert \log p_i+N^{2c} \left\lvert\log \frac{\prod_{i=1}^n p^{e_i}}{N}\right\rvert^2\\
&=\log(uv)+N^{2c} \left\lvert\ln \frac{u}{vN}\right\rvert^2 \left(\because u = \prod_{e_i > 0} p_i ^ {e_i},~ v=\prod_{e_i<0}p_i ^ {e_i} \right)\\
Q.E.D.
\end{aligned}
```

この命題から、格子ベクトル$\boldsymbol{b}$と目標ベクトル$\boldsymbol{t}$が十分に近ければ、$\frac{u}{vN}$が$1$に近づき、$u-vN$が$p_n$-平滑になることが期待されるので、この方法によって$p_n$-平滑な関係対を集めようというのが、Schnorrによる方法のアイデアである。
しかし、$|u-vN|$については、[6]で$c$のみを増加させた場合は発散することが示され、格子階数$n$と$c$を増加させた場合も収束しないことが示唆されている。

## Yan et al.による改良

Yan et al.は$\sigma :\lbrace 1,\ldots,n\rbrace\to\lbrace 1,\ldots,n\rbrace$を$n$次の置換とし、更に$f(i)=\left\lfloor\frac{\sigma(i)}{2}\right\rceil$として

```math
\boldsymbol{B}_{n, c} = \begin{bmatrix}
f(1) & 0 & \cdots & 0 & \left\lfloor N^c\log p_1\right\rceil\\
0 & f(2) & \cdots & 0 & \left\lfloor N^c\log p_2\right\rceil\\
\vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 0 & \cdots & f(n) & \left\lfloor N^c\log p_n\right\rceil
\end{bmatrix}
```

の各行ベクトルの張る格子$L=\mathcal{L}(\boldsymbol{B}_{n, c})$に、対角成分を取り替えたものに変更し、すべて整数に丸めている。更に、目標ベクトルも

```math
\boldsymbol{t} = \begin{bmatrix}
0 & \cdots & 0 & \left\lfloor N^c\log N\right\rceil
\end{bmatrix}
\in \mathbb{Z}^{n+1}
```
と整数に丸めている。また、因子基底のサイズも格子階数$n$ではなく、$\ell=2n^2$としている。これは即ち、Schnorrのときと同様に定義された整数$u,v\in \mathbb{Z}$に対して$u-vN$が$p_\ell$-平滑でさえあれば良い。

# SageMathでの実装

## 基底行列の設計方法

基底を作る最も素朴な方法は毎回```for```文で回して作成する方法だろうが、SageMathはPythonベースの言語故```for```文は遅いだろうし、また、毎回１から作り直すのはあまりに肥効率なので、まず基底の外枠と対角成分だけ作っておいて、対角成分のみを毎回並び替えることにする。

```python
# 一番右の部分
B_right = np.array([np.ceil(100000 * np.log(P[1 : n + 1]))]).T
# 対角成分
S = np.ceil(np.arange(1, m) * 0.5)
```

尚、上で出てくる```P```は因子基底を意味しており```P = np.array([-1] + prime_range(Prime.unrank(K)))```というコードで生成している。この情報を基に各loop内で格子基底を構成する。

```python
for _ in range(factorial(n) // 2):
	# prime latticeの構成
	# seedを生成してから乱数的に並び替え
	seed(datetime.now().timestamp()); shuffle(S)
	# 組み合わせる
	C = Matrix(ZZ, np.hstack([np.diag(S), B_right]))
	# fpylllモジュールの組み込み函数を使用して最近ベクトルの操作をしたいので、変換
	B = IntegerMatrix.from_matrix(C)
	...
```

## uとvの作成

以下の様に$u,v$を作成する。これも、```for```文で回すのが最も素朴であるが、速度のために使用しないでいく。

```python
b = IntegerMatrix.from_iterable(1, B.nrows, map(lambda x: int(round(x)), b)); w = b * B
e = C.solve_left(vector(w[0])); e = np.array(e)
		
# 整数の組(u,v)を構成する
PositiveIndex = np.where(e > 0)
NegativeIndex = np.where(e < 0)
primes_for_u = Q[PositiveIndex[0] + 1]
primes_for_v = Q[NegativeIndex[0] + 1]
u_factor = primes_for_u ^ e[PositiveIndex[0]]
v_factor = primes_for_v ^ (-e[NegativeIndex[0]])
u = prod(vector(ZZ, u_factor))
v = prod(vector(ZZ, v_factor))
```

ここで、

```python
b = IntegerMatrix.from_iterable(1, B.nrows, map(lambda x: int(round(x)), b)); w = b * B
e = C.solve_left(vector(w[0])); e = np.array(e)
```
の部分で```w```に最近ベクトルの近似解を代入して、```B```は飽くまでLLL-reduceされた基底ベクトルなので、```e = C.solve_left(vector(w[0]))```で、LLL-reduction前の“元の”基底の係数ベクトルを```e```に代入している。

また
```python
PositiveIndex = np.where(e > 0)
NegativeIndex = np.where(e < 0)
primes_for_u = Q[PositiveIndex[0] + 1]
primes_for_v = Q[NegativeIndex[0] + 1]
u_factor = primes_for_u ^ e[PositiveIndex[0]]
v_factor = primes_for_v ^ (-e[NegativeIndex[0]])
u = prod(vector(ZZ, u_factor))
v = prod(vector(ZZ, v_factor))
```

の箇所において、初めの四行で係数が負となるindexと正となるindexをそれぞれ取得した上で、そのindexに対応する素数を```primes_for_u```と```primes_for_v```に入れている。それ以下の部分で```primes_for_u```の各要素の正の係数乗、```primes_for_v```の各要素の負の係数乗を計算し総乗している。なお、Sageの```vector(ZZ)```にして総乗しているのはオーバーフローを避けるためである（何度かそれらしいことで失敗した）。

## 平滑な関係対の収集

$u$と$v$が設定できたとしても、$u-vN$が平滑でなければ意味がない。$u-vN$の平滑性を調べるためにSageで素因数分解を行う組み込み函数```factor```を使い素因数分解して調べてから収集を行う。

```python
LT = np.array(factor(u - v * N))
Lu = np.array(factor(u))
L = LT.T; M = Lu.T
if len(L) > 0:
	if set(L[0]) <= set(P):# 平坦性のチェック
		vec = zero_vector(ZZ, K)
		for p in np.r_[L[0], M[0]]:
			e1 = e2 = 0
			j = np.where(P == p); j = j[0][0]
			if p in M[0]:
				index = np.where(Lu == p)
				e1 = Lu[index[0][0]][1]
			if p in L[0]:
				index = np.where(LT == p)
				e2 = LT[index[0][0]][1]
			vec[j - 1] = e2 - e1
		if vec not in List:
			num += 1
			print(num, "sr-pairs are found. u =", u,"v =", v)
			List.append(vec)
			AA = Matrix(GF(2), List)
			r = AA.rank()
```

ここで

```python
for p in np.r_[L[0], M[0]]:
	e1 = e2 = 0
	j = np.where(P == p); j = j[0][0]
	if p in M[0]:
		index = np.where(Lu == p)
		e1 = Lu[index[0][0]][1]
	if p in L[0]:
		index = np.where(LT == p)
		e2 = LT[index[0][0]][1]
	vec[j - 1] = e2 - e1
```

の部分では、$u$と$u-vN$のすべての素因数$p_j$に対して、$u$を素因数分解したときの$p_j$の肩の数$e_1$、$u-vN$を素因数分解したときの$p_j$の肩の数$e_2$を取得し、$\text{vec}\in\mathbb{Z}^\ell$について$\text{vec}_j=e_2-e_1$とする、ということを繰り返している。
更に、

```python
if vec not in List:
	num += 1
	print(num, "sr-pairs are found. u =", u,"v =", v)
	List.append(vec)
	AA = Matrix(GF(2), List)
	r = AA.rank()
```

では、`vec`を`List`に結合し、$\mathbb{F}_2$上の行列に変換し、その階数を`r`へ代入している。

## 素因数分解の実行
ここでは、十分な個数の$p_\ell$平滑な関係対が得られた状態で、今までで得られた情報をもとに、素因数分解に挑戦する。

```python
V = AA.kernel()
for tt in V:
	if not tt.is_zero():
		OneIndex = np.where(tt); OneIndex = OneIndex[0]
		Array = np.array(List); Array = Array[OneIndex]
		ee = vector(ZZ, Array.sum(axis = 0))
		if ee not in already_list:
			already_list.append(ee)

			ee = np.array(ee) // 2
			PositiveIndex = np.where(ee > 0)
			NegativeIndex = np.where(ee < 0)

			X = Y = R(1)
			for j in PositiveIndex[0]: X *= R(P[j + 1]) ^ ee[j]
			for j in NegativeIndex[0]: Y *= R(P[j + 1]) ^ (-ee[j])

			print("X =", X, "Y =", Y)
			if X != Y: p = gcd(ZZ(X - Y), N)
			else: p = gcd(ZZ(X + Y), N)
```

ここでは、$\mathbb{F}_2$上の行列`AA`の核のすべての元`tt`について、`ee`に
$\displaystyle \sum _ {\texttt{tt}_j = 1} \frac{\texttt{List} _ j}{2}$を入れて、`ee`の要素が正になる任意のindex $j$に対して$p_j ^ {\texttt{ee} _ j}$の総乗を`X`へ、負になる任意のindex $k$に対して$p_k ^ {\texttt{ee} _ k}$の総乗を`Y`へ代入している。あとは$\gcd(\texttt{X}\pm\texttt{Y},N)$が非自明な因子になるかを調べればよい。

```python:lattice_factorization.py
from fpylll import *
from time import perf_counter
from datetime import datetime
from random import seed, shuffle
import numpy as np

c = 4
N = ZZ(input("N = "))
if N < 100: N = gen_semiprime(N)
R = Integers(N)

# 格子階数の設定
bit_size = N.nbits()
if bit_size >= 40:
	n = round(2.2 * bit_size / log(bit_size) - 8); m = n + 1
else:
	n = 15; m = 16
J = n * n
K = J + J

# 因子基底の構成
Prime = Primes()
P = np.array([-1] + prime_range(Prime.unrank(K)))
Q = P; P = vector(ZZ, P)

# 目標ベクトルの設定
t = vector(ZZ, m); t[n] = ceil(10 ^ c * log(N))

# 素数基底の設定
B_right = np.array([np.ceil(10 ^ c * np.log(P[1 : n + 1]))]).T
S = np.ceil(np.arange(1, m) * 0.5)
List = []; num = 0; loop_times = 0; already_list = []; f: bool = False; r = 0

start = perf_counter()
# 格子を用いた素因数分解法
for _ in range(factorial(n) // 2):
	loop_times += 1
    
	# prime latticeの構成
	seed(datetime.now().timestamp()); shuffle(S)
	C = Matrix(ZZ, np.hstack([np.diag(S), B_right]))
	B = IntegerMatrix.from_matrix(C)

	# LLL-reductionで基底簡約
	LLL.reduction(B)
	M = GSO.Mat(B); _ = M.update_gso()
	
	# Babaiの最近平面法で、最近ベクトル問題の近似解を求める
	w = M.babai(t)
    
	# Babai法で得られた格子ベクトルよりも目標ベクトルに近い格子ベクトルを数え上げる
	radius = (vector(ZZ, B.multiply_left(w)) - t).norm()
	enum = Enumeration(M, strategy = EvaluatorStrategy.BEST_N_SOLUTIONS)
	solutions = enum.enumerate(0, n, radius * radius + 1, 0, M.from_canonical(t))

	for _, b in solutions:
		b = IntegerMatrix.from_iterable(1, B.nrows, map(lambda x: int(round(x)), b)); w = b * B
		e = C.solve_left(vector(w[0])); e = np.array(e)
		
		# 整数の組(u,v)を構成する
		PositiveIndex = np.where(e > 0)
		NegativeIndex = np.where(e < 0)
		primes_for_u = Q[PositiveIndex[0] + 1]
		primes_for_v = Q[NegativeIndex[0] + 1]
		u_factor = primes_for_u ^ e[PositiveIndex[0]]
		v_factor = primes_for_v ^ (-e[NegativeIndex[0]])
		u = prod(vector(ZZ, u_factor))
		v = prod(vector(ZZ, v_factor))

		
		LT = np.array(factor(u - v * N))
		Lu = np.array(factor(u))
		L = LT.T; M = Lu.T
		if len(L) > 0:
			if set(L[0]) <= set(P):# 平坦性のチェック
				vec = zero_vector(ZZ, K)
				for p in np.r_[L[0], M[0]]:
					e1 = e2 = 0
					j = np.where(P == p); j = j[0][0]
					if p in M[0]:
						index = np.where(Lu == p)
						e1 = Lu[index[0][0]][1]
					if p in L[0]:
						index = np.where(LT == p)
						e2 = LT[index[0][0]][1]
					vec[j - 1] = e2 - e1
				if vec not in List:
					num += 1
					print(num, "sr-pairs are found. u =", u,"v =", v)
					List.append(vec)
					AA = Matrix(GF(2), List)
					r = AA.rank()

	if len(List) > r:
		V = AA.kernel()
		for tt in V:
			if not tt.is_zero():
				OneIndex = np.where(tt); OneIndex = OneIndex[0]
				Array = np.array(List); Array = Array[OneIndex]
				ee = vector(ZZ, Array.sum(axis = 0))
				if ee not in already_list:
					already_list.append(ee)

					ee = np.array(ee) // 2
					PositiveIndex = np.where(ee > 0)
					NegativeIndex = np.where(ee < 0)

					X = Y = R(1)
					for j in PositiveIndex[0]: X *= R(P[j + 1]) ^ ee[j]
					for j in NegativeIndex[0]: Y *= R(P[j + 1]) ^ (-ee[j])

					print("X =", X, "Y =", Y)
					if X != Y: p = gcd(ZZ(X - Y), N)
					else: p = gcd(ZZ(X + Y), N)
					
					if 1 < p < N:
						print("==============================\nN =",
							N, ", bit size = ", bit_size, 
							"\nc = ", c, ", beta = 2.0\nN = ", p, "*", N / p, 
							"\nloop times = ", loop_times, 
							"\nnumber of sr-pairs =", num, 
							"\n==============================")
						f = True; break
				if f:
					break
		if f:
			break

end = perf_counter()
if f: print(end - start, "[secs]")
else: print("Factorization failed.")
```

ここで、`gen_semiprime`はランダムな半素数を生成する函数であり、次のコードで生成している。

```python: gen_semiprime.py
def gen_semiprime(n):
	while 1:
		p = next_prime(randint(2 ^ ((n - 1) // 2), 2 ^ ((n + 1) // 2)))
		q = next_prime(randint(2 ^ ((n - 3) // 2), 2 ^ ((n + 1) // 2)))
		N = p * q
		if N.nbits() == n and p != q: return N
```

# 実装結果
この実験にはIntel Core i7-1355U @ 1.70 GHzを用いた。
$20$ビット半素数$N = 602579$の場合は以下。

```:出力
N = 20
1 sr-pairs are found. u = 271753345 v = 451
2 sr-pairs are found. u = 646522481 v = 1073
3 sr-pairs are found. u = 24697093 v = 41
4 sr-pairs are found. u = 602301 v = 1
5 sr-pairs are found. u = 13857057 v = 23
6 sr-pairs are found. u = 602485 v = 1
7 sr-pairs are found. u = 13850386 v = 23
...
39 sr-pairs are found. u = 172895117 v = 287
X = 24576 Y = 193652
==============================
N = 602579 , bit size =  20
c =  4 , beta = 2.0
N =  983 * 613
loop times =  69
number of sr-pairs = 39
==============================
2.5130279930000086 [secs]
```

$30$ビット半素数$N = 894667853$の場合

```:出力
N = 30
1 sr-pairs are found. u = 16989269465 v = 19
2 sr-pairs are found. u = 894417797 v = 1
3 sr-pairs are found. u = 3578643875 v = 4
4 sr-pairs are found. u = 36677636515 v = 41
5 sr-pairs are found. u = 1788950511 v = 2
6 sr-pairs are found. u = 894517254 v = 1
7 sr-pairs are found. u = 894773627 v = 1
...
127 sr-pairs are found. u = 25947033475 v = 29
X = 480136814 Y = 782817591
==============================
N = 894667853 , bit size =  30
c =  4 , beta = 2.0
N =  30259 * 29567
loop times =  937
number of sr-pairs = 127
==============================
41.698412693999984 [secs]
```

$40$ビット半素数$N = 730085796257$の場合

```:出力
N = 40
1 sr-pairs are found. u = 31380966957549 v = 43
2 sr-pairs are found. u = 729631962009 v = 1
3 sr-pairs are found. u = 1459407529269 v = 2
4 sr-pairs are found. u = 25554518110771 v = 35
5 sr-pairs are found. u = 729573108825 v = 1
6 sr-pairs are found. u = 730004400457 v = 1
7 sr-pairs are found. u = 729896629825 v = 1
...
299 sr-pairs are found. u = 3650461562462 v = 5
X = 370497004722 Y = 635572826345
X = 106409623324 Y = 349031220746
X = 629344165616 Y = 665960445318
X = 183868597978 Y = 239478744779
X = 627587837482 Y = 406374531489
==============================
N = 730085796257 , bit size =  40
c =  4 , beta = 2.0
N =  990163 * 737339
loop times =  13916
number of sr-pairs = 299
==============================
1588.453225263 [secs]
```

# パラメータを変えて実行

`c = 7`としたとき

```:出力
N = 894667853
1 sr-pairs are found. u = 10890790784126 v = 12173
2 sr-pairs are found. u = 29524030783 v = 33
3 sr-pairs are found. u = 370392186305 v = 414
4 sr-pairs are found. u = 4912617467758 v = 5491
5 sr-pairs are found. u = 1271322323674 v = 1421
6 sr-pairs are found. u = 7446313773250 v = 8323
7 sr-pairs are found. u = 500119232074 v = 559
...
182 sr-pairs are found. u = 171776238965 v = 192
X = 377314074 Y = 753495015
==============================
N = 894667853 , bit size =  30
c =  7 , beta = 2.0
N =  29567 * 30259
loop times =  3074
number of sr-pairs = 182
==============================
172.25563198099996 [secs]
```

`c = 2`のとき

```:出力
N = 894667853
1 sr-pairs are found. u = 896671875 v = 1
2 sr-pairs are found. u = 834840743 v = 1
3 sr-pairs are found. u = 863492135 v = 1
4 sr-pairs are found. u = 16567436743 v = 19
5 sr-pairs are found. u = 2565726409 v = 3
6 sr-pairs are found. u = 1733567017 v = 2
7 sr-pairs are found. u = 861871747 v = 1
...
163 sr-pairs are found. u = 867782630 v = 1
X = 709920557 Y = 747229904
==============================
N = 894667853 , bit size =  30
c =  2 , beta = 2.0
N =  30259 * 29567
loop times =  1202
number of sr-pairs = 163
==============================
42.14274347700007 [secs]
```

# 参考文献

[1] Claus Peter Schnorr. _Factoring_ _integers_ _and_ _computing_ _discrete_ _logarithms_ _via_ _Diophantine_ _approximation_. In Advances in Computational Complexity Theory, pp171–181, 1991.
[2] Claus Peter Schnorr. _Fast_ _factoring_ _integers_ _by_ _SVP_ _algorithms_, _corrected_. Cryptology ePrint Archive, Paper 2021/933, 2021. https://eprint.iacr.org/2021/933
[3] Bao Yan, Ziqi Tan, Shijie Wei, Haocong Jiang, Weilong Wang, Hong Wang, Lan Luo, Qianheng Duan, Yiting Liu, Wenhao Shi, Yangyang Fei, Xiangdong Meng, Yu Han, Zheng Shan, Jiachen Chen, Xuhao Zhu, Chuanyu Zhang, Feitong Jin, Hekang Li, Chao Song, Zhen Wang, Zhi Ma, H. Wang, and Gui-Lu Long. _Factoring_ _integers_ _with_ _sublinear_ _resources_ _on_ _a_ _superconducting_ _quantum_ _processor_. arXiv preprint arXiv:2212.12372, 2022.
[4] 山口純平, 伊豆哲也, and 國廣昇. 格子と最適化手法を用いた素因数分解法の実験報告. 2023. 情報処理学会研究報告.
[5] 佐藤新, Aurélien Auzemery, 片山瑛, and 安田雅哉. 近似最近ベクトル探索と埋め込み法を用いた格子による素因数分解法の実装報告. SCIS2024 予稿集, 2024. 
[6] 谷仁裕, 長谷川直樹, and 藤崎英一郎. Schnorrの格子問題に基づく素因数分解アルゴリズムについての考察. SCIS2024 予稿集, 2024.