格子アルゴリズムの開発とその素因数分解への応用
>100 Views
February 14, 26
スライド概要
2024年度，修士論文報告会の発表資料です
立教大学大学院で，格子基底簡約アルゴリズムに関する研究をしています． 趣味でゲーム開発も行ってます． C++ | Go | Python | SageMath | Asir | Bash NTL | Eigen | DXライブラリ Visual Studio
関連スライド
各ページのテキスト
格子アルゴリズムの開発とその素因数分解への応用 Development of Lattice Algorithms and Its Application for Integer Factorization 佐藤 新 2025 年 2 月 17 日（水） 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 1 / 35
本修士研究で行ったこと 格子アルゴリズムの開発 ▶ ▶ 停止性の保証された新しい格子基底簡約アルゴリズムを開発 国内会議 SCIS2025 で，「自己双対型 PotBKZ 基底簡約の提案と BKZ との比較」 （佐藤新，安田雅哉）の題目で発表 格子を用いた素因数分解の実装実験 既存のアルゴリズムでどの程度の大きさの合成数の素因数分解が可能か報告 得られた実験値から計算量がどのように振る舞うのか解析 ▶ 国内会議 SCIS2024 で， 「近似最近ベクトル探索と埋め込み法を用いた格子による 素因数分解法の実装報告」 （佐藤新，Aurélien Auzemery，片山瑛，安田雅哉）の題 目で発表 ▶ 査読付き国際学会 IWSEC2024 で， 「Experimental Analysis of Integer Factorization Methods Using Lattices」 （佐藤新，Aurélien Auzemery，片山瑛，安田雅哉）の題目 で発表 ▶ ▶ 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 2 / 35
研究背景 格子暗号の安全性評価と基底簡約アルゴリズム 格子暗号は次世代暗号の一つ ▶ ▶ 安全性は後に紹介する格子問題の求解困難性に基づく 格子暗号の安全性評価には，格子問題の求解困難性評価が必要 基底簡約は格子問題の求解に必須の技術 ▶ ▶ LLL [6] ⇝ 格子次元に関して多項式時間計算量 BKZ [10] やその改良 ⇝ ブロックサイズに関して指数時間計算量 BKZ は強力な基底簡約アルゴリズムで，安全性解析における標準ツール LLL と異なり，BKZ の停止性は理論的には保証されてない ⋆ 実用上，実行時間や繰り返し（ツアー）回数に上限を設けて強制停止 ⋆ ⋆ 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 4 / 35
本研究の目的 停止性を保証する BKZ の変種の提案と BKZ との実験比較 1 停止性を保証する BKZ[10] の変種 PotBKZ を提案 ▶ 基底に対して定まるポテンシャル量を利用 ⋆ ▶ 2 ポテンシャル量は基底の良さを判断する量の一つ PotBKZ ではポテンシャル量を単調減少させる基底操作のみを行う =⇒ 多項式回のツアー回数で停止することが保証できる PotBKZ の様々な変種を開発＋実験比較 ▶ ▶ 双対型や自己双対型の PotBKZ まで開発 BKZ と実験比較：BKZ とのツアー回数，出力基底の品質を比較 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 5 / 35
数学的準備：格子の基礎 定義 1 (格子の GSO ベクトルと体積) 一次独立な b1 , . . . , bn の整数係数の一次結合全体 P L = L(b1 , . . . , bn ) := { ni=1 ai bi | a1 , . . . , an ∈ Z} を格子，{b1 , . . . , bn } を基底，n を次元と呼ぶ． b⋆1 := b1 , b⋆i := bi − Pi−1 ⋆ ⋆ ⋆ 2 j=1 µi,j bj , µi,j := ⟨bi , bj ⟩/∥bj ∥ で定義される b⋆1 , . . . , b⋆n を GSO ベクトル，µ = (µi,j ) を GSO 係数行列と呼ぶ． 格子 L の体積を vol(L) = Qn ⋆ i=1 ∥bi ∥ と表し，これは基底のとり方によらない 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 6 / 35
数学的準備：格子問題，基底簡約とは 格子問題 {b1 , . . . , bn }：n 次元格子 L の基底 最短ベクトル問題（SVP）：∥v∥ を最小にする非零な v ∈ L を一つ見つけよ，とい う問題 ▶ 最近ベクトル問題（CVP） ：与えられた目標ベクトル t ∈ Rn \ L に対し，∥v − t∥ を最小にする v ∈ L を一つ見つけよ，という問題 ▶ 63425 78873 69323 50254 21085 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 (−3, −5, 1, 1, 1) SVP の解 0 0 0 CVP の解 (35605, 55896, 75401, 54327, 59522) 1 目標ベクトル t = (35608, 55896, 75400, 54329, 59521) 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 7 / 35
数学的準備：基底簡約の概要 基底簡約：長く平行に近い基底を短く直交に近い基底に変換する操作 格子の基底は無数に存在 良い基底の方が SVP や CVP などの格子問題が求解しやすい ▶ 代表的なアルゴリズム：LLL[6]，BKZ[10] ▶ ▶ 87349 0 0 0 −8 8 −1 3 −7 −9 83474 1 0 0 14 4 98247464 0 1 0 −2 −3 −11 16 基底簡約 847984 0 0 1 8 6 12 17 悪い基底 良い基底 基底のノルムが長くほぼ平行 基底のノルムが短くほぼ直交 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 8 / 35
準備：格子アルゴリズムとは 格子アルゴリズム格子に関するアルゴリズム全般 基底簡約アルゴリズム 悪い基底を良い基底に変換するアルゴリズム ENUM 与えられた格子上の最短ベクトルを数え上げるアルゴリズム 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 9 / 35
ポテンシャル量と LLL アルゴリズム
基底 {b1 , . . . , bn } のポテンシャル量
Pot({b1 , . . . , bn }) :=
LLL アルゴリズム [6]
次の条件を満たす基底を見つける
1
|µi,j | ≤ 1/2
2
2
δ · b⋆k−1 ≤ ∥πk−1 (bk )∥2
特に，条件 2 を満たさない
(bk , bk+1 ) を交換（Step 7）
▶
ポテンシャルが δ 倍ずつ減少
=⇒ 多項式時間で停止
Qn
⋆ 2(n−k+1)
>0
k=1 ∥bk ∥
Algorithm LLL 基底簡約アルゴリズム [6]
Require: 格子 L の基底 {b1 , . . . , bn }
定数 1/4 < δ < 1
Ensure: δ に関して LLL 簡約された基底
1: k ← 2
2: while k ≤ n do
3:
基底をサイズ簡約 [5]
4:
if 条件 2 を満たす then
5:
k ←k+1
6:
else
7:
swap(bk , bk+1 )
8:
k ← max{k − 1, 2}
佐藤
格子アルゴリズムの開発とその素因数分解への応用
2025 年 2 月 17 日（水）
10 / 35
DeepLLL アルゴリズムと PotLLL アルゴリズム 基底に対する deep-insertion という操作 σk,ℓ ({b1 , . . . , bn }) = {. . . , bk−1 , bℓ , bk , . . . , bℓ−1 , bℓ+1 . . .} DeepLLL アルゴリズム [10] PotLLL アルゴリズム [2] 次の条件を満たす基底を見つける 次の条件を満たす基底を見つける (1) |µi,j | ≤ 1/2 (1) |µi,j | ≤ 1/2 (2) δ · ∥b⋆i ∥2 ≤ ∥πi (bk )∥2 (2’) δ · Pot(B) ≤ Pot(σk,ℓ (B)) 条件 2 を満たさない基底を 条件 2’ を満たさない基底を deep-insertion で入れ替え deep-insertion で入れ替え ▶ ポテンシャルは増えたり減ったり ▶ Pot(B) を下げる deep-insertion のみ ▶ ポテンシャルが単調減少 =⇒ 指数時間 =⇒ 多項式時間で停止 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 11 / 35
PotENUM：PotLLL の一般化 Pot(B) を減少させる格子ベクトル v = ▶ ▶ Pm i=j vi bi (vm = 1) の数え上げ C = {. . . , bj−1 , v, bj , . . . , b| m , . . .}：j 番目に v を挿入+bm を除去 Pot(C) < Pot(B) （cf., PotLLL[2] では deep-insertion σj,m で得られる基底に限定） Pm 格子ベクトル v = i=j vi bi (vm = 1) に対して次は同値 Pm （Bi = ∥b⋆i ∥, Di = ℓ=i vℓ2 Bℓ ） 1. Pot(C) < Pot(B) 2. m Y Di < i=k m Y Bi i=k PotENUM では，式 2 を満たす格子ベクトル数え上げる ▶ 毎回ポテンシャルを計算するより計算コストを抑えられる 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 12 / 35
PotENUM：探索方法 D1 ≥ D2 ≥ · · · ≥ Dm であるので D1 · · · Dm−1 < δB1 · · · Bm−1 を満たすと仮定すると Dkk · Dk+1 · · · Dm−1 < δB1 · · · Bm−1 1/k δB1 · · · Bm−1 ⇐⇒ Dk < =: Rk2 Dk+1 · · · Dm−1 が成立する．PotENUM は，上の式を満たす格子ベクトルを探索する 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 13 / 35
PotBKZ（1/2） ：BKZ との構成の差異 今回開発 PotBKZ BKZ[10] LLL[6] ENUM[3] PotLLL[2] PotENUM 今回開発 PotBKZ では BKZ の LLL を PotLLL に，ENUM を PotENUM に置き換え PotLLL と PotENUM はどちらもポテンシャルを単調減少 ▶ PotENUM が呼ばれる回数（ツアー回数）は格子次元に関して多項式的 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 14 / 35
PotBKZ（2/2）
：アルゴリズムの概要
Algorithm PotBKZ 基底簡約アルゴリズム
Require: n 次元格子の基底 {b1 , . . . , bn }，簡約変数 1/4 < δ < 1
Ensure: 簡約された基底 {b1 , . . . , bn }
1: {b1 , . . . , bn } ← PotLLL({b1 , . . . , bn }, δ) /* BKZ[10] では LLL[6] を利用*/
2: z ← 0
3: while z < n − 1 do
4:
j ← (j mod n − 1) + 1; k ← min(j + β − 1, n)
5:
v ← PotENUM(πj (bj ), . . . , πj (bk )) /* BKZ では ENUM[3] で最短ベクトルを探索*/
6:
if no solution then
7:
z ←z+1
8:
else
9:
{b1 , . . . , bn } ← MLLL({. . . , bj , v, bj+1 , . . .}, δ) /* MLLL[10] で一次独立性を除く*/
10:
{b1 , . . . , bn } ← PotLLL({b1 , . . . , bn }, δ)
11:
z←0
佐藤
格子アルゴリズムの開発とその素因数分解への応用
2025 年 2 月 17 日（水）
15 / 35
自己双対型 PotBKZ ：自己双対型 BKZ との構成の差異 b = x ∈ Rn 格子 L の双対格子：L b の基底 D = (B ⊤ )−1 の各行が L ∀ y ∈ L, ⟨x, y⟩ ∈ Z 自己双対型 BKZ[7] BKZ[10] 双対型 BKZ[7] 今回開発 自己双対型 PotBKZ 双対型 PotBKZ 今回開発 PotBKZ 自己双対型 PotBKZ は PotBKZ とその双対型を交互に呼び出す 双対型 PotBKZ を開発 ▶ 双対型 PotENUM⇝双対基底への挿入でポテンシャルが減少するベクトルの数え上げ 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 16 / 35
実験結果（1/3）：実装方法と実験方法 実装方法 実装は総て C++言語で NTL ライブラリ [11] と Eigen ライブラリ [4] を使用 g++でコンパイル ▶ コンパイルオプションは-O3 -mtune=native -march=native -mfpmath=both ▶ 基底は long 型，GSO 情報は long double 型を使用 ▶ ▶ 実験方法 ▶ ▶ SVP-challenge[1] のシード 0〜9 で実行 ツアー回数，ポテンシャル量の対数値，GSA スロープの傾きの平均をとる ⋆ GSA スロープの傾きは良い基底を判断する指標の一つ（小さい方が良い） 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 17 / 35
実験結果 (2/3)：100 次元のポテンシャル量の変化 #,;ͷϙςϯγϟϧྔ 1PU#,;ͷϙςϯγϟϧྔ ࣗݾରܕ1PU#,;ͷϙςϯγϟϧྔ ϙςϯγϟϧྔͷର πΞʔ PotBKZ は 1 ツアー目で一気にポテンシャルが低くなり，その後 2 ツアーで停止 自己双対型 PotBKZ も同様の挙動を取り 4 ツアーで停止 ▶ PotBKZ より小さいポテンシャル量をとる 一方，BKZ[10] は緩やかに減少し，その後 7 ツアー目頃から停滞を続ける 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 18 / 35
実験結果 (3/3)： 実験結果 Intel Core i7-1355U @ 1.70 GHz 上で実験 ブロックサイズは β = 40 を選択 ▶ PotBKZ は約 2 回程度のツアー回数で停止 ▶ 自己双対型 PotBKZ も約 5 回程度のツアー回数で停止 ▶ ▶ ⋆ ▶ 格子 階数 100 110 120 PotBKZ よりも低い GSA スロープの傾きとポテンシャル量の対数値の比をとる 一方, BKZ[10] と比較すると高く，十分に下げられていない BKZ[10] ツアー 回数 ≥ 20 ≥ 20 ≥ 20 PotBKZ log Pot の比 −ρ 0.9668 0.9658 0.9616 0.0553 0.0561 0.0558 ツアー 回数 1.9 1.9 1.7 log Pot の比 −ρ 0.9735 0.9722 0.9685 0.0615 0.0617 0.0612 自己双対型 PotBKZ ツアー log Pot −ρ 回数 の比 4.8 0.9714 0.0595 5.2 0.9697 0.0594 5.9 0.9665 0.0597 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 19 / 35
PotBKZ とその変種の公開ソースコード 本研究の成果となるソースコードを GitHub にて公開 https://github.com/satoshin-des/self-dual-PotBKZ ファイル構成 ┣━━ src ┃ ┃ ┃ ┗━━各種ソース（SelfDualPotBKZ.h，PotBKZ.h など） ┣━━ svp_challenge_list ┃ ┃ ┃ ┗━━テストケースとして svp challenge[1] の基底（LLL 済） ┣━━ libSDPotBKZ.so ┃ ⇝C++ファイルをコンパイルした共有ライブラリ ┗━━ excample.py ⇝libSDPotBKZ.so を python で動かすテストコード 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 20 / 35
本研究の目的 1 格子を用いた素因数分解法の古典計算機上での実装報告 ▶ 2 既存アルゴリズムで, どの程度のサイズの合成数の素因数分解が可能か報告 実験的な計算量の振る舞いを解析 ▶ 数体篩法などの素因数分解法より高速になりうるか議論 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 22 / 35
平方差法の処理手順 1 平滑な関係対の探索 N を素因数分解したい合成数，pi を i 番目の素数（p0 = −1）とする．(ℓ + 2) 個 の異なる Q Q e′ e ui = ℓj=0 pj i,j , ui − vi N = ℓj=0 pj i,j と素因数分解できる整数の組 (ui , vi ) を見つける（格子を利用した探索法は後述） 2 非自明な素因子の探索 Pℓ+2 このとき, ∃ (t1 , t2 , . . . , tℓ+2 ) ̸= 0 s.t. i=1 ti (e′i,j − ei,j ) ≡ 0 (mod 2). Qℓ Pℓ+2 mj 1 ′ X := j=0 pj ∈ Z mj := 2 i=1 ti (ei,j − ei,j ) ∈ Z とすると X2 ≡ 1 (mod N ) =⇒ gcd(X ± 1, N ) が N の非自明な素因子かも 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 23 / 35
Schnorr の格子と平滑な関係対の探索 (1/2) Schnorr[8] による格子と CVP の構成 ▶ c > 0: 与えられた調整パラメータ √ log p1 √ 0 0 log p2 Rn,c := .. .. . . 0 0 ··· ··· .. . 0 0 .. √ . ··· log pn N c log p1 b c N log p2 .1 = .. .. . bn c N log pn の行ベクトルで生成される格子 L = L(Rn,c ) 上で t := 0 · · · 0 N c log N ∈ Rn+1 を目標ベクトルとする CVP を考える. 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 24 / 35
Schnorr の格子と平滑な関係対の探索 (2/2) Schnorr の格子 L = L(Rn,c ) の性質 [9, Section 3] b := u := Pn Q i=1 ei bi ：格子 L 上の格子ベクトル (ei ∈ Z) Q −ej ej ∈Z p , v := j ej <0 pj ej >0 N 2c ≫ ln(uv) =⇒ ∥b − t∥2 ≳ N 2c ln u 2 . vN 平滑な関係対の探索の近似 CVP への帰着 b ≈ t のとき |u − vN Q | が小さくなる e ⇝ u − vN = ℓj=0 pj j と素因数分解できる可能性が高まる 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 25 / 35
実験結果 (1/3)：実装方法と実験方法 実装方法 ▶ ▶ 実装は総て C++言語で NTL ライブラリ [11] を使用 g++でコンパイル 実験方法 ランダムに生成した RSA 型の合成数を格子素因数分解法で分解 Yan ら [12] による変形格子を用いて実験 ▶ 実験的に実行時間の最も短くなる格子次元をとり，Yan ら [12] の先行研究をもと に他のパラメタ（c や ℓ）をとった ▶ ▶ 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 26 / 35
実験結果 (1/2)：格子素因数分解法の処理時間と成功確率 実験結果 Intel Xeon Gold 5222 CPU @ 3.80 GHz のシングルコア上で実験 O(m/ ln m) のサイズの格子を用いて 3 日強で 90 ビット合成数の素因数分解に成功 ▶ 一方, N のビット長が増大すると, 整数の組 (u , v ) の探索の成功確率は急激に減少 i i ▶ ▶ 合成数 N のビット長 m (m = ⌈log N ⌉) 60 70 80 90 n = O(m) の場合 n = ⌊0.55m⌋, c = 5.0, ℓ = 2n n 成功確率 処理時間 33 0.028% 9.2 時間 38 < 0.001% >3日 – – – – – – n = O(m/ ln m) の場合 n = ⌊2.3m/ ln m⌋, c = 5.0, ℓ = 2n2 n 成功確率 処理時間 23 6.6% 5.1 分 26 2.2% 57.5 分 29 0.75% 8.3 時間 31 0.17% 83.3 時間 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 27 / 35
実験結果 (2/2)：整数の組の探索の成功確率について TVDDFTTQSPCBCJMJUZ $BTFPG m ( /ln m) p = 40.5286977 × 0.8977569455m TVDDFTTQSPCBCJMJUZ $BTFPG(m) p = 4078.2008 × 0.756867758m pʢTVDDFTTQSPCBCJMJUZʣ mʢCJUTJ[Fʣ CVP 近似解による整数の組の探索成功確率は m に関して指数的に減少 ⇝ 1 つの整数の組を見つけるのに, 指数回数分の格子の取り直しが必要 ⇝ 格子素因数分解法の計算量は, m に関して指数時間の振る舞い 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 28 / 35
まとめ（1/2）：新しい格子アルゴリズムの開発 PotBKZ と自己双対型 PotBKZ の開発と実験 ポテンシャルの単調減少により停止性の保証された BKZ[10] の変種 基底への挿入でポテンシャルが減少するベクトルを数え上げる PotENUM を開発 ▶ その双対版，自己双対版を開発 ▶ 120 次元格子での実験結果 ▶ ▶ ⇝ PotBKZ は 2 ツアー程度，自己双対型 PotBKZ は 5 ツアー程度で停止 ⇝ BKZ は途中で止めているが，基本的に停止しない 今回の実験結果から得られた知見 ▶ PotBKZ や自己双対型 PotBKZ は BKZ ほどポテンシャルを下げれない ⋆ ⋆ より大きなブロックサイズを試せばBKZ 程度の品質が出せると期待 より大きなブロックサイズの利用のため，枝切りや篩の適用をしたい 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 29 / 35
まとめ（2/2）：格子を用いた素因数分解法の実装実験 格子を用いた素因数分解法を古典計算機上で実験 合成数のビット長 m に対して O(m) と O(m/ ln m) の格子を採用 O(m/ ln m) の場合，3 日強で 90 ビット合成数の素因数分解に成功 （Cf., これ以前は 55 ビットまでの実装報告 [13]） より洗練されたパラメタの取り方をしたためより大きいサイズの合成数の素因 数分解が成功 ▶ 各 N に対して最良な格子次元を選択し，それに近いオーダーの n を選択 今回の実験結果から得られた知見 ビット長が増大すると, 整数の組の探索の成功確率は指数的に減少 ⇝ 格子を用いた素因数分解法は指数時間計算量の振る舞い （これは古典・量子計算機の違いに依らない） ⇝ 準指数時間計算量の数体篩法より非効率 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 30 / 35
参考文献 I [1] TU Darmstadt. SVP challenge. Available at https://www.latticechallenge.org/svp-challenge/. [2] Felix Fontein, Michael Schneider, and Urs Wagner. PotLLL: A polynomial time version of LLL with deep insertions. Designs, Codes and Cryptography, 73:355–368, 2014. [3] Nicolas Gama, Phong Q Nguyen, and Oded Regev. Lattice enumeration using extreme pruning. In Advances in Cryptology–EUROCRYPT 2010, volume 6110 of Lecture Notes in Computer Science, pages 257–278. Springer, 2010. 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 31 / 35
参考文献 II [4] Gaël Guennebaud, Benoît Jacob, et al. Eigen v3. http://eigen.tuxfamily.org, 2010. [5] C. Hermite. Extraits de lettres de M. Ch. Hermite à M. Jacobi sur différents objects de la théorie des nombres. Journal für die reine und angewandte Mathematik, 40:261–277, 1850. [6] Arjen Klaas Lenstra, Hendrik Willem Lenstra, and László Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982. 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 32 / 35
参考文献 III [7] Daniele Micciancio and Michael Walter. Practical, predictable lattice basis reduction. In Advances in Cryptology–EUROCRYPT 2016, volume 9665 of Lecture Notes in Computer Science, pages 820–849. Springer, 2016. [8] Claus Peter Schnorr. Factoring integers and computing discrete logarithms via Diophantine approximation. In Advances in Computational Complexity Theory, pages 171–181, 1991. [9] Claus Peter Schnorr. Fast factoring integers by SVP algorithms, corrected. Cryptology ePrint Archive, Paper 2021/933, 2021. https://eprint.iacr.org/2021/933. 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 33 / 35
参考文献 IV [10] Claus-Peter Schnorr and Martin Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical programming, 66:181–199, 1994. [11] Victor Shoup. NTL: A Library for doing Number Theory. http://www.shoup.net/ntl/. [12] Bao Yan, Ziqi Tan, Shijie Wei, Haocong Jiang, Weilong Wang, Hong Wang, Lan Luo, Qianheng Duan, Yiting Liu, Wenhao Shi, et al. Factoring integers with sublinear resources on a superconducting quantum processor. arXiv preprint arXiv:2212.12372, 2022. 佐藤 格子アルゴリズムの開発とその素因数分解への応用 2025 年 2 月 17 日（水） 34 / 35