---
title: 多点評価は素因数分解の役に立つ
tags:  #競技プログラミング #アルゴリズム #素因数分解 #ecm #楕円曲線法 #多点評価 #multipoint evaluation #rust  
author: [wasd314](https://image.docswell.com/user/wasd314)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/4JQYZ8QR7P.jpg?width=480
description: 2026-06-06 に開かれた「競プロキャンプ 2026 関東」( https://connpass.com/event/382761 ) 内の LT 会への登壇資料．  素因数分解アルゴリズムの1つである楕円曲線法（Elliptic-Curve factorization Method; ECM）の Stage 2 に多点評価が現れることを示す．また多点評価（Multipoint Evaluation）の Rust による実装を2種類紹介し，実行時間を比較する．
published: June 07, 26
canonical: https://image.docswell.com/s/wasd314/KX261Y-2026-06-07-021729
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/4JQYZ8QR7P.jpg)

多点評価は素因数分解の役に立つ
wasd314
2026-06-06
競プロキャンプ 2026 関東 – LT 会


# Page. 2

![Page Image](https://bcdn.docswell.com/page/K74W32NQE1.jpg)

自己紹介
• 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


# Page. 3

![Page Image](https://bcdn.docswell.com/page/LJ1Y1M5LEG.jpg)

自己紹介
• 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


# Page. 4

![Page Image](https://bcdn.docswell.com/page/GJWG835Q72.jpg)

初作問 @ yukicoder
wasd314 さんの単発問題コンテスト (2025-11-02, 2 h)
https://yukicoder.me/contests/575
2 / 22


# Page. 5

![Page Image](https://bcdn.docswell.com/page/4EZL8VN373.jpg)

初作問 @ yukicoder
B 問題: No. 3332 Consecutive Power Sum (Small)1
• ネタバレ：𝑁 の素因数分解が要る
• 𝑁 ≤ 1012
1https://yukicoder.me/problems/no/3332
3 / 22


# Page. 6

![Page Image](https://bcdn.docswell.com/page/Y76WP58Z7V.jpg)

初作問 @ 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


# Page. 7

![Page Image](https://bcdn.docswell.com/page/G75MKY9974.jpg)

初作問 @ 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


# Page. 8

![Page Image](https://bcdn.docswell.com/page/9J29WG25ER.jpg)

Library Checker にも
Factorize1
• 𝑁 ≤ 1018
• 10 s で 100 回
1https://judge.yosupo.jp/problem/factorize
4 / 22


# Page. 9

![Page Image](https://bcdn.docswell.com/page/DEY4LVY6JM.jpg)

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


# Page. 10

![Page Image](https://bcdn.docswell.com/page/VJNY4MR178.jpg)

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


# Page. 11

![Page Image](https://bcdn.docswell.com/page/YE9PQNMYJ3.jpg)

今，素因数分解がアツい！


# Page. 12

![Page Image](https://bcdn.docswell.com/page/GE8DGKLKED.jpg)

素因数分解のアルゴリズム
5 / 22


# Page. 13

![Page Image](https://bcdn.docswell.com/page/LELMGZLP7R.jpg)

素因数分解のアルゴリズム
試し割り法
worst Θ(𝑁1/2 ) 時間
5 / 22


# Page. 14

![Page Image](https://bcdn.docswell.com/page/4JMYQVM2JW.jpg)

素因数分解のアルゴリズム
試し割り法
worst Θ(𝑁1/2 ) 時間
• AtCoder ABC-D が解ける1
• Consecutive Power Sum (Small) (𝑁 ≤ 1012 ) が解ける
1例: AtCoder – ABC169D (𝑁 ≤ 1012 )
5 / 22


# Page. 15

![Page Image](https://bcdn.docswell.com/page/PJR982V579.jpg)

素因数分解のアルゴリズム
Pollard’s 𝝆
expected 𝑂(𝑝1/2 ) ⊆ 𝑂(𝑁1/4 ) 時間
6 / 22


# Page. 16

![Page Image](https://bcdn.docswell.com/page/PEXQ8DZXJX.jpg)

素因数分解のアルゴリズム
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


# Page. 17

![Page Image](https://bcdn.docswell.com/page/3EK9KX89ED.jpg)

素因数分解のアルゴリズム
では Factorial (Large) (𝑁 ≤ 1038 ) の想定解は？
7 / 22


# Page. 18

![Page Image](https://bcdn.docswell.com/page/L73WZ52975.jpg)

素因数分解のアルゴリズム
では Factorial (Large) (𝑁 ≤ 1038 ) の想定解は？
👉️ 楕円曲線法
(Elliptic-Curve factorization Method; ECM)
7 / 22


# Page. 19

![Page Image](https://bcdn.docswell.com/page/87DKRDZ8JG.jpg)

素因数分解のアルゴリズム
では Factorial (Large) (𝑁 ≤ 1038 ) の想定解は？
👉️ 楕円曲線法
(Elliptic-Curve factorization Method; ECM)
楕円曲線群を使って 𝑁 の素因数 𝑝 を
expected exp[(√2 + 𝑜(1))√ln(𝑝) ln(ln(𝑝))] 時間
で見つける
7 / 22


# Page. 20

![Page Image](https://bcdn.docswell.com/page/VJPKWXDWE8.jpg)

楕円曲線群とは
{(𝑥, 𝑦) ∈ 𝔽𝑝 × 𝔽𝑝 | 𝑦 2 = 𝑥 3 + 𝐶𝑥 2 + 𝑥}
と無限遠点 𝑂 を合わせた集合 𝐸
8 / 22


# Page. 21

![Page Image](https://bcdn.docswell.com/page/2EVV8L19EQ.jpg)

楕円曲線群とは
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 ,
{
⊖ (𝑥, 𝑦) ≔ (𝑥, −𝑦).
(𝐸, ⊕, 𝑂, ⊖) は有限可換群をなし，これを楕円曲線群と呼ぶ


# Page. 22

![Page Image](https://bcdn.docswell.com/page/57GL5X24EL.jpg)

楕円曲線群とは
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 ,
{
⊖ (𝑥, 𝑦) ≔ (𝑥, −𝑦).
(𝐸, ⊕, 𝑂, ⊖) は有限可換群をなし，これを楕円曲線群と呼ぶ
点の整数倍 ⏟
𝑃 + 𝑃 + ⋯ + 𝑃 を [𝑛]𝑃 と書く
𝑛個


# Page. 23

![Page Image](https://bcdn.docswell.com/page/4EQYZ8PRJP.jpg)

ECM の戦略
点 𝑃 ∈ 𝐸 の整数倍を mod 𝑝 の代わりに mod 𝑁 で計算する
9 / 22


# Page. 24

![Page Image](https://bcdn.docswell.com/page/KJ4W32YQ71.jpg)

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 が可逆でないと失敗する
⋯⋯ これは和が 𝑂 になる場合に対応する


# Page. 25

![Page Image](https://bcdn.docswell.com/page/LE1Y1M6L7G.jpg)

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 , 𝑁) として 𝑝 が取り出せる


# Page. 26

![Page Image](https://bcdn.docswell.com/page/GEWG83WQJ2.jpg)

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 𝑝 で 𝑶 になるのを待つ


# Page. 27

![Page Image](https://bcdn.docswell.com/page/47ZL8V53J3.jpg)

ECM
1. パラメータ 𝐵1 , 𝐵2 を決める
2. 楕円曲線群とその元 𝑃 を乱択する
3. (Stage 1) 𝑃 を 𝐿 倍した点 𝑄 ≔ [𝐿]𝑃 を求める
• 𝐿 ≔ lcm(1, 2, …, 𝐵1 )
• 𝑄 = 𝑂 になったら成功
4. (Stage 2) [𝑘]𝑄 (1 ≤ 𝑘 ≤ 𝐵2 ) を求める
• どれかが 𝑂 なら成功
5. 失敗したら 2. に戻る
10 / 22


# Page. 28

![Page Image](https://bcdn.docswell.com/page/YJ6WP59ZJV.jpg)

ECM – Stage 2
4. (Stage 2) [𝑘]𝑄 (1 ≤ 𝑘 ≤ 𝐵2 ) を求める
• どれかが 𝑂 なら成功
[1]𝑄, [2]𝑄, [3]𝑄, …, [𝐵2 ]𝑄 を愚直に列挙 & 𝑂 と比較
⋯⋯ Ω(𝐵2 ) 時間かかる
11 / 22


# Page. 29

![Page Image](https://bcdn.docswell.com/page/GJ5MKYN9J4.jpg)

ECM – Stage 2
4. (Stage 2) [𝑘]𝑄 (1 ≤ 𝑘 ≤ 𝐵2 ) を求める
• どれかが 𝑂 なら成功
[1]𝑄, [2]𝑄, [3]𝑄, …, [𝐵2 ]𝑄 を愚直に列挙 & 𝑂 と比較
⋯⋯ Ω(𝐵2 ) 時間かかる
𝑜(𝐵2 ) 時間にしたい
11 / 22


# Page. 30

![Page Image](https://bcdn.docswell.com/page/LE3WZ522E5.jpg)

平方分割
12 / 22
𝐷 ≔ ⌈√𝐵2 ⌉ として 𝑘 ≕ 𝑖𝐷 + 𝑗 (𝑖, 𝑗 ∈ [0, 𝐷)) と表示すると
⟺
[𝑘]𝑄 ≡ 𝑂
(mod 𝑝)
[𝑖𝐷]𝑄 + [𝑗]𝑄 ≡ 𝑂
(mod 𝑝)
⟺
[𝑖𝐷]𝑄 ≡ [−𝑗]𝑄
(mod 𝑝)
変数分離
⟹
𝑥([𝑖𝐷]𝑄) ≡ 𝑥([−𝑗]𝑄)
(mod 𝑝)
𝑥 座標だけ見る
⟺
𝐴𝑖 ≡ 𝐵𝑗
(mod 𝑝)


# Page. 31

![Page Image](https://bcdn.docswell.com/page/8EDKRDZ67G.jpg)

平方分割
12 / 22
𝐷 ≔ ⌈√𝐵2 ⌉ として 𝑘 ≕ 𝑖𝐷 + 𝑗 (𝑖, 𝑗 ∈ [0, 𝐷)) と表示すると
⟺
[𝑘]𝑄 ≡ 𝑂
(mod 𝑝)
[𝑖𝐷]𝑄 + [𝑗]𝑄 ≡ 𝑂
(mod 𝑝)
⟺
[𝑖𝐷]𝑄 ≡ [−𝑗]𝑄
(mod 𝑝)
変数分離
⟹
𝑥([𝑖𝐷]𝑄) ≡ 𝑥([−𝑗]𝑄)
(mod 𝑝)
𝑥 座標だけ見る
⟺
𝐴𝑖 ≡ 𝐵𝑗
(mod 𝑝)
⟺
𝑝 ∣ 𝐴𝑖 − 𝐵𝑗
⟺
𝑝 ∣ gcd(𝐴𝑖 − 𝐵𝑗 , 𝑁)
ただし 𝐴𝑖 ≔ 𝑥([𝑖𝐷]𝑄) mod 𝑁, 𝐵𝑗 ≔ 𝑥([−𝑗]𝑄) mod 𝑁


# Page. 32

![Page Image](https://bcdn.docswell.com/page/V7PKWXYZJ8.jpg)

平方分割
12 / 22
𝐷 ≔ ⌈√𝐵2 ⌉ として 𝑘 ≕ 𝑖𝐷 + 𝑗 (𝑖, 𝑗 ∈ [0, 𝐷)) と表示すると
⟺
[𝑘]𝑄 ≡ 𝑂
(mod 𝑝)
[𝑖𝐷]𝑄 + [𝑗]𝑄 ≡ 𝑂
(mod 𝑝)
⟺
[𝑖𝐷]𝑄 ≡ [−𝑗]𝑄
(mod 𝑝)
変数分離
⟹
𝑥([𝑖𝐷]𝑄) ≡ 𝑥([−𝑗]𝑄)
(mod 𝑝)
𝑥 座標だけ見る
⟺
𝐴𝑖 ≡ 𝐵𝑗
(mod 𝑝)
⟺
𝑝 ∣ 𝐴𝑖 − 𝐵𝑗
⟺
𝑝 ∣ gcd(𝐴𝑖 − 𝐵𝑗 , 𝑁)
ただし 𝐴𝑖 ≔ 𝑥([𝑖𝐷]𝑄) mod 𝑁, 𝐵𝑗 ≔ 𝑥([−𝑗]𝑄) mod 𝑁
gcd(𝐴𝑖 − 𝐵𝑗 , 𝑁) たちを列挙すると依然 Ω(𝐷2 ) = Ω(𝐵2 ) 時間


# Page. 33

![Page Image](https://bcdn.docswell.com/page/2JVV8LGMJQ.jpg)

問題の変形
gcd(𝐴𝑖 − 𝐵𝑗 , 𝑁) たちを列挙すると依然 Ω(𝐷2 ) = Ω(𝐵2 ) 時間
𝐴𝑖 − 𝐵𝑗 たちのどれかが 𝑝 の倍数と分かれば良い
13 / 22


# Page. 34

![Page Image](https://bcdn.docswell.com/page/5EGL5X8XJL.jpg)

問題の変形
13 / 22
gcd(𝐴𝑖 − 𝐵𝑗 , 𝑁) たちを列挙すると依然 Ω(𝐷2 ) = Ω(𝐵2 ) 時間
𝐴𝑖 − 𝐵𝑗 たちのどれかが 𝑝 の倍数と分かれば良い
各 𝑖 について gcd(∏
𝐷−1
𝑗=0
(𝐴𝑖 − 𝐵𝑗 ), 𝑁) が求まれば良い


# Page. 35

![Page Image](https://bcdn.docswell.com/page/4JQYZ8957P.jpg)

問題の変形
13 / 22
gcd(𝐴𝑖 − 𝐵𝑗 , 𝑁) たちを列挙すると依然 Ω(𝐷2 ) = Ω(𝐵2 ) 時間
𝐴𝑖 − 𝐵𝑗 たちのどれかが 𝑝 の倍数と分かれば良い
𝐷−1
各 𝑖 について gcd(∏
𝑗=0
各 𝑖 について ∏
𝐷−1
𝑗=0
(𝐴𝑖 − 𝐵𝑗 ), 𝑁) が求まれば良い
(𝐴𝑖 − 𝐵𝑗 ) mod 𝑁 が求まれば良い


# Page. 36

![Page Image](https://bcdn.docswell.com/page/K74W32XVE1.jpg)

問題の変形
13 / 22
gcd(𝐴𝑖 − 𝐵𝑗 , 𝑁) たちを列挙すると依然 Ω(𝐷2 ) = Ω(𝐵2 ) 時間
𝐴𝑖 − 𝐵𝑗 たちのどれかが 𝑝 の倍数と分かれば良い
𝐷−1
各 𝑖 について gcd(∏
𝑗=0
𝐷−1
各 𝑖 について ∏
𝑗=0
(𝐴𝑖 − 𝐵𝑗 ), 𝑁) が求まれば良い
(𝐴𝑖 − 𝐵𝑗 ) mod 𝑁 が求まれば良い
𝐷−1
• 𝐷 次多項式 𝐹(𝑥) ≔ ∏
• 数列 (𝐴0 , 𝐴1 , …, 𝐴𝐷−1 )
𝑗=0
(𝑥 − 𝐵𝑗 )
が与えられる．𝐹(𝐴𝑖 ) mod 𝑁 たちを 𝑜(𝐷2 ) 時間で列挙せよ


# Page. 37

![Page Image](https://bcdn.docswell.com/page/LJ1Y1MN4EG.jpg)

多点評価とは
14 / 22
𝑁−1
• 𝑁 次未満の多項式 𝐹(𝑥) = ∑
• 数列 (𝐴0 , 𝐴1 , …, 𝐴𝑀−1 )
• 正整数 𝑃
‣ 素数だったり任意だったり
𝑗=0
𝐹𝑗 𝑥 𝑗
が与えられる．𝐹(𝐴𝑖 ) mod 𝑃 たちを列挙せよ


# Page. 38

![Page Image](https://bcdn.docswell.com/page/GJWG834Z72.jpg)

多点評価とは
14 / 22
𝑁−1
• 𝑁 次未満の多項式 𝐹(𝑥) = ∑
• 数列 (𝐴0 , 𝐴1 , …, 𝐴𝑀−1 )
• 正整数 𝑃
‣ 素数だったり任意だったり
𝑗=0
𝐹𝑗 𝑥 𝑗
が与えられる．𝐹(𝐴𝑖 ) mod 𝑃 たちを列挙せよ
• 愚直には Θ(𝑁𝑀) 時間
• 賢くやると Θ(𝑁 log 𝑁 + 𝑀(log 𝑀)2 ) 時間
‣ 概要：
1. 多項式剰余算に Θ(𝑁 log 𝑁) 時間
2. 完全二分木の要領で畳み込みに Θ(𝑀 log 𝑀) 時間/段 × ⌈log2 𝑀⌉ 段


# Page. 39

![Page Image](https://bcdn.docswell.com/page/4EZL8V2L73.jpg)

高速化する
15 / 22
再掲
𝐷−1
• 𝐷 次多項式 𝐹(𝑥) ≔ ∏
• 数列 (𝐴0 , 𝐴1 , …, 𝐴𝐷−1 )
𝑗=0
(𝑥 − 𝐵𝑗 )
が与えられる．𝐹(𝐴𝑖 ) mod 𝑁 たちを 𝑜(𝐷2 ) 時間で列挙せよ


# Page. 40

![Page Image](https://bcdn.docswell.com/page/Y76WP5VM7V.jpg)

高速化する
15 / 22
再掲
𝐷−1
• 𝐷 次多項式 𝐹(𝑥) ≔ ∏
• 数列 (𝐴0 , 𝐴1 , …, 𝐴𝐷−1 )
𝑗=0
(𝑥 − 𝐵𝑗 )
が与えられる．𝐹(𝐴𝑖 ) mod 𝑁 たちを 𝑜(𝐷2 ) 時間で列挙せよ
これは任意 mod の多点評価
Θ(𝐷(log 𝐷)2 ) ⊂ 𝑜(𝐷2 ) 時間でできる


# Page. 41

![Page Image](https://bcdn.docswell.com/page/G75MKYDQ74.jpg)

実測
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


# Page. 42

![Page Image](https://bcdn.docswell.com/page/9J29WG8WER.jpg)

結果
17 / 22
𝐷 ≳ 4000 なら愚直より高速になった！1
1https://github.com/wasd314/integer-factorization/blob/6811e95220c50e1b49ce752fdfc2
a429596fad74/rust/factor/benches/diff_product.rs


# Page. 43

![Page Image](https://bcdn.docswell.com/page/DEY4LV69JM.jpg)

パラメータ 𝐵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


# Page. 44

![Page Image](https://bcdn.docswell.com/page/VJNY4MZD78.jpg)

𝐷 ≲ 1400 …?
19 / 22


# Page. 45

![Page Image](https://bcdn.docswell.com/page/YE9PQNZ8J3.jpg)

𝐷 ≲ 1400 …?
19 / 22
愚直に敗北！


# Page. 46

![Page Image](https://bcdn.docswell.com/page/GE8DGK1ZED.jpg)

まとめ
• ECM という素因数分解アルゴリズムがある
‣ 試し割り法，Pollard’s 𝜌 よりもさらに高速
• ECM の Stage 2 に多点評価が現れる
‣ 「多点評価は素因数分解の役に立つ」
• 多点評価パートの高速化を実装したが，愚直に負けた
‣ 128 bit 任意 mod 多点評価なので定数倍がひどく悪い
‣ 𝑁 が 256 bit なら勝てるかも？
20 / 22


# Page. 47

![Page Image](https://bcdn.docswell.com/page/LELMGZQ17R.jpg)

まとめ
• ECM という素因数分解アルゴリズムがある
‣ 試し割り法，Pollard’s 𝜌 よりもさらに高速
• ECM の Stage 2 に多点評価が現れる
‣ 「多点評価は素因数分解の役に立つ」
• 多点評価パートの高速化を実装したが，愚直に負けた
‣ 128 bit 任意 mod 多点評価なので定数倍がひどく悪い
‣ 𝑁 が 256 bit なら勝てるかも？
20 / 22


# Page. 48

![Page Image](https://bcdn.docswell.com/page/4JMYQV15JW.jpg)

宣伝
21 / 22
• 本スライドは Typst 0.14.2, Touying 0.7.3 などを用いて作成さ
れました 皆さんもぜひ
‣ Typst: Rust-based 爆速組版ソフト
‣ Touying: Typst のスライド作成 package
• 弊コンテストよろしくお願いします
‣ https://yukicoder.me/contests/575
‣ 自作問題の Solved が増えると，うれしい！


# Page. 49

![Page Image](https://bcdn.docswell.com/page/PJR982LZ79.jpg)

宣伝
21 / 22
• 本スライドは Typst 0.14.2, Touying 0.7.3 などを用いて作成さ
れました 皆さんもぜひ
‣ Typst: Rust-based 爆速組版ソフト
‣ Touying: Typst のスライド作成 package
• 弊コンテストよろしくお願いします
‣ https://yukicoder.me/contests/575
‣ 自作問題の Solved が増えると，うれしい！
ご清聴ありがとうございました！


# Page. 50

![Page Image](https://bcdn.docswell.com/page/PEXQ8DW1JX.jpg)

参考文献・リンク
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


# Page. 51

![Page Image](https://bcdn.docswell.com/page/3EK9KXVMED.jpg)

Appendix


# Page. 52

![Page Image](https://bcdn.docswell.com/page/L73WZ5M275.jpg)

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 になりやすい


# Page. 53

![Page Image](https://bcdn.docswell.com/page/87DKRD66JG.jpg)

Hasse の定理
24 / 22
mod 𝑝 の楕円曲線群 𝐸 について
|#𝐸 − (𝑝 + 1)| ≤ 2√𝑝
よりラフには
#𝐸 ∼ 𝑝


# Page. 54

![Page Image](https://bcdn.docswell.com/page/VJPKW6ZZE8.jpg)

𝐵-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


# Page. 55

![Page Image](https://bcdn.docswell.com/page/2EVV83WMEQ.jpg)

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(𝑝))]


# Page. 56

![Page Image](https://bcdn.docswell.com/page/57GL53DXEL.jpg)

他の素因数分解アルゴリズム：二次篩法
𝑥 ≢𝑦
{𝑥 ≢ −𝑦
𝑥2 ≡ 𝑦2
𝑁 ∤ (𝑥 + 𝑦)
(mod 𝑁) ⟹ {𝑁 ∤ (𝑥 − 𝑦)
𝑁 ∣ (𝑥 + 𝑦)(𝑥 − 𝑦)
なのでこのとき gcd(𝑥 ± 𝑦, 𝑁) が非自明になる
• 𝑁 の素因数が 𝑥 + 𝑦 と 𝑥 − 𝑦 に一部ずつ含まれている
1. 𝑥𝑖2 ≡ 𝑎𝑖 ，𝑎𝑖 : smooth なる関係式をたくさん求める
2. ∏𝑖 𝑎𝑖 が平方数 𝐴2 になるように選ぶ
• 𝑎𝑖 を素因数分解した指数ベクトルの和を全成分偶数に →線形代数
2
3. (∏𝑖 𝑥𝑖 ) ≡ 𝐴2 とわかる
4. gcd((∏𝑖 𝑥𝑖 ) ± 𝐴, 𝑁) を求める
27 / 22


# Page. 57

![Page Image](https://bcdn.docswell.com/page/4EQYZ515JP.jpg)

素因数分解最速界隈のみなさんの計算量
🥉 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


# Page. 58

![Page Image](https://bcdn.docswell.com/page/KJ4W39RV71.jpg)

実測結果
29 / 22
(𝐵𝑗 ) から ∏𝑗 (𝑥 − 𝐵𝑗 ) の係数列を得るのにも Θ(𝐷(log 𝐷)2 ) 時間
𝑗