多点評価は素因数分解の役に立つ
642 Views
June 07, 26
スライド概要
2026-06-06 に開かれた「競プロキャンプ 2026 関東」( https://connpass.com/event/382761 ) 内の LT 会への登壇資料．
素因数分解アルゴリズムの1つである楕円曲線法（Elliptic-Curve factorization Method; ECM）の Stage 2 に多点評価が現れることを示す．また多点評価（Multipoint Evaluation）の Rust による実装を2種類紹介し，実行時間を比較する．
関連スライド
Meta XR SDK(V66-74)でQuestアプリを開発
あうぜん
1.2M
各ページのテキスト
多点評価は素因数分解の役に立つ wasd314 2026-06-06 競プロキャンプ 2026 関東 – LT 会
自己紹介 • AtCoder: wasd3141 • yukicoder: wasd3142 • GitHub: wasd3143 • 使用言語 1. Python 2. C++ 3. Rust • 抽象代数学と整数論が好き • 本キャンプ 幹事 1https://atcoder.jp/users/wasd314 2https://yukicoder.me/users/14310 3https://github.com/wasd314 1 / 22
自己紹介 • AtCoder: wasd3141 • yukicoder: wasd3142 • GitHub: wasd3143 • 使用言語 1. Python 2. C++ 3. Rust • 抽象代数学と整数論が好き • 本キャンプ 幹事 1https://atcoder.jp/users/wasd314 2https://yukicoder.me/users/14310 3https://github.com/wasd314 1 / 22
初作問 @ yukicoder wasd314 さんの単発問題コンテスト (2025-11-02, 2 h) https://yukicoder.me/contests/575 2 / 22
初作問 @ yukicoder B 問題: No. 3332 Consecutive Power Sum (Small)1 • ネタバレ：𝑁 の素因数分解が要る • 𝑁 ≤ 1012 1https://yukicoder.me/problems/no/3332 3 / 22
初作問 @ yukicoder B 問題: No. 3332 Consecutive Power Sum (Small)1 • ネタバレ：𝑁 の素因数分解が要る • 𝑁 ≤ 1012 C 問題: No. 3333 Consecutive Power Sum (Large)2 • B 問題の制約強化版 • 𝑁 の素因数分解が要る 1https://yukicoder.me/problems/no/3332 2https://yukicoder.me/problems/no/3333 3 / 22
初作問 @ yukicoder B 問題: No. 3332 Consecutive Power Sum (Small)1 • ネタバレ：𝑁 の素因数分解が要る • 𝑁 ≤ 1012 C 問題: No. 3333 Consecutive Power Sum (Large)2 • B 問題の制約強化版 • 𝑁 の素因数分解が要る • 𝑵 ≤ 𝟏𝟎𝟐𝟒 1https://yukicoder.me/problems/no/3332 2https://yukicoder.me/problems/no/3333 3 / 22
Library Checker にも Factorize1 • 𝑁 ≤ 1018 • 10 s で 100 回 1https://judge.yosupo.jp/problem/factorize 4 / 22
Library Checker にも Factorize1 • 𝑁 ≤ 1018 • 10 s で 100 回 Factorize (Large)2 • 準備中 (PR #1400) 1https://judge.yosupo.jp/problem/factorize 2https://github.com/yosupo06/library-checker-problems/pull/1400 4 / 22
Library Checker にも Factorize1 • 𝑁 ≤ 1018 • 10 s で 100 回 Factorize (Large)2 • 準備中 (PR #1400) • 𝑵 ≤ 𝟏𝟎𝟑𝟖 ‣ ちなみに 2127 ∼ 1.70 × 1038 • 10 s で 10 回 1https://judge.yosupo.jp/problem/factorize 2https://github.com/yosupo06/library-checker-problems/pull/1400 4 / 22
今，素因数分解がアツい！
素因数分解のアルゴリズム 5 / 22
素因数分解のアルゴリズム 試し割り法 worst Θ(𝑁1/2 ) 時間 5 / 22
素因数分解のアルゴリズム 試し割り法 worst Θ(𝑁1/2 ) 時間 • AtCoder ABC-D が解ける1 • Consecutive Power Sum (Small) (𝑁 ≤ 1012 ) が解ける 1例: AtCoder – ABC169D (𝑁 ≤ 1012 ) 5 / 22
素因数分解のアルゴリズム Pollard’s 𝝆 expected 𝑂(𝑝1/2 ) ⊆ 𝑂(𝑁1/4 ) 時間 6 / 22
素因数分解のアルゴリズム Pollard’s 𝝆 expected 𝑂(𝑝1/2 ) ⊆ 𝑂(𝑁1/4 ) 時間 • AtCoder ABC-D が殴れる1 • Factorize (𝑁 ≤ 1018 ) が解ける • Consecutive Power Sum (Large) (𝑁 ≤ 1024 ) が解ける 1例: AtCoder – ABC284D (𝑁 ≤ 9 ⋅ 1018 , 𝑁 = 𝑝2 𝑞) 6 / 22
素因数分解のアルゴリズム では Factorial (Large) (𝑁 ≤ 1038 ) の想定解は？ 7 / 22
素因数分解のアルゴリズム では Factorial (Large) (𝑁 ≤ 1038 ) の想定解は？ 👉️ 楕円曲線法 (Elliptic-Curve factorization Method; ECM) 7 / 22
素因数分解のアルゴリズム では Factorial (Large) (𝑁 ≤ 1038 ) の想定解は？ 👉️ 楕円曲線法 (Elliptic-Curve factorization Method; ECM) 楕円曲線群を使って 𝑁 の素因数 𝑝 を expected exp[(√2 + 𝑜(1))√ln(𝑝) ln(ln(𝑝))] 時間 で見つける 7 / 22
楕円曲線群とは {(𝑥, 𝑦) ∈ 𝔽𝑝 × 𝔽𝑝 | 𝑦 2 = 𝑥 3 + 𝐶𝑥 2 + 𝑥} と無限遠点 𝑂 を合わせた集合 𝐸 8 / 22
楕円曲線群とは 8 / 22 {(𝑥, 𝑦) ∈ 𝔽𝑝 × 𝔽𝑝 | 𝑦 2 = 𝑥 3 + 𝐶𝑥 2 + 𝑥} と無限遠点 𝑂 を合わせた集合 𝐸 に加法・減法を定める： (𝑥1 , 𝑦1 ) ⊕ (𝑥2 , 𝑦2 ) ≔ (𝑥3 , 𝑦3 ) ただし 𝑥1 ≠ 𝑥2 の場合, 𝑚 ≔ (𝑦2 − 𝑦1 )/(𝑥2 − 𝑥1 ), 𝑥3 ≔ 𝑚2 − 𝐶 − 𝑥1 − 𝑥2 , 𝑦3 ≔ 𝑚(𝑥1 − 𝑥3 ) − 𝑦1 , { ⊖ (𝑥, 𝑦) ≔ (𝑥, −𝑦). (𝐸, ⊕, 𝑂, ⊖) は有限可換群をなし，これを楕円曲線群と呼ぶ
楕円曲線群とは 8 / 22 {(𝑥, 𝑦) ∈ 𝔽𝑝 × 𝔽𝑝 | 𝑦 2 = 𝑥 3 + 𝐶𝑥 2 + 𝑥} と無限遠点 𝑂 を合わせた集合 𝐸 に加法・減法を定める： (𝑥1 , 𝑦1 ) ⊕ (𝑥2 , 𝑦2 ) ≔ (𝑥3 , 𝑦3 ) ただし 𝑥1 ≠ 𝑥2 の場合, 𝑚 ≔ (𝑦2 − 𝑦1 )/(𝑥2 − 𝑥1 ), 𝑥3 ≔ 𝑚2 − 𝐶 − 𝑥1 − 𝑥2 , 𝑦3 ≔ 𝑚(𝑥1 − 𝑥3 ) − 𝑦1 , { ⊖ (𝑥, 𝑦) ≔ (𝑥, −𝑦). (𝐸, ⊕, 𝑂, ⊖) は有限可換群をなし，これを楕円曲線群と呼ぶ 点の整数倍 ⏟ 𝑃 + 𝑃 + ⋯ + 𝑃 を [𝑛]𝑃 と書く 𝑛個
ECM の戦略 点 𝑃 ∈ 𝐸 の整数倍を mod 𝑝 の代わりに mod 𝑁 で計算する 9 / 22
ECM の戦略 9 / 22 点 𝑃 ∈ 𝐸 の整数倍を mod 𝑝 の代わりに mod 𝑁 で計算する (𝑥1 , 𝑦1 ) ⊕ (𝑥2 , 𝑦2 ) ≔ (𝑥3 , 𝑦3 ) ただし 𝑥1 ≠ 𝑥2 の場合, 𝑚 ≔ (𝑦2 − 𝑦1 )/(𝑥2 − 𝑥1 ), 𝑥3 ≔ 𝑚2 − 𝐶 − 𝑥1 − 𝑥2 , 𝑦3 ≔ 𝑚(𝑥1 − 𝑥3 ) − 𝑦1 { 𝑥2 − 𝑥1 が可逆でないと失敗する ⋯⋯ これは和が 𝑂 になる場合に対応する
ECM の戦略 9 / 22 点 𝑃 ∈ 𝐸 の整数倍を mod 𝑝 の代わりに mod 𝑁 で計算する (𝑥1 , 𝑦1 ) ⊕ (𝑥2 , 𝑦2 ) ≔ (𝑥3 , 𝑦3 ) ただし 𝑥1 ≠ 𝑥2 の場合, 𝑚 ≔ (𝑦2 − 𝑦1 )/(𝑥2 − 𝑥1 ), 𝑥3 ≔ 𝑚2 − 𝐶 − 𝑥1 − 𝑥2 , 𝑦3 ≔ 𝑚(𝑥1 − 𝑥3 ) − 𝑦1 { 𝑥2 − 𝑥1 が可逆でないと失敗する ⋯⋯ これは和が 𝑂 になる場合に対応する が，もしそうなら gcd(𝑥2 − 𝑥1 , 𝑁) として 𝑝 が取り出せる
ECM の戦略 9 / 22 点 𝑃 ∈ 𝐸 の整数倍を mod 𝑝 の代わりに mod 𝑁 で計算する (𝑥1 , 𝑦1 ) ⊕ (𝑥2 , 𝑦2 ) ≔ (𝑥3 , 𝑦3 ) ただし 𝑥1 ≠ 𝑥2 の場合, 𝑚 ≔ (𝑦2 − 𝑦1 )/(𝑥2 − 𝑥1 ), 𝑥3 ≔ 𝑚2 − 𝐶 − 𝑥1 − 𝑥2 , 𝑦3 ≔ 𝑚(𝑥1 − 𝑥3 ) − 𝑦1 { 𝑥2 − 𝑥1 が可逆でないと失敗する ⋯⋯ これは和が 𝑂 になる場合に対応する が，もしそうなら gcd(𝑥2 − 𝑥1 , 𝑁) として 𝑝 が取り出せる 𝑷 を何倍かして mod 𝑝 で 𝑶 になるのを待つ
ECM 1. パラメータ 𝐵1 , 𝐵2 を決める 2. 楕円曲線群とその元 𝑃 を乱択する 3. (Stage 1) 𝑃 を 𝐿 倍した点 𝑄 ≔ [𝐿]𝑃 を求める • 𝐿 ≔ lcm(1, 2, …, 𝐵1 ) • 𝑄 = 𝑂 になったら成功 4. (Stage 2) [𝑘]𝑄 (1 ≤ 𝑘 ≤ 𝐵2 ) を求める • どれかが 𝑂 なら成功 5. 失敗したら 2. に戻る 10 / 22
ECM – Stage 2 4. (Stage 2) [𝑘]𝑄 (1 ≤ 𝑘 ≤ 𝐵2 ) を求める • どれかが 𝑂 なら成功 [1]𝑄, [2]𝑄, [3]𝑄, …, [𝐵2 ]𝑄 を愚直に列挙 & 𝑂 と比較 ⋯⋯ Ω(𝐵2 ) 時間かかる 11 / 22
ECM – Stage 2 4. (Stage 2) [𝑘]𝑄 (1 ≤ 𝑘 ≤ 𝐵2 ) を求める • どれかが 𝑂 なら成功 [1]𝑄, [2]𝑄, [3]𝑄, …, [𝐵2 ]𝑄 を愚直に列挙 & 𝑂 と比較 ⋯⋯ Ω(𝐵2 ) 時間かかる 𝑜(𝐵2 ) 時間にしたい 11 / 22
平方分割 12 / 22 𝐷 ≔ ⌈√𝐵2 ⌉ として 𝑘 ≕ 𝑖𝐷 + 𝑗 (𝑖, 𝑗 ∈ [0, 𝐷)) と表示すると ⟺ [𝑘]𝑄 ≡ 𝑂 (mod 𝑝) [𝑖𝐷]𝑄 + [𝑗]𝑄 ≡ 𝑂 (mod 𝑝) ⟺ [𝑖𝐷]𝑄 ≡ [−𝑗]𝑄 (mod 𝑝) 変数分離 ⟹ 𝑥([𝑖𝐷]𝑄) ≡ 𝑥([−𝑗]𝑄) (mod 𝑝) 𝑥 座標だけ見る ⟺ 𝐴𝑖 ≡ 𝐵𝑗 (mod 𝑝)
平方分割 12 / 22 𝐷 ≔ ⌈√𝐵2 ⌉ として 𝑘 ≕ 𝑖𝐷 + 𝑗 (𝑖, 𝑗 ∈ [0, 𝐷)) と表示すると ⟺ [𝑘]𝑄 ≡ 𝑂 (mod 𝑝) [𝑖𝐷]𝑄 + [𝑗]𝑄 ≡ 𝑂 (mod 𝑝) ⟺ [𝑖𝐷]𝑄 ≡ [−𝑗]𝑄 (mod 𝑝) 変数分離 ⟹ 𝑥([𝑖𝐷]𝑄) ≡ 𝑥([−𝑗]𝑄) (mod 𝑝) 𝑥 座標だけ見る ⟺ 𝐴𝑖 ≡ 𝐵𝑗 (mod 𝑝) ⟺ 𝑝 ∣ 𝐴𝑖 − 𝐵𝑗 ⟺ 𝑝 ∣ gcd(𝐴𝑖 − 𝐵𝑗 , 𝑁) ただし 𝐴𝑖 ≔ 𝑥([𝑖𝐷]𝑄) mod 𝑁, 𝐵𝑗 ≔ 𝑥([−𝑗]𝑄) mod 𝑁
平方分割 12 / 22 𝐷 ≔ ⌈√𝐵2 ⌉ として 𝑘 ≕ 𝑖𝐷 + 𝑗 (𝑖, 𝑗 ∈ [0, 𝐷)) と表示すると ⟺ [𝑘]𝑄 ≡ 𝑂 (mod 𝑝) [𝑖𝐷]𝑄 + [𝑗]𝑄 ≡ 𝑂 (mod 𝑝) ⟺ [𝑖𝐷]𝑄 ≡ [−𝑗]𝑄 (mod 𝑝) 変数分離 ⟹ 𝑥([𝑖𝐷]𝑄) ≡ 𝑥([−𝑗]𝑄) (mod 𝑝) 𝑥 座標だけ見る ⟺ 𝐴𝑖 ≡ 𝐵𝑗 (mod 𝑝) ⟺ 𝑝 ∣ 𝐴𝑖 − 𝐵𝑗 ⟺ 𝑝 ∣ gcd(𝐴𝑖 − 𝐵𝑗 , 𝑁) ただし 𝐴𝑖 ≔ 𝑥([𝑖𝐷]𝑄) mod 𝑁, 𝐵𝑗 ≔ 𝑥([−𝑗]𝑄) mod 𝑁 gcd(𝐴𝑖 − 𝐵𝑗 , 𝑁) たちを列挙すると依然 Ω(𝐷2 ) = Ω(𝐵2 ) 時間
問題の変形 gcd(𝐴𝑖 − 𝐵𝑗 , 𝑁) たちを列挙すると依然 Ω(𝐷2 ) = Ω(𝐵2 ) 時間 𝐴𝑖 − 𝐵𝑗 たちのどれかが 𝑝 の倍数と分かれば良い 13 / 22
問題の変形 13 / 22 gcd(𝐴𝑖 − 𝐵𝑗 , 𝑁) たちを列挙すると依然 Ω(𝐷2 ) = Ω(𝐵2 ) 時間 𝐴𝑖 − 𝐵𝑗 たちのどれかが 𝑝 の倍数と分かれば良い 各 𝑖 について gcd(∏ 𝐷−1 𝑗=0 (𝐴𝑖 − 𝐵𝑗 ), 𝑁) が求まれば良い
問題の変形 13 / 22 gcd(𝐴𝑖 − 𝐵𝑗 , 𝑁) たちを列挙すると依然 Ω(𝐷2 ) = Ω(𝐵2 ) 時間 𝐴𝑖 − 𝐵𝑗 たちのどれかが 𝑝 の倍数と分かれば良い 𝐷−1 各 𝑖 について gcd(∏ 𝑗=0 各 𝑖 について ∏ 𝐷−1 𝑗=0 (𝐴𝑖 − 𝐵𝑗 ), 𝑁) が求まれば良い (𝐴𝑖 − 𝐵𝑗 ) mod 𝑁 が求まれば良い
問題の変形 13 / 22 gcd(𝐴𝑖 − 𝐵𝑗 , 𝑁) たちを列挙すると依然 Ω(𝐷2 ) = Ω(𝐵2 ) 時間 𝐴𝑖 − 𝐵𝑗 たちのどれかが 𝑝 の倍数と分かれば良い 𝐷−1 各 𝑖 について gcd(∏ 𝑗=0 𝐷−1 各 𝑖 について ∏ 𝑗=0 (𝐴𝑖 − 𝐵𝑗 ), 𝑁) が求まれば良い (𝐴𝑖 − 𝐵𝑗 ) mod 𝑁 が求まれば良い 𝐷−1 • 𝐷 次多項式 𝐹(𝑥) ≔ ∏ • 数列 (𝐴0 , 𝐴1 , …, 𝐴𝐷−1 ) 𝑗=0 (𝑥 − 𝐵𝑗 ) が与えられる．𝐹(𝐴𝑖 ) mod 𝑁 たちを 𝑜(𝐷2 ) 時間で列挙せよ
多点評価とは 14 / 22 𝑁−1 • 𝑁 次未満の多項式 𝐹(𝑥) = ∑ • 数列 (𝐴0 , 𝐴1 , …, 𝐴𝑀−1 ) • 正整数 𝑃 ‣ 素数だったり任意だったり 𝑗=0 𝐹𝑗 𝑥 𝑗 が与えられる．𝐹(𝐴𝑖 ) mod 𝑃 たちを列挙せよ
多点評価とは 14 / 22 𝑁−1 • 𝑁 次未満の多項式 𝐹(𝑥) = ∑ • 数列 (𝐴0 , 𝐴1 , …, 𝐴𝑀−1 ) • 正整数 𝑃 ‣ 素数だったり任意だったり 𝑗=0 𝐹𝑗 𝑥 𝑗 が与えられる．𝐹(𝐴𝑖 ) mod 𝑃 たちを列挙せよ • 愚直には Θ(𝑁𝑀) 時間 • 賢くやると Θ(𝑁 log 𝑁 + 𝑀(log 𝑀)2 ) 時間 ‣ 概要： 1. 多項式剰余算に Θ(𝑁 log 𝑁) 時間 2. 完全二分木の要領で畳み込みに Θ(𝑀 log 𝑀) 時間/段 × ⌈log2 𝑀⌉ 段
高速化する 15 / 22 再掲 𝐷−1 • 𝐷 次多項式 𝐹(𝑥) ≔ ∏ • 数列 (𝐴0 , 𝐴1 , …, 𝐴𝐷−1 ) 𝑗=0 (𝑥 − 𝐵𝑗 ) が与えられる．𝐹(𝐴𝑖 ) mod 𝑁 たちを 𝑜(𝐷2 ) 時間で列挙せよ
高速化する 15 / 22 再掲 𝐷−1 • 𝐷 次多項式 𝐹(𝑥) ≔ ∏ • 数列 (𝐴0 , 𝐴1 , …, 𝐴𝐷−1 ) 𝑗=0 (𝑥 − 𝐵𝑗 ) が与えられる．𝐹(𝐴𝑖 ) mod 𝑁 たちを 𝑜(𝐷2 ) 時間で列挙せよ これは任意 mod の多点評価 Θ(𝐷(log 𝐷)2 ) ⊂ 𝑜(𝐷2 ) 時間でできる
実測 16 / 22 Rust で実装しました1 𝐷−1 • 𝐷 次多項式 𝐹(𝑥) ≔ ∏ • 数列 (𝐴0 , 𝐴1 , …, 𝐴𝐷−1 ) 𝑗=0 (𝑥 − 𝐵𝑗 ) が与えられる．𝐹(𝐴𝑖 ) mod 𝑁 たちを列挙せよ ↑これを解く部分を測定 1https://github.com/wasd314/integer-factorization/blob/6811e95220c50e1b49ce752fdfc2 a429596fad74/rust/factor/src/multipoint_evaluation/u128.rs
結果 17 / 22 𝐷 ≳ 4000 なら愚直より高速になった！1 1https://github.com/wasd314/integer-factorization/blob/6811e95220c50e1b49ce752fdfc2 a429596fad74/rust/factor/benches/diff_product.rs
パラメータ 𝐵1 , 𝐵2 の決め方 18 / 22 GMP-ECM1 によれば 𝑝 の桁数 最適 𝐵1 既定 𝐵2 𝐷 = ⌈√𝐵2 ⌉ 20 1.1 × 104 1.9 × 106 1.4 × 103 25 5.0 × 104 1.3 × 107 3.6 × 103 30 2.5 × 105 1.3 × 108 1.1 × 104 35 1.0 × 106 1.0 × 109 3.2 × 104 40 3.0 × 106 5.7 × 109 7.5 × 104 ⋮ ⋮ ⋮ ⋮ 𝑁 ≤ 1038 では 𝑝 ≤ 1019 なので 𝐷 ≲ 1400 1https://gitlab.inria.fr/zimmerma/ecm/-/blob/6226d2d752f07ca183e88bcc1fd5478dfee1 ccd6/README, Table 1
𝐷 ≲ 1400 …? 19 / 22
𝐷 ≲ 1400 …? 19 / 22 愚直に敗北！
まとめ • ECM という素因数分解アルゴリズムがある ‣ 試し割り法，Pollard’s 𝜌 よりもさらに高速 • ECM の Stage 2 に多点評価が現れる ‣ 「多点評価は素因数分解の役に立つ」 • 多点評価パートの高速化を実装したが，愚直に負けた ‣ 128 bit 任意 mod 多点評価なので定数倍がひどく悪い ‣ 𝑁 が 256 bit なら勝てるかも？ 20 / 22
まとめ • ECM という素因数分解アルゴリズムがある ‣ 試し割り法，Pollard’s 𝜌 よりもさらに高速 • ECM の Stage 2 に多点評価が現れる ‣ 「多点評価は素因数分解の役に立つ」 • 多点評価パートの高速化を実装したが，愚直に負けた ‣ 128 bit 任意 mod 多点評価なので定数倍がひどく悪い ‣ 𝑁 が 256 bit なら勝てるかも？ 20 / 22
宣伝 21 / 22 • 本スライドは Typst 0.14.2, Touying 0.7.3 などを用いて作成さ れました 皆さんもぜひ ‣ Typst: Rust-based 爆速組版ソフト ‣ Touying: Typst のスライド作成 package • 弊コンテストよろしくお願いします ‣ https://yukicoder.me/contests/575 ‣ 自作問題の Solved が増えると，うれしい！
宣伝 21 / 22 • 本スライドは Typst 0.14.2, Touying 0.7.3 などを用いて作成さ れました 皆さんもぜひ ‣ Typst: Rust-based 爆速組版ソフト ‣ Touying: Typst のスライド作成 package • 弊コンテストよろしくお願いします ‣ https://yukicoder.me/contests/575 ‣ 自作問題の Solved が増えると，うれしい！ ご清聴ありがとうございました！
参考文献・リンク 22 / 22 • R. Crandall，C. Pomerance 著，和田秀男 監訳．素数全書 — 計算からのアプローチ—．朝倉書店，2010． ‣ 7 章「楕円曲線を使った方法」を参照しました • P. Zimmermann．20 years of ECM．https://members.loria. fr/PZimmermann/papers/ecm.pdf． • keymoon．高速な楕円曲線法① 理論と手法編．https:// keymoon.hatenablog.com/entry/2024/12/05/032548． （2026-06-04 閲覧）． 今回の実装: https://github.com/wasd314/integerfactorization/tree/6811e95220c50e1b49ce752fdfc2a429596fad 74/rust/factor
Appendix
ECM の実装 23 / 22 楕円曲線の表示形式 (𝑥, 𝑦) s.t. 𝑦 2 = 𝑥 3 + 𝐶𝑥 2 + 𝑥 の代わりに 𝑥 = 𝑋/𝑍, 𝑦 = 𝑌/𝑍 として (𝑋, 𝑌, 𝑍) s.t. 𝑌 2 𝑍 = 𝑋 3 + 𝐶𝑋 2 𝑍 + 𝑋𝑍 2 の斉次形を使うと 𝑌 を忘れて (𝑋, 𝑍) だけ管理すれば良い • 和の点の 𝑥 座標が足す前の 𝑥 座標だけから求まるので • 𝑃 = 𝑂 mod 𝑝 は gcd(𝑍, 𝑁) > 1 で判定 • 逆元計算を遅延させられる Suyama’s parametrization 乱択した 𝑠 ≠ 0, 1, 5 から楕円曲線群 𝐸 と 𝑃 ∈ 𝐸 を得る • 12 | #𝐸 が保証され #𝐸 が 𝐵1 -smooth になりやすい
Hasse の定理 24 / 22 mod 𝑝 の楕円曲線群 𝐸 について |#𝐸 − (𝑝 + 1)| ≤ 2√𝑝 よりラフには #𝐸 ∼ 𝑝
𝐵-smooth, 𝐵-powersmooth 𝑒𝑖 𝑛 ≕ ∏𝑖 𝑝𝑖 と素因数分解したとき • 𝑛 が 𝐵-smooth :⟺ ∀𝑖. 𝑝𝑖 ≤ 𝐵 𝑒𝑖 • 𝑛 が 𝐵-powersmooth :⟺ ∀𝑖. 𝑝𝑖 ≤ 𝐵 ‣ 𝐵-powersmooth ⟹ 𝐵-smooth 例: 𝑛 = 25 32 131 は 13-smooth である • 2, 3, 13 ≤ 13 より 13-powersmooth ではない • 25 ≰ 13 より 32-smooth である • 2, 3, 13 ≤ 32 より 32-powersmooth である • 25 , 32 , 131 ≤ 32 より 25 / 22
ECM の計算量 26 / 22 （Stage 2 を無視すると） (𝐸, 𝑃 ∈ 𝐸) から 𝑝 が取り出せるには #𝐸 (∼ 𝑝) が 𝐵1 -smooth なることが必要で，その確率は prob(𝐵1 ) ≈ 1 #{𝑥 ≤ 𝑝 | 𝑥 は 𝐵1 -smooth} 𝑝 ≈ 𝑢−𝑢 𝑝 までの割合で近似 (𝑢 ≔ ln(𝑝)/ ln(𝐵1 )). 1 回の試行に Θ(𝐵1 ) 時間かかるので，𝐵1 / prob(𝐵1 ) ≈ 𝐵1 𝑢𝑢 を 最小化すると √2 𝐵1 = exp[( + 𝑜(1))√ln(𝑝) ln(ln(𝑝))] のとき 2 𝐵1 𝑢𝑢 = exp[(√2 + 𝑜(1))√ln(𝑝) ln(ln(𝑝))]
他の素因数分解アルゴリズム：二次篩法 𝑥 ≢𝑦 {𝑥 ≢ −𝑦 𝑥2 ≡ 𝑦2 𝑁 ∤ (𝑥 + 𝑦) (mod 𝑁) ⟹ {𝑁 ∤ (𝑥 − 𝑦) 𝑁 ∣ (𝑥 + 𝑦)(𝑥 − 𝑦) なのでこのとき gcd(𝑥 ± 𝑦, 𝑁) が非自明になる • 𝑁 の素因数が 𝑥 + 𝑦 と 𝑥 − 𝑦 に一部ずつ含まれている 1. 𝑥𝑖2 ≡ 𝑎𝑖 ，𝑎𝑖 : smooth なる関係式をたくさん求める 2. ∏𝑖 𝑎𝑖 が平方数 𝐴2 になるように選ぶ • 𝑎𝑖 を素因数分解した指数ベクトルの和を全成分偶数に →線形代数 2 3. (∏𝑖 𝑥𝑖 ) ≡ 𝐴2 とわかる 4. gcd((∏𝑖 𝑥𝑖 ) ± 𝐴, 𝑁) を求める 27 / 22
素因数分解最速界隈のみなさんの計算量 🥉 ECM 🥈 QS 🥇 GNFS 1 𝐿𝑝 [ , √2] 2 1 𝐿𝑝 [ , 1] 2 1 3 64 𝐿𝑝 [ , 𝑐] (𝑐 = √ ≈ 1.923) 3 9 ただし 𝐿𝑛 [𝛼, 𝑐] は 𝐿-notation: 𝐿𝑛 [𝛼, 𝑐] ≔ exp[(𝑐 + 𝑜(1)) ⋅ ln(𝑛)𝛼 ⋅ ln(ln(𝑛))1−𝛼 ] 𝛼 1−𝛼 𝑐+𝑜(1) = exp[ln(𝑛) ⋅ ln(ln(𝑛)) ] 𝐿𝑛 [0, 𝑐] = exp[(𝑐 + 𝑜(1)) ⋅ ln(ln(𝑛))] = ln(𝑛)𝑐+𝑜(1) 𝐿𝑛 [1, 𝑐] = exp[(𝑐 + 𝑜(1)) ⋅ ln(𝑛)] = 𝑛𝑐+𝑜(1) 28 / 22
実測結果 29 / 22 (𝐵𝑗 ) から ∏𝑗 (𝑥 − 𝐵𝑗 ) の係数列を得るのにも Θ(𝐷(log 𝐷)2 ) 時間 𝑗