公立はこだて未来大学 2017 年度 システム情報科学実習
グループ報告書
Future University Hakodate 2017 System Information Science PracticeGroup Report

プロジェクト名
FUN-ECM プロジェクト

Project NameFUN-ECM Project

グループ名
A グループGroup Name
A Group
プロジェクト番号/Project No.

11-A

プロジェクトリーダ/Project Leader
1015014

中島俊平

Shunpei Nakajima

グループリーダ/Group Leader
1015014

中島俊平

Shunpei Nakajima

グループメンバ/Group Member
1015014中島俊平

1015082

福永慧

1015112

小澤貴也

Takaya Ozawa

1015182

落合航平

Kouhei Ochiai

1015202

金子真澄

Masumi Kaneko

1015237

水上敬介

Keisuke Mizukami

1015260

外山拓Shunpei Nakajima
Kei Fukunaga

Taku Toyama

指導教員
白勢政明 由良文孝

AdvisorMasaaki Shirase

Fumitaka Yura

提出日2018 年 1 月 19 日

Date of Submission
January 19, 2018

概要
私達のプロジェクトの目的は，より大きな桁数の素因数を見つけることである．素因数分解が重要であることの背景として，RSA 暗号がある．RSA 暗号は，40 年前に考案された初めての公開鍵暗号で，現在でもデジタル署名などで利用されている．RSA 暗号は，「大きい桁数の2 つの素数からなる合成数を素因数分解することが難しい」ということで安全が保証されているが，近年，より高い安全性を持つ楕円曲線暗号が利用されてきている．そこで FUN-ECM
プロジェクトでは，楕円曲線法（ECM）を用いて，より大きい桁数の素因数分解を行うプログ
ラムを作成し，RSA 暗号の安全性について検証を行う．更に私たちは，大きい数の素因数分解
をランキングしたサイトである，ECMNET[2] や STUDIO KAMADA[3] へのランクインを目標として掲げ活動を行った．
まず私達は，理論班とプログラム班に分かれ活動を行っている．理論班の目的は，ECM の高速化のための論文を理解し，プログラム班に引き継ぐことである．プログラム班の目的は，理論班が準備したアルゴリズムを実装し，高速化できているか確かめることである．
理論班は，ECM の Stage2 をより高速に行えるアルゴリズムの発見・理解を目標とした．前期は昨年度のプログラムに使われていた理論の理解，Baby-step Giant-step の理解，

PARI/GP での実装を行った．後期は Montgomery 曲線の理解，素数ペアリングの理解，Pollard’s ρ 法の理解，FFT の実装の検討を行った．
プログラム班は，前年度に作成された素因数分解プログラムをさらに高速化することを目標とした．前期は昨年度のプログラムで余分に座標変換を行っていた部分のコードの修正，並列処理の強制終了の機能の追加，Baby-step Giant-step の実装，Stage2 の実行速度のテストを行った．後期は，Montgomery 曲線を使用した ECM プログラムの作成した．また，素数テーブルの実装や Xeon に置ける階層化，シェルスクリプトなどを行った．また，ソースファイルの説明書の作成を作成した．
以上の２つの班が互いに足りない部分を補完しあい活動を行った．その結果，約 80 倍のStage2 の高速化に成功し，素因数分解を高速に行えるプログラムが完成した．
キーワード

素因数分解，楕円曲線法，ECMNET，STUDIO KAMADA，エドワーズ曲線，拡張射影座標，RSA 暗号，Baby-step Giant-step，Pollard’s ρ 法，FFT（※文責: 中島俊平）-i-Abstract
The goal of our project team is to find prime factor as large as possible. Factorizationsin prime numbers have become more important because of RSA cryptosystem. RSA
cryptosystem which was invented 40 years ago is still being used for digital signatures.
RSA cryptosystem has been seemed to be secure because it is diﬃcult to prime factorize a composite number composed of two prime numbers with large number of digits.
However, elliptic curve cryptography has been used in recent years because it’s security
is higher than RSA. Therefore, we create a program that performs prime factorization
with a larger number of digits by the elliptic curve method (ECM). Then, we verify
security of the RSA cryptosystem. For that purpose, we have carried out activity withthe goal of ranking in ECMNET[2] and STUDIO KAMADA[3]. ECMNET and STUDIO KAMADA is a website ranked by large number of prime factorization.
First, we divided into two groups, that Theory group and Program group. The purposeof Theory group was to understand manuscripts for speeding up ECM, and to hand over
it to Program group. The purpose of Program group is to implement algorithm which
prepared by Theory group and to validate whether or not we can do increase in speedof program.
Theory group aimed for algorithmic discovery and understanding to be able to perform
Stage2 of ECM with high-speed.We understood a theory used for a program of last yearof project, we understood Baby-step Giant-step, and we implemented them in PARI/GP
in first semester. We understood a theory Montgomery curve and Pollard’s ρ method
and we considered whether to implement FFT in second semester.
Programgroup aimed to speed up the ECM program created in last year. We
modified the code of the part where the coordinate conversion was wasting last year
program, implemented Baby-step Giant-step method, added the function of forcibly
terminating parallel processing, and tested speed of Stage 2.Program group made ECM
program using Montgomery Curve. In addition, we implemented prime table, layered
in Xeon, and made shell script etc. In addition, we created a description of the source
file.
These two groups complemented each other missing parts and carried out activities.
As a result, we succeeded in speeding up Stage 2, and completed a program capable offast prime factorization.
KeywordElliptic Curve Method, prime factorization, ECMNET, STUDIO KAMADA, Twisted Edwards Curve, Extended Twisted Edwards Coordinates, RSA cryptosystem, Baby-step Giant-step method, Pollard’s ρ method, FFT（※文責: 中島俊平）- ii -

目次
第1章

背景

1

1.1

本プロジェクトの背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

ECMNET とは. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.3

STUDIO KAMADA とは . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.4

課題の概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

到達目標

4

第2章

2.1

本プロジェクトにおける目的. . . . . . . . . . . . . . . . . . . . . . . . . . . .

4プログラムの性能の向上化 . . . . . . . . . . . . . . . . . . . . . . . . . .

4

課題達成の為の班分け . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

活動内容

6

3.1

基礎学習 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

3.2

理論班 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.1.1
2.2
第3章

3.3

3.4

3.5

3.2.1

楕円曲線法とは. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

3.2.2

Baby-step Giant-step . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.2.3

素数ペアリング. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

3.2.4

Montgomery 曲線 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

3.2.5

Pollard’s ρ 法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

3.2.6

Brent のアルゴリズム . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

プログラム班 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

3.3.1

座標変換の際の冗長なコストの削減 . . . . . . . . . . . . . . . . . . . . .

16

3.3.2

ソースコードの改善 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

3.3.3

Montgomery 曲線による楕円曲線法の実装 . . . . . . . . . . . . . . . . .

18

3.3.4

素数テーブルの実装 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

3.3.5

VPS の導入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

3.3.6

開発環境と実行環境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

3.3.7

プログラムの実行方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

3.3.8

本プロジェクトで作成したソースファイルの説明書の作成 . . . . . . . . .

23

3.3.9

スクリプトの作成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

3.3.10 Xeon におけるソースコードの階層化 . . . . . . . . . . . . . . . . . . . .

24

中間発表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

3.4.1

準備

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

3.4.2

アンケート . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

3.4.3

発表

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

最終発表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

3.5.1

準備

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

3.5.2

アンケート . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28- iii -

3.5.3

発表. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

第4章

プロジェクト内のインターワーキング

30

第5章

結果

33

5.1

理論班 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

5.2

プログラム班 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

5.2.1

計測結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

5.2.2

STUDIO KAMADA . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

第6章

まとめ

37

6.1

前期活動成果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

6.2

後期活動成果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

6.3

今後の展望 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

参考文献

39

- iv -

FUN-ECM Project

第 1 章 背景RSA 暗号は，大きい桁数の素因数分解が難しいことを安全性の根拠としている．そこで，楕円曲線法 (ECM) を利用し高速に素因数分解を行い，RSA 暗号の安全性を検証することが私たちの目的である．また，そのプログラムを利用して大きい桁数の素因数分解を行い，ECMNET やSTUDIO KAMADA へランクインすることも目標として掲げた．
（※文責: 中島俊平）

1.1

本プロジェクトの背景

暗号技術は，情報の保護やコンピュータセキュリティにおいて欠かせない技術である．ファイルの暗号化の他に，HTTPS や，無線 LAN における通信など多くの場面で暗号技術が利用されている．しかし，暗号技術は常に進化する攻撃方法により解読の脅威に晒されている．様々な攻撃方法
から安全な暗号アルゴリズムを作成するためには，作成する側が暗号解読の方法を知る必要があ
る．暗号の安全性評価は暗号解読の技術が利用されていて，暗号の強度は暗号解読に必要な情報量と計算量によって評価される．今回のプロジェクトでは，その暗号解読アルゴリズムの１つである，楕円曲線法 (ECM) を学ぶ．
現在，有名な公開鍵暗号の１つとして RSA 暗号がある．RSA 暗号は，桁数が大きい合成数の素因数分解が困難であることを安全性の根拠としている暗号である．RSA 暗号を解読する時は，合成数の元となる 2 つの素因数を見つけ出す必要がある．楕円曲線法では，与えられた曲線の点のス
カラー倍が無限遠点になることによって，因数が発見される．この性質を利用することで，RSA暗号が解読できる．
楕円曲線法には Stage1 と Stage2 があり，Stage1 で素因数分解できなかった場合，Stage2
で素因数分解を試みる．前年度のプロジェクトでは Stage1 のプログラムはほぼ完成していたため，今年度のプロジェクトでは Stage2 を完成させることを課題とした．また，ECMNET やSTUDIO KAMADA という分解した素因数の大きさを競うサイトがあり，Stage2 を実装することで ECMNET や STUDIO KAMADA でのランクインをすることを目標として掲げた．
（※文責: 福永慧）

1.2

ECMNET とは

ECMNET とは，楕円曲線法を用いてカニンガム数を素因数分解し，見つかった素因数の大きさをランキング形式で競う Web サイトである．

ECMNET は，特定の範囲のカニンガム数の素因数分解を行うことで，Cunningham project に貢献することを主な活動としている．
カニンガム数，Cunningham project の詳細を以下に記す．

Group Report of 2017 SISP

-1-Group Number 11-A

FUN-ECM Project
カニンガム数以下の条件を満たす数をカニンガム数という．なお ECM N ET では，変数 b，n の範囲を限定している．
カニンガム数:bn ± 1s.t.

b, n ∈ N,

b は累乗数でないCunningham project
Cunningham project とは，b，n を表 1.1 の範囲に限定したカニンガム数を素因数分解するプロジェクトである．

b

2

3

5

6

7

10

11

12

n の上限

1300

850

550

500

450

400

350

350

表 1.1 Cunningham project における b，n の範囲

2018 年 1 月 19 日現在，ECMNET にランクインするためには，2017 年のトップ 10 で 65 桁，
全期間のトップ 50 で 68 桁以上の素因数を発見する必要がある．
（※文責: 中島俊平）

1.3

STUDIO KAMADA とは

STUDIO KAMADA とは，レプディジットやニアレプディジットなど合成数の素因数分解を行い，結果を報告する個人 Web サイトである．合成数を素因数分解するための方法も多様であり，その中の 1 つに楕円曲線法がある．ECMNET 同様に，解読された素因数の大きさをランキング形
式で競うことが出来る．STUDIO KAMADA で対象とされている合成数を以下で説明する．
レピュニットrepeated unit の略で，1，1111，11111111 のような 1 だけからなる自然数のこと．
レプディジット

repeated digit の略で，レピュニットを含む，すべての桁の数字が同じ（ぞろ目）自然数のこと．
ニアレプディジット

near − repeated unit の略で，レプディジットから 1 桁だけ他の数字に置き換えた自然数のこと．
プラトウアンドデプレッション
レプディジットから，両端の数字を共通の異なる数字に置き換えた自然数のこと．
クワージレプディジット
レプディジットから，2 つの桁の数字を共通の異なる数字に置き換えた自然数のこと．
ニアレプディジット回文数
ニアレプディジットのうち，桁数が奇数で中央の数字だけが異なる自然数のこと．
（※文責: 福永慧）

Group Report of 2017 SISP

-2-Group Number 11-A

FUN-ECM Project

1.4

課題の概要

本プロジェクトでは，楕円曲線法の Stage1 の部分については去年の時点でほぼ完成していたた
め，Stage2 を中心に作成することにした．Stage2 を完成させることで，大きな合成数を素因数分解することを目指す．そして，ECMNET や STUDIO KAMADA へのランクインを目指す．
（※文責: 福永慧）

Group Report of 2017 SISP

-3-Group Number 11-A

FUN-ECM Project

第2章
2.1

到達目標

本プロジェクトにおける目的

RSA 暗号は桁数の大きい合成数の因数分解が難しいことを安全性の根拠としている．しかし，その合成数の因数分解が容易にできてしまうと RSA 暗号は簡単に解読できてしまう．簡単に解読されてしまうと RSA 暗号の安全性が保証されない．当プロジェクトでは，RSA 暗号の安全性を保証するために素因数分解を行うプログラムを作成した．プログラムを作成するために課題を設定した．

プログラムの性能の向上化

2.1.1

プログラムの性能を確認するために，ECMNET と STUDIO KAMADA に記載されている合成数などを用いて計算を行った．ECMNET や STUDIO KAMADA に記載されている合成数の素因数分解が成功した場合，当プロジェクトの名前が ECMNET や STUDIO KAMADA に記載される．合成数の素因数分解を行うプログラムの性能を向上させるために，既存のプログラムを改善し，単位時間ごとの計算速度を向上させる必要がある．そのため，この目的を達成するために以下のことを実施した．
（※文責: 水上敬介）• 既存のプログラムのバグの修正• プログラムの無駄な処理の除去• 論文の読解• アルゴリズムの検討・理解• Stage2 においての新たなアルゴリズムの実装• プログラム内で扱う曲線の変更• プログラムの性能検証のための合成数の決定（※文責: 水上敬介）

2.2

課題達成の為の班分け

前年度のプロジェクトでは前期で ECM についての学習を行い，後期でアルゴリズムの提案・実装を行っていた．しかし，このような日程でプロジェクトを進行していくと以下のような問題が発生した．

• 実際にプログラムを実装する期間が少ない• 完成したプログラムを試行する期間が少ない• 巨大な合成数の分解を行いにくい

Group Report of 2017 SISP

-4-Group Number 11-A

FUN-ECM Project
本プロジェクトでは，5 月上旬まで全員で楕円曲線法についての基礎学習を行った．5 月中旬以降，既存のプログラムを改善するためにグループ全員でアルゴリズムの理解と実装をするのは効率が悪いと判断し，プログラム班，理論班の 2 つのグループに班分けをした．以下にそれぞれの班の課題を述べる．
理論班
楕円曲線法について理解を深め，前期では，計算速度の向上のためのアルゴリズム，Stage2
での新たなアルゴリズム (Baby-step Giant-step) の検討，理解に取り組んだ．後期では，モンゴメリー曲線を用いた計算，ρ 法，高速フーリエ変換，素数ペアリングの検討，理解に取り組んだ．逐次，理解したアルゴリズムをプログラム班に説明した．
プログラム班
前期では，既存のプログラムの内容を理解し，プログラムの動作内容の理解に取り組んだ．
理論班から提示されたアルゴリズム (Baby-step Giant-step) をもとに，既存のプログラムを基に実装を行った．後期では，モンゴメリー曲線，素数ペアリングの実装を行った．
（※文責: 水上敬介）

Group Report of 2017 SISP

-5-Group Number 11-A

FUN-ECM Project

第3章

活動内容

プロジェクトが発足した当初，楕円曲線についての基礎知識がなかったため，去年のプロジェク
トでも基礎知識を身につけるために使われた資料 [1] を用いて，理解した．理解できないところは
プロジェクトリーダーが主体となって解説をしてもらい楕円曲線についての基礎知識を学んだ．その後，アルゴリズムの提案をする理論班，提案されたアルゴリズムをプログラムに実装するプログ
ラム班に分けてプロジェクトを進行した．
（※文責: 水上敬介）

3.1

基礎学習

去年のプログラムを理解するために５月の中頃までメンバー全員が楕円曲線法のアルゴリズムや基礎知識についての学習を行った．具体的な内容は以下の通りである．
有限体
素数 p に対し，0 から p − 1 までの整数の集合 Fp = {0，1，…，p − 1} を有限体と言う．Fp
では四則演算が可能であり，楕円曲線法ではこの範囲で考える．

Euclid の互除法
自然数 a，b(a ≥ b) に対して以下の操作を繰り返し行い，余りが 0 になるまで行うことによって a，b の最大公約数を求めるものである．

Algorithm 1 Euclidean Algorithm
Require: a, b ∈ N, a, b ̸= 0, a ≥ b
Ensure: gcd (a, b)
while b ̸= 0 do
q ← a/br ← a mod ba←bb←r
end while
以後，a, b の最大公約数を gcd (a, b) と表記することとする．
拡張 Euclid の互除法
与えられた整数 a，b，c に対し，未知数 x，y に関する一次方程式 ax + by = c の整数解は，1 組存在すれば無数に存在する．この方程式を一次不定方程式という．一次不定方程式の解を求めるには，拡張 Euclid の互除法が有効である．拡張 Euclid の互除法は，自然数 a，bに関する一次不定方程式 ax + by = gcd(a，b) を満たす無数の整数 x，y を効率よく求めることができるというものである．例として 174x + 69y = 3 の整数解を求める．まず Euclid

Group Report of 2017 SISP

-6-Group Number 11-A

FUN-ECM Projectの互除法を用いて 174 と 69 の最大公約数を求める．

174/69 = 2 ∗ 69 + 36
69/36 = 1 ∗ 36 + 33
36/33 = 1 ∗ 33 + 3
33/3 = 11となる．そしてこれらは

3 = 36 − 33 ∗ 1
33 = 69 − 36 ∗ 1
36 = 174 − 69 ∗ 2と表せるので3 = 36 − 33 ∗ 1= 36 − (69 − 36 ∗ 1) ∗ 1= 36 ∗ 2 + 69 ∗ (−1)= (174 − 69 ∗ 2) ∗ 2 + 69 ∗ (−1)= 174 ∗ 2 + 69 ∗ (−5)
以上より，174x + 69y = 3 の整数解は (x, y) = (2, −5) と求めることができる．有限体 Fp において除算 a ÷ b を計算する場合，p と b は互いに素なので，拡張 Euclid の互除法により不定方程式 px + by = 1 の解 (x0 , y0 ) を求めることができる．このとき

px0 + by0 = 1 となるので，有限体 Fp 上では by = 1，つまり b− 1 = y0 が成立する．よって a ÷ b = a × b−1 = a × y0 と変形することで，除算を乗算に置き換えて計算できる．
楕円曲線の定義方程式a, b ∈ Fp に対して y 2 = x3 + ax + b で定義される曲線を有限体 Fp 上の楕円曲線という．
楕円曲線の加算と逆元(加算) 楕円曲線上のある 2 点 P, Q を通る直線をとすると，楕円曲線と直線 ℓの 3 つ目の交
点 R (= P × Q) の x 軸に関する対称点を R とする．これで得られた点 R を R′ の逆元と呼び，R = −R′ が成り立つ．また，R を P と Q を加算した点と定義し，R = P + Q が成り立つ．
無限遠点
楕円曲線上の点 P とその逆元 − P をとり，P + (−P ) を考える．そうすると，２点を通る直線と楕円曲線には P と − P の他には交点が存在しない．このような状態のときに，存在しない点を仮想的に考え，それを無限遠点と呼び，P + (−P ) = O が成り立つ．
楕円曲線の２倍算
楕円曲線上の点 P の接線を ℓとし，楕円曲線と直線 ℓの P 以外の交点を R′ とし，R′ の逆元を R とする．この R は R = P + P = 2P であり．楕円曲線の 2 倍算と定義する．

Group Report of 2017 SISP

-7-Group Number 11-A

FUN-ECM Project
楕円曲線の scalar 倍算
点 P と自然数 d に対して，
点 P を d 倍 (dP = P + P + P + P +・・・・+ P (d 個の和)) することを，楕円曲線の scalar 倍算という．

以上のことを基礎学習として学んだ．以下の章では，２つの班のそれぞれの活動内容を記述する．
（※文責: 落合航平）

理論班

3.2

理論班では，楕円曲線法の，特に Stage2 を高速化するために論文を探し理論を理解した．そして，プログラム班にアルゴリズムの実装を引き継いだ．前期では，Baby-Step Giant-Step やMontgomery 曲線の理論をプログラム班に提案した．後期では，Montgomery 曲線の詳細な実装，
Baby-step Giant-step の発展形である素数ペアリング，Brent のアルゴリズムをプログラム班に提案した．その他にも，Pollard’s ρ 法や FFT についても検討を行った．
（※文責: 落合航平）

3.2.1

楕円曲線法とは理論班では，楕円曲線法について，[5] を参考にし，理解をした．楕円曲線法は，1985 年 Lenstra
によって提案された中規模合成数の因数分解にとってよいとされているアルゴリズムである．楕円
曲線は曲線のパラメータを変えることで位数がランダムに変わるという性質を持っている． そのため群の位数と合成数の相性が悪ければ，パラメータを変更し曲線を変更すればよいため，効率的に因数を見つけることができる．楕円曲線法は大きく Stage1，Stage2 に分けられる．
楕円曲線法の Stage1
本節では，合成数 N の因数 p を見つけることを考える．合成数 N の桁数から，因数の大きさを予想して，パラメータ B1 ，B2 を定める．合成数 N と B1 ，B2 の対応表を表 3.1 に記す．
digitsoptimal B1
optimal B2

20
11,0001,100,000

25
50,0005,000,00030
250,000
25,000,000

35
1,000,000
100,000,000

40
3,000,000
300,000,000

45
11,000,000
1,100,000,000

50
43,000,000
4,300,000,000

表 3.1 素因数の桁数に対応する適切な B1 ，B2 の値ある楕円曲線上の射影座標で与えられた点 P = (XP : YP : ZP ) を利用し，以下の手順で，因数を見つけることができる．

Step1 楕円曲線を決定し，点 P を選択する．
Step2 B1 以下の自然数全てにおける最小公倍数 l = lcm (2, 3, ..., B1 ) を求める．
Step3 点 Q = l × P = (XQ : YQ : ZQ ) を計算する．
Step4 ZQ と N の最大公約数 d = gcd(ZQ , N ) を計算する．
(1) d が 1 よりも大きいならば，プログラムを終了する．
(2) d が 1 ならば，Stage2 に移行する．
Group Report of 2017 SISP

-8-Group Number 11-A

FUN-ECM Project
楕円曲線法の Stage2

Stage1 のみを利用していると，素因数を見つけやすくするには B1 を大きくし，非常に大きい数
l に対して，scalar 倍 l × P を計算しなければならない．scalar 倍の計算は，非常に計算量が大きくなってしまうため，Stage2 を用いる．
楕円曲線法の Stage1 で因数を見つけることができなかったとき， modp での位数は，少なくとも B1 よりも大きい．そのため，楕円曲線法の Stage2 では，B1 から B2 までの素数 s の中に，位数があるかを調べる．

B1 < s < B2 を満たす全ての素数 s1 , s2 , s3 , . . . , sk について Stage1 の結果得られた点 Q に対す
る scalar 倍をそれぞれ求める．

s1 × Q = Q1 = (x1 , y1 )s2 × Q = Q2 = (x2 , y2 )s3 × Q = Q3 = (x3 , y3 )...
sk × Q = Qk = (xk , yk )x1 , x2 , x3 , . . . , xk を求め，合成数 N との最大公約数を求める．Q1 , Q2 , Q3 , . . . , Qk のうちある点 Qi で Qi = O (mod p) を満たせば素因数が求まり，成功となる．
（※文責: 金子真澄）

3.2.2

Baby-step Giant-step

去年までのプログラムでは楕円曲線法の Stage2 の計算に，総当たり法を用いていた．この方法では，k 回の scalar 倍が必要となるため高速ではない．そこで今年は総当たり法に代わり

Baby-step Giant-step を実装した．Baby-step Giant-step とは，B1 < s < B2 を満たす全ての素数 s1 , s2 , s3 , . . . , sk に対して，s を変形して計算を行うことで高速化を図る手法である．

Stage2 は s × P ≡ O のとき成功する．この式を変形していく．まず s を( aa)
s = av + u
− <u<
2
2

(3.1)

と変形する．すると

s×Q≡O(av + u) × Q ≡ O(av) × Q = −u × Qと言い換えられる．この式を満たすかを確認すればよい．(u × Q は −に計算しておける)

(3.2)
a
a
< u < であるから事前
2
2

ここで逆元の関係にある点の x 座標は等しい．つまり (av) × Q の x 座標を Gx ，−u × Q の x
座標を Hx とすると

Gx ≡ Hx(mod p)Gx − Hx ≡ 0 (mod p)← Gx − Hx が p の倍数が成り立つ．

Group Report of 2017 SISP

-9-Group Number 11-A

FUN-ECM Project
これまでの説明をまとめると，Gx − Hx ≡ 0 (mod p) となる s が存在するならば，(av) × P =−u × P となる s が存在する．すなわち，s × P = O となる s が存在するため，Stage2 が成功，素因数分解が完了となる．
ここで，全ての s について Gxk − Hxk を計算しすべてを掛け合わせた数を d をすると，

Gx − Hx ≡ 0 (mod p) となる s が存在すれば，d ≡ 0 (mod p) となる．したがって d と合成数 Nの最大公約数を求めることで素因数 p が判明する．Baby-step Giant-step の手順は，以下のようになる．

Step1 B1 < s < B2 を満たすすべての素数 s について計算する．
(1) 素数 s について v ，u を求める
(2) (3.2) 式の左辺の x 座標 Gx ，(3.2) 式の右辺の x 座標 Hx を求める
Step2 d = (Gx1 − Hx1 )(Gx2 − Hx2 ) . . . (Gxk − Hxk ) を計算する
Step3 d と合成数 N の最大公約数をとる．
Step4 最大公約数が 1，N 以外ならその数は求めたい素因数であり，成功する．
Algorithm 2 Baby-step Giant-step
Require: E: 楕円曲線，Q0 : 楕円曲線法の Stage1 で得られた点，B1 ，B2
Ensure: p: 因数for each i = 1 to a − 1 do
H[i] ← i × Q0
end forQ ← a × Q0d←1
for each prime s = B1 to B2 dou ← s/av ← s%aG←v×Q
d ← d × (Gx − H[i]x )end forq ← gcd(d, N )if q > 1 thenreturn q
else
return FAIL
end if（※文責: 金子真澄）

3.2.3

素数ペアリング

Baby-step Giant-step をより高速化する手法として，素数ペアリングがある．楕円曲線の定義から，点 H と逆元の関係にある点 −H は x 座標が等しいため，Gx − Hx を計算すると，Gx + Hx

Group Report of 2017 SISP

- 10 -

Group Number 11-A

FUN-ECM Projectも同時に計算していることになる．そのため，vw ± u の両方が素数になるとき，結果的に計算量が少なくなる．以下，詳しい理論である．

(av) × P = −u × P(3.3)

先ほどの (3.3) 式の計算を掘り下げて考える．逆元の定義より，−u ∗ P と u ∗ P は，x 軸に対して対称であり，x 座標の値が等しい．
つまり，(av) × P = −u × P と (av) × P = u × P ではその後の (Gx − Hx ) の値は同じになる．
もし，av + u，av − u がともに素数だったとき，従来の計算手法だと，同じ計算を 2 重に行うことになり効率が悪い．そこで，av + u と av − u がともに素数になるペアを計算し，s がどちらかの時のみ Gx − Hx を求めることにより，Step1 の計算回数が減るため高速化できる．
積極的なぺアリング
上記のペアリングの発展形として，より積極的なペアリングを考えることができる．

(av) × P = −u × P

s = av + u= a(v − 1) + (a + u)(a(v − 1)) × P = −(u + a) × P= a(v − 2) + (2a + u) (a(v − 2)) × P = −(u + 2a) × P(3.4)= a(v − 3) + (3a + u) (a(v − 3)) × P = −(u + 3a) × P...
式 (3.3) は式 (3.4) のように変形できる．もし，s = av + u は素数だったが，av − u が素数でないためにペアリングできなかったときに，s = av + u = a(v − 1) + (a + u) = a(v − 2) + (2a + u) =a(v − 3) + (3a + u) = . . . と考えることで，より深くペアを探すことができる．ペアの数が増え，手順の回数がより減るため，高速化が期待できる．一方で，(3.3) 式の右辺が増える分，多くの事
前計算が必要となることを考慮するべきである．
（※文責: 落合航平）

3.2.4

Montgomery 曲線

私たちのプロジェクトでは，楕円曲線として Twisted Edwards 曲線を利用していたが，Mont-gomery 曲線 [6] を導入するため，論文を探した．
Montgomery 曲線の特徴として，y 座標を用いずに加算，2 倍算ができるということがある．
そのため，y 座標を計算せず，計算時間を減らすことができる．Weierstrass 曲線，Twisted

Edwards 曲線では (x, y) = (X/Z, Y /Z) という射影座標系を用いていたが，Montgomery 曲線では，x = (X/Z) 座標のみで計算することができる．以下は Montgomery 曲線について理解したことである．

Montgomery 曲線の定義
Montgomery 曲線は，パラメータ a, b を用いて，
Ep (a, b) : by 2 = x3 + ax2 + x 但し b(a2 − 4) ̸= 0

(3.5)

で定められる．

Weierstrass 曲線と同様に，射影座標系を導入することを考える．このとき方程式 (3.5) に，
x = X/Z, y = Y /Z を代入すると方程式: bY 2 Z = X 3 + aX 2 Z + XZ 2Group Report of 2017 SISP

- 11 -(3.6)
Group Number 11-A

FUN-ECM Project
Algorithm 3 PAIR
Require: B1 , B2 ∈ N
Ensure: {(u, v) ∈ N2 | s = av ± u are prime numbers between B1 and B2 }amin ← ⌊(B1 + w)/2w⌋
set Qq to empty state for each q satisfying |q| < w
while more primes between B1 and B2 do
get next prime s, where B1 < s < B2a ← ⌊(s + w)/2w⌋
while a > amin + L doamin ← amin + L − ⌈umax /w⌉
for all q satisfying |q| < w do
for all a′ Qq with a′ < amin doremove a′ from Qq
output the pair (2a′ , |q|)end forend forend whileq ← s − 2aw {so s = 2aw + q}
{look for mate in Q−q or save in Qq }repeatif Q−q is nonempty thenremove the front element a′ of Q−q{we have found two primes 2aw + q and 2a′ w − q}u ← w(a − a′ ) + q
if u > umax thenoutput the pair (2a′ , |q|)else
output the pair (a + a′ , u)
end ifelse
insert a at the rear of Qq
u ← 0 {force exit from loop}
end ifuntil u < umax
end while{end of loop over primes}
for all q satisfying |q| < w dowhile Qq is nonempty doremove front element a′ of Qq
output the pair (2a′ , |q|)
end while
end forGroup Report of 2017 SISP

- 12 -

Group Number 11-A

FUN-ECM Projectが得られる．

Montgomery 曲線上の点の加算，二倍算
Montgomery 曲線上の点 P = (X :: Z) に対して，自然数 m, n を用いて，Pm = mP =(Xm :: Zm ), Pn = nP = (Xn :: Zn )，Pm−n = Pm − Pn = (Xm−n :: Zm−n ) とする．このときMontgomery 曲線上の点における加算，二倍算は次の計算でできる．

Group Report of 2017 SISP

- 13 -

Group Number 11-A

FUN-ECM Project

加算：Pm+n = Pm + Pn = (Xm+n :: Zm+n )Xm+n = Zm−n [(Xm − Zm )(Xn + Zn ) + (Xm + Zm )(Xn − Zn )]2
Zm+n = Xm−n [(Xm − Zm )(Xn + Zn ) − (Xm + Zm )(Xn − Zn )]2
二倍算：P2n = Pn + Pn = (X2n :: Z2n )4Xn Zn = (Xn + Zn )2 − (Xn − Zn )2X2n = (Xn + Zn )2 (Xn − Zn )2Z2n = (4Xn Zn )[(Xn − Zn )2 + (A+2)(4Xn Zn )]4

加算，二倍算の式を見ると，確かに y 座標を用いずに計算できることがわかる．Pm と Pn の加算をするとき，Pm−n を用いることは，不便である．

Montgomery ladder
Pm と Pn の加算をするとき，Pm−n を用いることは，不便に思うかもしれないが，楕円曲線法
においては，重大な問題とならず，Montgomery ladder と呼ばれる方法を用いると，点 Pm−n を変化させずに計算することができる．

Algorithm 4 は，Montgomery 曲線上の点 P ，ある 2 進数 d に対して，scalar 倍 d × P を計算する Montgomery ladder である．但し，add point(R0 , R1 ) は点の加算，double point(R0 )，double point(R1 ) は点の二倍算を意味している．
Algorithm 4 Calculate dP with Montgomery ladder
Require: Point P = (X :: Z) on a Montgomery curve，the binary representation of d =
m
∑
ki 2i
i=0

Ensure: The point k × P = (Xk :: Zk )R0 ← (0 :: 0)
R1 ← Pfor (i = m; i ≥ 0; i − −) do
if ki = 0 thenR1 ← add point(R0 , R1 )R0 ← double point(R0 )else
R0 ← add point(R0 , R1 )R1 ← double point(R1 )end ifend forreturn R0
アルゴリズムにおける R0 , R1 は，常に R0 = kP , R1 = (k + 1)P , k ∈ N が成り立つため，R0 ，

R1 の差は P となり，効率的に計算することができる．
（※文責: 金子真澄）

Group Report of 2017 SISP

- 14 -

Group Number 11-A

FUN-ECM Project

3.2.5

Pollard’s ρ 法

楕円曲線法のほかにも合成数から因数を見つけるアルゴリズムが研究されてきた．理論班では，因数分解する方法として，ρ 法に関して学習した．
ランダムウォーク関数 f を用いて，xk+1 = f (xk ), yk = x2k と定める．例えばランダムウォー
ク関数として，f (x) = x2 + 1(mod N ) を用いる．

Step1 xi , yi を計算する．
k∏
Step2 α =|xi − yi | を計算する．
i=1

Step3 gcd(α, N ) を計算する．
理論班では，ρ 法を実現できるか論文を探していたが，楕円曲線を用いた方法を見つけることができず，楕円曲線法を用いた方法と比べて効率的に計算することができないと考えた．ρ 法は運が悪ければ，因数を見つける時間がいくらでも長くなる可能性がある．これら 2 点の理由から，ρ 法の実装をしなかった．
（※文責: 落合航平）

3.2.6

Brent のアルゴリズム

Brent は，Birthday Paradox に基づく方法を提案している．楕円曲線法の Stage2 を解くアルゴリズムとして提案された．Brent のアルゴリズム [7] は，次の手順で行う．

Step0 ランダムウォーク関数 f を用意する．
楕円曲線法の Stage1 で得られた点 P に対して，Q1 = k × P , Q2 = l × P を計算する．


P + Q1 (r mod k ≡ 0)





P + Q2 (r mod k ≡ 1)
f (P ) =


...





P + Qk (r mod k ≡ k)
Step1 α = 1, P1 = P = (X1 : Y1 : Z1 ) を設定する．

Step2 P2 = f (P1 ), P3 = f (P2 ), . . . , Pk = f (Pk−1 ) を計算する．
k ∏i∏(Xi Zj − Zi Xj ) を計算する．
Step3 α =i=1 j=1

Step4 d = gcd(α, N ) を計算する．

Stage1 で得られた点 Q，B1 < q < B2 となる因数 q があるとすると，qQ ≡ O が成り立つ．
前述の Step3 において α を求める計算は，莫大な時間がかかる．この演算を行うのに，FFT(fastFourier transform:高速フーリエ変換)[8] と，IFFT（inverse fast Fourier transform:逆高速フーリエ変換）を利用することで計算量を減らすことができると言われている．そのため，理論班では，FFT についての論文を読み，理解に努めた．しかし，FFT についての前提知識が十分でないため，論文を読むことが困難であったことに加えて，GMP を利用した FFT の実装は難易度が高く，最終発表に間に合わないと判断したため実装には至らなかった．

Group Report of 2017 SISP

- 15 -

Group Number 11-A

FUN-ECM Project
離散フーリエ変換（離散フーリエ変換の式）

F (t) =

N−1∑

f (x)e−i N

2πtx

x=0

高速フーリエ変換（高速フーリエ変換の式）

F (t) =

N−1∑

f (x)e−i N

2πtx

x=0

（※文責: 落合航平）

3.3

プログラム班プログラム班では，昨年度の FUN-ECM プロジェクトで作成したプログラムを使用し，単位時間あたりの計算量を増幅させるために，プログラムの改善を行った．高速化するために，Stage2での Baby-step Giant-step の実装，Montgomery 曲線の実装，Stage2 における素数テーブルや素数ペアリングでの計算，去年のソースコードの不具合の修正を行った．今後のプロジェクトのことを考え Xeon におけるソースコードの階層化，ソースコードのドキュメントの作成を行った．作成
したプログラムをテストするために VPS をレンタルした．また，昨年度のプログラムと今年度のプログラムの速度を比較するために，計測方法を確立させた．具体的には以下の通りである．
（※文責: 水上敬介）

3.3.1

座標変換の際の冗長なコストの削減

前年度のプロジェクトで作成された楕円曲線法プログラムでは，scalar 倍をする際の座標を射影
座標から拡張射影座標に変換していた．scalar 倍を行う処理は楕円曲線法プログラムを実行する際に何度も使われるので，処理速度に影響する．そのため，最初から拡張射影座標を用意することによって座標変換する分のコストを減らすことが出来た．射影座標から拡張射影座標に変換する際に使われたアルゴリズムを Algorithm 5 に示す．

Algorithm 5 Projective Coordinates to Extended Coordinates
Require: (PX,PY,PZ) is Projective, (EX,EY,ET,EZ) is Extended, N ≥ 2
Ensure: (EX,EY,ET,EZ)
EX ← P X × P Z
EX ← EX mod N
EY ← P Y × P Z
EY ← EY mod N
ET ← P X × P YET ← ET mod N
EZ ← P Z × P Z
EZ ← EZ mod N

Group Report of 2017 SISP

- 16 -

Group Number 11-A

FUN-ECM Project
Algorithm 5 では，乗算を 4 回と mod の計算を 4 回行っている．プログラム班では，scalar 倍を行う前に行われていた Algorithm 5 を省略することによって，計算コストを削減することが出来た．
（※文責: 福永慧）

3.3.2

ソースコードの改善

scalar 関数における引数の修正
前年度のプロジェクトでは scalar 倍を行うときに座標Ｐのみを用意して，座標Ｐを scalar 倍したものを座標Ｐに代入していた．そのため，scalar 倍の処理を複数回行った場合，scalar 倍された
座標に scalar 倍を行っていたことが分かった．しかし，scalar 倍を複数回行った場合でも，1 回分の scalar 倍の座標が必要であった．この問題は scalar 倍が行われる座標Ｐの他に，その結果を代入するための座標を用意することで解決した．以上を簡単に計算式で表す．
前期の scalar 倍算

P = kP(k = 1, 2, ....., m)(3.7)

Q = kP(k = 1, 2, ....., m)(3.8)

後期の scalar 倍算

Extended dedicated add 関数の修正
前年度のプロジェクトで作成された楕円曲線法プログラムでは，拡張射影座標を用いて加算をしていた．ECM プログラムで加算を行う関数の名前を Extended dedicated add と名付けていた．
しかし，関数内の記述に書き損じがあり，正しく加算が出来ていなかった．今年度のプロジェクト
ではその記述を発見し，修正した．

main 関数における並列処理部分の変更
楕円曲線法プログラムでは，OpenMP を導入して並列処理が行なえるようにしていた．並列処理は main 関数内にある for 文に用いられていた．
今年度のプロジェクトでは main 関数内にある for 文の冗長性を発見し，ソースコードの修正を行った．前年度のプロジェクトで記述されていた処理を Listing 3.1 に記す．
Listing 3.1 前年度の並列処理
1
2
3
4
5
6
7
8
9
10

i n t found =0;
f o r ( i =0; i <n u m b e r o f e l l i p t i c c u r v e s ; i ++) {mpz t f a c t o r ;mpz init ( factor ) ;i f ( found == 0 ) {ecm ( f a c t o r , N, X, Y, d , B1 , B2 , fp , w i n d o w s i z e ) ;i f ( mpz cmp ui ( f a c t o r , 1 ) != 0 && mpz cmp ui ( f a c t o r , N) != 0 )found = 1 ;}}Listing 3.1 の概要を以下に記す．
Group Report of 2017 SISP

- 17 -

Group Number 11-A

FUN-ECM Project• 関数 ecm は与えられた合成数Ｎの素因数分解を行う関数である．関数 ecm では，素因数分解された素数を引数 factor へ返す．

• 関数 ecm で素因数分解された素数が 1 かつ合成数 N でない場合，found に 1 を代入する．
• found が１の時，for 文の処理が終わるまで ecm 関数を計算しない．
今年度のプロジェクトでは，このソースコードの改善点を 2 つ見つけた．1 つ目に引数 found が

1 でも，ループから抜け出せていない点があった．2 つ目にこの for 文は並列処理で行われているので，他のスレッドの処理が終わるまでプログラムの処理が終わらないという点があった．今年度のプロジェクトではこれらの 2 点を改善するために，Listing 3.1 の 9 行目と 10 行目の間に exit関数を用いた．また，found が 1 の時のみ exit 関数を呼び出すように記述した．
（※文責: 福永慧）

3.3.3

Montgomery 曲線による楕円曲線法の実装

後期のプロジェクトでは Montgomery 曲線を用いて，stage1 と stage2 の実装を行った. 計算公式は，Montgomery Ladder Algorithm というアルゴリズムを用いて，scalar 倍算を行った. このアルゴリズムはどの曲線にも適用することが可能であり，アフィン座標や射影座標の両方で実行することが可能であるが，特に Montgomery 曲線を射影座標で表現している場合に効率的だと言われている. また，射影座標で表現されている場合アルゴリズムの中間計算は X 及び Z 座標のみを使用して実行することができ，Y 座標を使用することがない. ただし，計算された後の座標の Y 座標
は必要な場合 X 座標と Z 座標から取得することが可能である. 今回は，stage1 と stage2 の両方でMontgomery 曲線を用いているため，Y 座標を取得する必要がなかったので，使うことがなかった．
また，Montgomery 曲線は by 2 z = x3 + ax2 z + xz 2 （ただし，b(a2 − 4) が 0 以外）の式から

x = 1，z = 2 とし，a，y はランダムで取り，b はそれぞれの取った値を代入した式から計算して求めた．
次に，作成された Montgomery 曲線を使用した楕円曲線法プログラムの stage1 のソースコード
を Listing3.2 に記す．
Listing 3.2 Montgomery ecm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

while ( p <= B1 ) {i n t found =0;e = ( i n t ) ( l o g ( B1 ) / l o g ( p ) ) ;f o r ( i = 1 ; i <= e ; i ++){
m o n t g o m e r y s c a l a r (P , P , p , montgomery a , N ) ;mpz gcd ( f , P−>Z , N ) ;i f ( mpz cmp ui ( f , 1 ) != 0 && mpz cmp ( f , N) != 0 ) {mpz set ui ( f , 1);
goto FACTOR FOUND;}}
mpz nextprime ( prime , prime ) ;p = m p z g e t u i ( prime ) ;}計算の概要を以下に記す．

Group Report of 2017 SISP

- 18 -

Group Number 11-A

FUN-ECM Project• 関数 Montgomery ecm は与えられた合成数Ｎの素因数分解を行う関数である．関数 ecm では，素因数分解された素数を引数 factor へ返す．

• 任意の Montgomery 曲線に対して，B1 以下の素数 p で関数 montgomery scalar で計算を行う．

• 関数 Montgomery ecm で素因数分解された素数が 1 かつ合成数 N でない場合，found に
1 を代入する.
• 素因数分解されなかった場合または，関数 Montgomery ecm で素因数分解された素数が 1かつ合成数 N だった場合，mpz nextprime により p の次の素数を p に代入する．

• P は，任意に定められたモンゴメリ曲線上の一点の x，y，z の値を格納している．
ま た ，新 た に 関 数 montgomery scalar を 作 成 し た ．関 数 montgomery scalar の ア ル ゴ リ
ズムは Montgomery ladder(詳しくは Algorithm2 を参照) を参考に作成された．関数 mont-

gomery scalar のプログラムは Listing3.3 に記す．

Listing 3.3 montgomery scalar
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

s e t ( R0 , P ) ;s e t (TP, P ) ;montgomery double ( R1 , R0 , a , N ) ;while ( k > 0 ){bit [ i ] = k % 2;
k >>= 1 ;i ++;}f o r ( i = m − 2 ; i >= 0 ; i −−){
i f ( b i t [ i ] == 1 ){montgomery add ( R0 , R1 , R0 , TP, N ) ;montgomery double ( R1 , R1 , a , N ) ;}else{
montgomery add ( R1 , R0 , R1 , TP, N ) ;montgomery double ( R0 , R0 , a , N ) ;}}計算の概要を以下に記す．

• k は scalar 倍算の係数を引数に取っており，bit 配列に k の二進数を格納している．
• set は第 1 引数の座標に第 2 引数の座標を代入する関数である．
• montgomery add 関数は加算の計算をしており，第２引数と第３引数の加算を第１引数に代入している．第 4 引数は加算される座標同士の距離であり，第５引数は合成数である．

• montgomery double 関数は 2 倍算の計算をしており，第 2 引数を 2 倍算して第 1 引数に代入している．第 3 引数は Montgomery 曲線における係数 a であり，第 4 引数は合成数である．

• R0 の初期値は，任意に定められた Montgomery 曲線上の一点の x，y，z の値を格納している．

Group Report of 2017 SISP

- 19 -

Group Number 11-A

FUN-ECM Project• R1 の初期値は，R0 の 2 倍算の座標である．
• a は，任意に定められた Montgomery 曲線の係数 a を表している．
• montgomery scalar 上では，R0 と R1 の座標の距離が常に TP で成り立つため，montgomery add 関数において R0 と R1 の減算を計算する必要がない．
scalar 倍算の流れとして，素数 k を 2 進数に変換する．次に 2 進数の最大桁数から順番に値を見て１だった場合，R0 ← R0 + R1，R1 ←2 * R1 を行う．0 だった場合，R1 ← R0 + R1，R0← 2 * R0 の計算を行う．全ての計算が終了すると R1 を返す．
次に，Montgomery 曲線を使用した楕円曲線法プログラムの stage ２を作成した．stage2 のア
ルゴリズムは，twisted edwards 曲線を使用したプログラム同様に Baby-step Giant-step を元に作成した．工夫した点として，本プログラムでは，Giant-step の区切りを 210 として作成した．そのため，Baby-step は 210 と互いに素な値が必要となる．よって，偶数は必要ないので，計算方法を工夫することで奇数倍の計算しか行わないようにした．加算を用いて奇数倍のみを作成する計算方法として，k + (k + 1) = 2k + 1(k = 1, 2, ....., m)(3.9)という式を用いた．この計算式の結果は 2k がどの k の値にもかかわらず必ず偶数となるため，

2k+1 は必ず奇数になる．詳細な計算は，Listing3.4 に記す．
Listing 3.4 Montgomery 曲線を使用した Baby-step の取り方
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

s e t ( add mP , P ) ;montgomery double ( double mP , P , ma , N ) ;s e t ( temp , P ) ;s e t ( temp2 , double mP ) ;f o r ( i = 0 ; i < 5 3 ; i ++){mpz set ui ( ti , 2 ∗ i + 1);
mpz gcd ( gcd , t i , t f ) ;i f ( mpz cmp ui ( gcd , 1 ) == 0 ){s e t ( b a b y s t e p [ i ] , add mP ) ;}i f ( i == 0 | | i == 1 ){montgomery add ( add mP , add mP , double mP , P , N ) ;i f ( i == 0 )s e t ( temp3 , add mP ) ;}else{
montgomery add ( temp , temp3 , P , temp2 , N ) ;montgomery add ( add mP , temp , temp3 , P , N ) ;s e t ( temp2 , temp3 ) ;s e t ( temp3 , temp ) ;}}計算の概要を以下に示す．

• P の初期値は，任意に定められた Montgomery 曲線上の一点の x，y，z の値を格納している．

Group Report of 2017 SISP

- 20 -

Group Number 11-A

FUN-ECM Project• temp，add mp の初期値は P で，double mp の初期値は，P を 2 倍算したものである．
• temp2 の初期値は，double mp を代入したものである．
• temp3 の初期値は add mp と double mp を add 関数で加算した結果の 3P である．
• 23 行目の montgomery add 関数は式 (3.6) を利用したものであり，add mP に奇数値を代入している．
また，Baby-step 同様に Giant-step も montgomery add 関数を利用するため，計算方法を工夫する必要があった．Giant-step におけるプログラムを Listing3.5 に記す．

Listing 3.5 Montgomery 曲線を使用した Giant-step の取り方
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

unsigned long i n t v2 ;PRIME TYPE ∗ s=&(p r i m e t a b l e [ n e x t p r i m e i n d e x ( p r i m e t a b l e , B1 ) ] ) ;v2 = ( ∗ s − f / 2 ) / f ;m o n t g o m e r y s c a l a r ( g i a n t s t e p , P , f , ma, N ) ;m o n t g o m e r y s c a l a r ( Giant , g i a n t s t e p , v2 , ma, N ) ;m o n t g o m e r y s c a l a r ( temp , g i a n t s t e p , ( v2 − 1 ) , ma, N ) ;p r o j e c t i v e p o i n t s e t ( temp2 , Giant ) ;while ( ∗ s <= B2 ) {v = (∗ s − f / 2) / f ;while ( v != v2 ) {v2++;
montgomery add ( Giant , Giant , g i a n t s t e p , temp , N ) ;p r o j e c t i v e p o i n t s e t ( temp3 , Giant ) ;p r o j e c t i v e p o i n t s e t ( temp , temp2 ) ;p r o j e c t i v e p o i n t s e t ( temp2 , temp3 ) ;}u = abs ( ( ∗ s − f / 2 ) % f − f / 2 ) ;mpz mul mod ( product , Giant−>X, b a b y s t e p [ ( u − 1 ) / 2]−>Z , N ) ;mpz mul mod ( a1 , Giant−>Z , b a b y s t e p [ ( u − 1 ) / 2]−>X, N ) ;mpz sub ( product , product , a1 ) ;mpz mul mod ( d , d , product , N ) ;s ++;}mpz gcd ( p , d , N ) ;計算の概要を以下に示す．

• 間接参照演算子*s には素数テーブルで格納した素数の値が入っている．22 行目の s++ でポ
インタをインクリメントすることによって，素数テーブル内の次の素数を割り当てている．

• Giant の初期値は v2fP であり，素数テーブルへ参照している値の倍算である．
• giant step の初期値は fP であり，1 つ分の大きさの Giant-step を示している．
• temp の初期値は (v2-1)fP であり，Giant と giant step の距離を示している．
• v は素数と Giant-step の大きさ f の徐算であり，素数が Giant-step を越えるたびに v の値
が 1 ずつ増えていく．

• v2 は過去の v を保存するための変数であり，10 行目の while 分で，v != 2 が成り立つ時にv2 から v までの回数分の Giant-step を加算を行う．
• 12 行目の montgomery add は Giant と giant step の距離を第 4 引数に代入する必要があ
るため，temp を用意し代入した．
（※文責: 小澤貴也）

Group Report of 2017 SISP

- 21 -

Group Number 11-A

FUN-ECM Project

3.3.4

素数テーブルの実装

プログラム中の実行時間について調べたところ，gmp nextprime 関数が時間を多く使っていることがわかった． gmp nextprime 関数は与えられた数の次の素数を返す関数である．この関数は内部で計算を行っていたため，より効率良く素数を求めることができる素数テーブルを作成することとした．
素数テーブルの概要を示す．素数テーブルとはあらかじめメモリ上に小さい順に素数を用意しておく手法である．メモリ上には unsigned long long int 型の配列として素数が 2,3,5,7,11,13,... と連番で配置されており，配列としてアクセスすることにより簡単に n 番目の素数を取得することができる．この手法により，毎回計算せず 1 回のメモリアクセスで次の素数を取得できるため，高速化につながる．
今回の素数テーブルで必要な素数の上限はプログラムのパラメータである B1,B2 に依存する．
素因数の桁数を 50 桁と想定すると最適な B1 の値は 4300 万となる．B2 を B1 の 100 倍とすると

B2 は 43 億となり，50 桁の素因数を想定した場合に必要な素数の上限は 43 億となる．また同様に，60 桁の素因数が想定される場合は 2900 億までの素数が必要となる．素数を格納するデータ型
は unsigned long long int としているが，これは 2900 億を格納するためには unsigned long int
ではオーバーフローするためである．
なお，この手法は多くのメモリを消費する．前期では 43 億までの素数テーブルを作成したが，後期では 2900 億までの素数テーブルを作成した．43 億までの素数テーブルはおよそ 1.6[GB] となり，2900 億の素数テーブルはおよそ 92[GB] となった．
具体的な実装としては素数テーブルの内容となるファイルを作成し，プログラムを実行した際にそのファイルをメモリ上に配置して利用する．素数テーブルを作成したことにより，最初に素数テーブルをメモリ上に読み込む時間は必要となるが，楕円曲線を用いた演算の部分は大幅に高速化した．
（※文責: 外山拓）

3.3.5

VPS の導入

より多くの素因数分解を試すため，VPS を導入することとした．前期まででは学内のサーバ一台で素因数分解を行っていたが，一台のみでは素因数分解の試行回数が限られていた．また，素因数分解の実行中はプログラムの開発が行うことが難しいという事情があった．そのため，後期からは新たに 2 台の VPS を導入することとした．これにより学内サーバー，VPS1，VPS2 の 3 台により開発・実行を行えるようになった．学内サーバーは主に ECMNET の素因数分解に使用し，VPS1 はプログラムの開発，VPS2 は STUDIO KAMADA の素因数分解に使用した．その結果，開発と実行を円滑に進めることができ，STUDIO KAMADA の合成数 2 つを素因数分解するという結果に繋がった．
（※文責: 外山拓）

Group Report of 2017 SISP

- 22 -

Group Number 11-A

FUN-ECM Project

3.3.6

開発環境と実行環境

プログラムの実行環境について，前期は Xeon E5-2640 を用いてプログラムを実行していた．

Xeon E5-2640 のスペックとしては，メモリ 64[GB] で CPU12 コアである．しかし，多くの素因
数分解を行うためには計算機資源が足りないと感じたため，新たに VPS を 2 台追加した．VPS のスペックとしては，メモリ 16[GB] 仮想 8 コア SSD200[GB] とした．
（※文責: 外山拓）

3.3.7

プログラムの実行方法

作成したプログラムには方式，合成数 N，B1，B2，出力ファイル名を入力する必要がある．つまり，以下のように使用する．

./funecm [options] N B1 B2 filename
options には以下のものが使用できる．
-h: ヘルプを表示する．
-c number: 楕円曲線の試行回数を変更する．
-w bit: Window Method における window size を変更する．
-a: Atkin-Moraine ECPP を使用する．
-m: Montgomery を使用する．
合成数 N には素因数分解を試したい数とする．また，B1 は予想される素因数の桁数により決定する．また，B2 は基本的に B1 の 100 倍として設定する．出力ファイル名には，プログラムの実
行結果を出力するファイル名を表示する．出力ファイルには，最初に合成数 N，B1，B2，楕円曲線の試行回数，Window Method における window size，thread 数が記載されている．その後試行した曲線ごとに，Atkin-Moraine ECPP のパラメータ d，Stage1 と Stage2 とにかかった時間，一試行にかかった時間 (つまり Stage1 と Stage2 をあわせた時間) が記載される．素因数が見つかった
場合は 2 つの素因数とその桁数が表示され，最後にプログラム全体でかかった時間が表示される．
（※文責: 外山拓）

3.3.8

本プロジェクトで作成したソースファイルの説明書の作成

今年度では新たに，素因数分解の自動化を行うためのシェルスクリプトや合成数を作成するソー
スファイルなどを追加した．また，Montgomery 曲線のみでの素因数分解を行うために，前年度のソースファイルに新たなオプションを追加した．上記のように今年度から様々な機能が増えた．
そのため，今までのプログラムを来年度のプロジェクトメンバに理解を促すための作業が必要だった．理解を促す作業として，今年度では学内の Xeon E5-250 に保存したソースファイルの使い方を記したファイルを追加した．また，そのソースファイルのソースコード中にある分かりにくい部
分にコメントを追加した．
（※文責: 福永慧）

Group Report of 2017 SISP

- 23 -

Group Number 11-A

FUN-ECM Project

3.3.9

スクリプトの作成

今回の活動では 3 つのスクリプトを作成し，それぞれテストデータの作成，プログラムの実行，データの集計に使用した．
テストデータの生成は乱数をもとに素数を 2 つ生成し，その 2 つの素数をかけ合わせたものを素因数分解に使用する合成数とした．なお，テストデータの生成では合成数の桁数を指定する．合成数のもととなる 2 つの素数の桁数は，それぞれ合成数の桁数の半分に近い桁数となるようにした．
プログラムの実行に関してもスクリプトを作成した．FUN-ECM のプログラムは桁数が大きくなるにつれ実行時間が準指数関数的に増大していく．プログラムの実行を人間が手で行うことは非効率であるためである．スクリプトは入力として一行に以下の内容を含む CSV ファイルを受け取る．
桁数，素数 A，素数 B，合成数 (A × B)，B1，B2
スクリプトは各行に記載されている合成数に対して指定された B1，B2 を用いて，今年度と昨年度の FUN-ECM のプログラムを実行する．すべての行の処理が終了すると，実行結果の出力ファイルを解析し，各桁の平均を算出しファイルに保存する．なお，スクリプトの実行には nohup コ
マンドを用いることでログアウト後も処理を継続することができる．
データの集計に関しては，プログラムの実行を行うと，結果や実行時間についてのログファイルが保存される．このログファイルを加工し，実行時間を CSV 形式で保存するスクリプトを作成した．

（※文責: 外山拓）

3.3.10

Xeon におけるソースコードの階層化

昨年度ではソースコードのファルダ分けがされておらず，すべて同一のフォルダに実行ファイル
やソースコードが含まれていた．そのため，フォルダ内にファイルが多く含まれ，データの管理やソースファイルの管理が難しくなっていた今年度では，ソースコードを管理しやすくするために，.c と.o やヘッダファイル，実行ファイルをフォルダごとに分類を行った. ソースコードの階層化につき Makefile を大幅に変更した Makefile を実行した際，生成されるファイルは自動的に各フォルダに振り分けられるようになっている．詳細なディレクトリは下記に示す．
（※文責: 水上敬介）

Group Report of 2017 SISP

- 24 -

Group Number 11-A

FUN-ECM Project
ディレクトリ構造
funecm※各ディレクトリに説明のための Readme.txt が存在する├── bin <-プログラムファイル│ ├── funecm├── data <-素数テーブルのデータ│ ├── prime data.bin│ ├── prime table generator│ └── Readme.txt├── inc <-ヘッダファイル│ ├── atkin.h│ ├── bsgs.h│ ├── double add.h│ ├── ecm.h│ ├── gmp.h│ ├── normal add.h│ ├── point.h│ ├── prime.h│ └── scalar.h├── Makefile├── result <-実行結果フォルダ├── obj <-オブジェクトファイル│ ├── atkin.o│ ├── bsgs.o│ ├── double add.o│ ├── ecm.o│ ├── main.o│ ├── normal add.o│ ├── point.o│ ├── prime.o│ └── scalar.o└── src <-.c ファイル├── atkin.c├── bsgs.c├── double add.c├── ecm.c├── main.c├── normal add.c├── point.c├── prime.c└── scalar.c（※文責: 水上敬介）

Group Report of 2017 SISP
- 25 -

Group Number 11-A

FUN-ECM Project

中間発表

3.4

中間発表は，7 月 14 日 (4 時限〜5 時限) に，1 階階スタジオで行った．発表時間は，全 6 回で前後半 3 回ずつ行った．1 回あたり 15 分の発表で，10 分間プレゼンして，残り５分間質問を受けた．
人数の振り分けは前半 3 人，後半 4 人で行った．前後半合わせて教員，生徒合計 74 名聴衆した．
（※文責: 小澤貴也）

3.4.1

準備

ポスター
初めに，前年度のプロジェクトで作成されたポスターを参考に構成を決定した．次に，概要，基礎学習，理論班，プログラム班の 4 つの項目に分け，作成を分担した．ポスターには，イラストを使用するなどよりわかりやすく楕円曲線法について理解できるように工夫した．ポスターは，理論班・プログラム班合計２枚作成した．ポスターの作成には「Microsoft

PowerPoint」というソフトウェアを使用した．ポスターが完成次第，理論班・プログラム班
でレビューを行い，誤字脱字やフォントの違い等を修正した．しかし，中間発表当日に誤字が発見された．
（※文責: 小澤貴也）
プレゼンテーション資料
本プロジェクトの内容を説明するのにポスターだけでは不十分と判断しプレゼンテーショ
ン資料を作成することにした．理論班，プログラム班から一人ずつメインに作成する人を決め，他メンバーと話し合いながら，発表内容を考えた．プレゼンテーション資料の作成には「Microsoft PowerPoint」を使用し，共有に「SharePoint Online for Oﬃce 365」を使用した．また，先生から，内容やデザインの指摘を受け，改良することで，どんな人でも理解できるように努めた．
（※文責: 福永慧）
原稿
前述のプレゼンテーション資料の作成と並行して，発表用の原稿の作成を行い，グループ
内で担当を決め各ページの原稿を作成した．楕円曲線方法を理解してもらうようになるため，基礎学習の部分を最低限の知識だけを伝えるように作成した．作成した原稿は，担当教員に確認していただき，伝わりにくい表現の修正を行った．
（※文責: 水上敬介）

3.4.2

アンケート

中間発表用アンケートを作成した．アンケートの質問項目は• 発表技術について（10 段階評価，コメント）
Group Report of 2017 SISP

- 26 -

Group Number 11-A

FUN-ECM Project• 発表内容について（10 段階評価，コメント）• 発表内容は理解しやすいものでしたか（10 段階評価）• その他の発表内容について（コメント）の４点であった．
中間発表終了後のアンケートの回答を分析を行った．
アンケートは発表を聞いた教員生徒合計 74 人を対象に回答を行った．分析結果として「発表技術について」は，10 段階評価の内平均 6.6 であった．コメントとしては，「声が小さい」「わかりにくい」などがあった．また，「発表内容について」では，10 段階評価の内平均 5.4 であった．コメントとしては，「内容が難しかった」「理解できなかった」などがあった．「発表内容は理解しやす
いものでしたか」は，10 段階評価の内平均 4.9 であった．
アンケートの分析結果として，発表技術では，声の小さいなど発表者の準備不足があったと考える．また，発表内容については，全体的に低い評価が多かった．理由として，楕円曲線法という馴染みがない知識について理解が難しかったなどが考えられる．しかし，「その他の発表内容について」の項目でポスターやスライドなどについては「イラストがあってわかりやすい」など肯定的なコメントがあった．
以上のことから反省点として，まず発表の準備不足であったことが考えられる．また，楕円曲線法についてわかりやすく説明を行う工夫をする必要があった．

（※文責: 小澤貴也）

3.4.3

発表

発表はスライドの説明をメインとし，ポスターにはスライドの内容をより詳しくしたものを用意した．中間発表会での発表を行い，その結果，スライドに数式が多く，発表時間の短さも相まって，
数学・楕円曲線法をよく知らない人にとって分かりにくい発表になってしまっていた．発表の反省を行った結果，後期末の発表では数学に興味のない人でも概観が分かるようにすることに決めた．
具体的には，スライドでは極力数式を出さずに説明し，興味を持った人に対して，ポスターを用いて専門的な説明をする，という形式をとることにした．
（※文責: 福永慧）

3.5

最終発表

成果発表会は，12 月 8 日 (４時限〜５時限) に 3 階モールで行った．発表時間は，全 6 回で前後半 3 回ずつ行った．一回あたり 15 分の発表で，10 分間プレゼンして，残り５分間質問を受け付けた．前半 4 人，後半 3 人で発表を行った．前後半合わせて教員，生徒合計 87 名聴衆した．
（※文責: 小澤貴也）

Group Report of 2017 SISP

- 27 -

Group Number 11-A

FUN-ECM Project

準備

3.5.1
ポスター

初めに，中間発表で作成されたポスターを参考に構成を決定した．次に，概要，活動内
容，楕円曲線法について，計測結果の 4 つの項目に分け，作成を分担した．今年度活動では，STUDIO KAMADA に本プロジェクトの名前を載せることができたため，その結果を知ってもらうために QR コードを貼った．また，中間発表で作ったポスターの内容に加えて，1 年間の活動を分かりやすくまとめたり，後期で理解したこと，去年と今年の前期と後期のプログラムの計測結果のグラフなどを 3 枚のポスターでまとめた． ポスターの作成には「Microsoft PowerPoint」というソフトウェアを使用した．ポスターが完成次第，理論
班・プログラム班でレビューを行い，誤字脱字やフォントの違い等を修正した．
（※文責: 小澤貴也）
プレゼンテーション資料
中間発表と同様，スライドを作成した．しかし，中間発表のスライドでは，理論的なことが多く書かれていたため，スライドを見ただけでは理解できないところがあった．そのため，成果発表でのスライドでは，数式をできる限り減らし，理論的な説明は発表後にポス
ターを見てもらうという形をとった．さらに，STUDIO KAMADA に載ったことを聞いてもらった人たちに知ってもらうために，ポスターだけでなく，スライドにも載せることにした．
（※文責: 落合航平）
原稿
前述のプレゼンテーション資料の作成と並行して，発表用の原稿の作成を行い，グループ
内で担当を決め各ページの原稿を作成した．前期では，専門用語や数式を使用しすぎて内容が理解できないという意見があった．そのため，成果発表用の原稿では，可能な限り専門用
語や数式を減らし当プロジェクトの概要を理解してもらえるように努めた．発表練習として，メンバーの前で発表をしあい冗長な表現をなくし，聴衆に理解がえられるように原稿を作成した．
（※文責: 水上敬介）

3.5.2

アンケート

最終成果発表用アンケートを作成した．アンケートの質問項目は• 発表技術について（10 段階評価，コメント）• 発表内容について（10 段階評価，コメント）• 発表内容は理解しやすいものでしたか（10 段階評価）• その他の発表内容について（コメント）の４点であった．
最終成果発表終了後のアンケートの回答を分析を行った．
アンケートは発表を聞いた教員生徒合計 87 人を対象に回答を行った．分析結果としてGroup Report of 2017 SISP

- 28 -

Group Number 11-A

FUN-ECM Project「発表技術について」は，10 段階評価の内平均 8.8 であった．コメントとしては，「聞きやすかった」「スライドを上手く使っていた」などがあった．また，「発表内容について」では，

10 段階評価の内平均 6.3 であった．コメントとしては，「活動内容がわかった」「楕円曲線法が少しわかった」などがあった．「発表内容は理解しやすいものでしたか」は，10 段階評価の内平均 6.7 であった．
アンケートの分析結果として，発表技術では，発表に対して準備は出来ていたと考えられる．また，発表内容については，中間発表時比べると評価が上がった．理由として，中間発表の反省から楕円曲線法など技術的な内容をポスターに書くことで発表には，あまり理解が難しい内容を簡略化したことが考えられる．しかし，そのことによって，技術的内容を発表
から簡略化したことで「内容がなかった」など否定的な意見もあった．
以上のことから反省点として，まず中間発表と比較して全体的には良い評価だったと考える．しかしまだ，楕円曲線法についてわからなかったという意見もあったので，よりわかりやすくすることが挙げられる．また，内容を簡略化する部分と発表するべき部分をしっかりと見極める必要がある．

（※文責: 水上敬介）

3.5.3

発表

中間発表の反省を踏まえ，スライドでの説明はほぼ数式を使わず行った．また，今年は SUDIO

KAMADA に名前を載せることができたので，そのことを最初の方で発表し，かつ時間を 8〜9 分に収めて発表を行った．その後の時間は質疑応答やポスターを見ていただいた．
成果発表を見ていただいた方からの評価アンケートでは，なぜ楕円曲線法を使うのか，どうして高速化できたのかなどという，理論的な説明が足りないという指摘をいただき，少し省きすぎてしまったと反省した．その一方で，分りやすかったという声が中間発表のときよりも増え，成果に対しての称賛なども得れたので，中間発表の反省を少しは踏まえられた発表になったと考えられる．
（※文責: 水上敬介）

Group Report of 2017 SISP

- 29 -

Group Number 11-A

FUN-ECM Project

第 4 章 プロジェクト内のインターワーキング• 中島俊平（プロジェクトリーダー・理論班）(1) 楕円曲線法の基礎を学んだ．
(2) 大まかな作業スケジュールを作成し，進捗管理を行った．
(3) ”Implementing the Elliptic Curve Method of Factoring in Reconfigurable Hardware”
を落合，金子と協力して読解した．

(4) PARI/GP で Baby-step Giant-step のプログラムを作成し，メンバーに共有すること
で，理解を深めた．

(5) 中間発表会に向けて，進捗管理を行った．
(6) 中間発表会に向けて，「理論班」の部分のポスターの原案を作成した．
(7) 落合，金子と協力して，FFT，素数ペアリング，Pollard’s ρ 法の理解をした．
(8) 最終発表会に向けて，進捗管理を行った．
(9) 最終発表会に向けて，「理論班」の部分のポスター・スライドの原案を作成した．
• 金子真澄（理論班）(1) 楕円曲線法の基礎を学んだ．
(2) ”Implementing the Elliptic Curve Method o Factoring in Reconfigurable Hardware”
を落合，中島と協力して読解した．

(3) 落合，中島と協力して，PARI/GP で ECM を実装した．
(4) 落合，中島と協力して，Baby-step Giant-step のアルゴリズムをプログラム班に教えた．
(5) 中間発表に向けて，「理論班」の部分のスライドを作成した．
(6) 落合，中島と協力して，FFT の理解をした．
(7) 落合，中島と協力して，素数ペアリングの理解をした．
(8) 落合，中島と協力して，Pollard’s ρ 法を理解した．
(9) 落合，中島と協力して，Brent のアルゴリズムを理解した．
• 落合航平（理論班）(1) 楕円曲線法の基礎を学んだ．
(2) ”Implementing the Elliptic Curve Method of Factoring in Reconfigurable Hardware”
を金子，中島と協力して読解した．

(3) 金子，中島と協力して，Baby-step Giant-step のアルゴリズムをプログラム班に教えた．
(4) 金子，中島と協力して，PARI/GP で ECM を実装した．
(5) 中間発表会に向けて，ポスターの「概要」の部分を作成した．
(6) 金子，中島と協力して，FFT の理解をした．
(7) 金子，中島と協力して，素数ペアリングの理解をした．
(8) 小澤，水上と協力して，ポスターを作成した．
(9) 水上，福永と協力して，成果発表のスライド，原稿を作成した．
• 水上敬介（プログラム班）(1) 楕円曲線法の基礎を学んだ．
(2) プログラム班と協力して昨年度のプログラムの不具合の修正を行った．
Group Report of 2017 SISP

- 30 -

Group Number 11-A

FUN-ECM Project(3) プログラム班でのスケジュール管理を行った．
(4) プログラム班での進行役を務め，課題に対してのメンバーの役割を決めた．
(5) 理論班から PARI/GP を用いて実装されたアルゴリズムをプログラムに実装した．
(6) GitHub のソースコードの管理を行った．
(7) 中間発表に向けてのスライド資料・プログラム班の原稿の原案を作成した．
(8) 論文の”Implementing the Elliptic Curve Method of Factoring in Reconfigurable
Hardware”を福永，小澤と協力して読解した．
(9) 福永，小澤と協力して Montgomery 曲線での楕円曲線法で用いる，加算，2 倍算，scalar
倍の関数を作成した．

(10) 福永，小澤と協力して Montgomery 曲線での Stage1 を作成した．
(11) 福永，小澤と協力して Montgomery 曲線での Stage2 を作成した．
(12) 最終発表会に向けて，福永と協力して各曲線での実行速度の測定を行った．
(13) 最終発表会に向けて，小澤と協力して後期のポスターを作成した．
(14) 後期の実行速度のデータ収集を行い，集計を行った．
• 福永慧（プログラム班）(1) 楕円曲線法の基礎を学んだ．
(2) Baby-step Giant-step の文献を読み，原理を理解した．
(3) 昨年度の FUN-ECM で作られたプログラムを理解した．
(4) Baby-step Giant-step のアルゴリズムを実装した．
(5) 中間発表に向けて，評価アンケートの作成をした．
(6) 中間発表に向けて，ポスターの英訳を行った．
(7) ”Implementing the Elliptic Curve Method of Factoring in Reconfigurable Hardware”
を水上，小澤と協力して読解した．

(8) 水上，小澤と協力して Montgomery 曲線での楕円曲線法で用いる， 加算， 2 倍算，
scalar 倍算の関数を作成した．
(9) 水上と協力して PARI/GP を用いて作成した加算，2 倍算，scalar 倍算の関数のテストを行った．

(10) 水上，小澤と協力して Montgomery 曲線での Stage1，Stage2 を作成した．
(11) 水上と協力して作成段階のプログラムを Github で一時共有した．
(12) Xeon に上がっている楕円曲線法のソースコードの使い方を説明するファイルを作成した．

(13) 成果発表会に向けて，評価アンケートの編集を行った．
(14) 成果発表会に向けて，水上と協力して各曲線での実行速度の測定を行った．
(15) 成果発表会に向けて，落合と協力してスライドを作成した．
• 小澤貴也（プログラム班）(1) 楕円曲線法の基礎を学んだ．
(2) 昨年度の ECM プログラムを理解した．
(3) 昨年度のプログラムの修正をした．
(4) Baby-step Giant-step のアルゴリズムを実装した．
(5) 中間発表に向けて，ポスターを作成した．
(6) ”Implementing the Elliptic Curve Method of Factoring in Reconfigurable Hardware”
を水上， 福永と協力して読解した．

Group Report of 2017 SISP

- 31 -

Group Number 11-A

FUN-ECM Project(7) 水上，福永と協力して Montgomery 曲線での楕円曲線法で用いる， 加算， 2 倍算，
scalar 倍の関数を作成した．
(8) 水上，福永と協力して Montgomery 曲線での Stage1 を作成した．
(9) 水上，福永と協力して Montgomery 曲線での stage2 を作成した．
(10) 成果発表会に向けて，水上と協力してポスター作成した．
• 外山拓（プログラム班）(1) 楕円曲線法の基礎を学んだ．
(2) Baby-step Giant-step の原理を学んだ．
(3) Baby-step Giant-step の実装を行った．
(4) プログラムを実行するサーバの管理を行った．
(5) 昨年度の FUN-ECM のプログラムを理解した．
(6) 昨年度のプログラムの並列処理を高速化した．
(7) テストデータを作成するためのスクリプトを作成した．
(8) 自動実行を行うためのスクリプトを作成した．
(9) VPS の導入を行い，各種設定を行った．
(10) 素数テーブルの設計，実装を行った．
(11) STUDIO KAMADA に記載されている合成数のうち，素因数分解を行う合成数を選んだ．

(12) プログラムの可読性を向上させた．
(13) プログラムのディレクトリを階層化し，可読性を向上させた．
(14) プログラムに関する適切なパラメータについて考察した．
（※文責: 中島俊平）

Group Report of 2017 SISP

- 32 -

Group Number 11-A

FUN-ECM Project

第 5 章 結果
本プロジェクトでは，前期はメンバー全員で楕円曲線法の学習から初め，楕円曲線法の概要を理解した．その後は理論班とプログラム班に分かれた．
（※文責: 外山拓）

5.1

理論班

前期では，まず Baby-step Giant-step の理解がある．基礎学習を終えた後，理論班は Baby-step

Giant-step について学習した．その後，理論班のメンバーそれぞれがそれに関する論文を探し，読むことで，Baby-step Giant-step をより深く理解することができた．そして，その知識を生かし，理論班で最適なアルゴリズムを考え，プログラム班に伝えることができた．また，去年のプログラ
ムで使われていた twiceted Edwards 曲線を Montgomery 曲線に変換することで，プログラムを高速化することができることをプログラム班に伝えることができた．そして，昨年度のプログラムに誤りがあったため，改良すべき点としてプログラム班に提案をしたことが挙げられる．
後期では，プログラムをより高速化させるため，素数ペアリング，FFT の理解と ρ 法の実装検討が挙げられる．ρ 法の実装は様々な論文を探したが，楕円曲線を用いた方法を見つけられず，楕
円曲線を用いた方法と比べて効率的に計算することができないと考えたため，最終的に実装を行わなかった．素数ペアリングについては，理解してプログラム班に伝えることができた．しかし，

FFT は成果発表の準備，プログラムを動かす時間等により，しっかりと理解してプログラム班へ伝えるというところまでには至らなかった．
（※文責: 落合航平）

5.2

プログラム班

5.2.1

計測結果

プログラム班の前期の活動では，Stage2 において Baby-step Giant-step を実装した．確立した計測方法を実証したところ，昨年度のプログラムより Stage2 の精度が向上し，高速化していることが確認できた．実証した結果は図 5.1，図 5.2 のようになったGroup Report of 2017 SISP

- 33 -

Group Number 11-A

FUN-ECM Project

図 5.1 Stage2 の実行にかかった時間

図 5.2 プログラム全体の実行にかかった時間

Group Report of 2017 SISP

- 34 -

Group Number 11-A

FUN-ECM Project

図 5.3 1 つの楕円曲線における実行時間

図 5.1，図 5.2 の結果から，Stage2 においての計算速度が 6〜7 倍向上したことが分かり，プロ
グラム全体の速度の大幅な改善が確認された．後期では，Montgomery 曲線を用いた計算を実装した．前期と計算方法を変更したものを実証した．結果は図 5.3 のようになった．図 5.3 の結果から 1 つの楕円曲線における Stage1 と Stage2 の計算速度が昨年度より約 80 倍向上したことがわかり，プログラム全体の速度の大幅な改善が確認された．
（※文責: 水上敬介）

5.2.2

STUDIO KAMADASTUDIO KAMADA に載っているまだ素因数が見つかっていなかった合成数 2 つの素因数分解
246に成功した．1 つめの合成数は 52×109+11である．素因数分解を行う前は以下のようになっていた．なお，括弧内の値は桁数を示す．

7 × 103 × 117762003928963<15> × 680487860622144784692186689940180556695269802424
5354755917126371127615803226830330902096841626585486261163739440917250043989
4855913620105666975824826219068165435329048574429632381845191827800361219414
933427569218654888877675993473<230>

Group Report of 2017 SISP

- 35 -

Group Number 11-A

FUN-ECM Project
230 桁の部分は合成数であるため，この部分の素因数分解を行った．プログラムを実行した結果，以下のように素因数分解を行うことができた．

2875346089898376501403929557115495946676931705069007<52> ×
2366629405109961217555371941546524027453028644830431871608275152430221324542
1183733989850244368881350937710509336289079138775690840645491197135578954400
531344510723459166224414639<179>プログラムの実行は VPS で行った．また，プログラムのパラメータ B1，B2 は表 3.1 を用いて決定した．曲線の試行回数は 10000 回を上限とし，上限に達した時点で素因数が見つからなかった
場合は次のパラメータを使用して再度 10000 回施行するという方式を用いた．実行時間としては，40 桁の試行で 135804[s]，45 桁の試行で 439470[s]，50 桁の試行で 242554[s] となり，素因数を発見した．合計では 817828[s]=9 日 11 時間 10 分 28 秒となった．
247

2 つめの合成数は 76×109−31である．素因数分解を行う前は以下のようになっていた．

3 × 85711 × 650112876289<12> × 1337489853071<13> ×
3776887093999995593565284031454930840028992047364324027878214996981296264285
7755191719536126331361064769743723934282859378845643509016769241702454838384
5399302922242732813858815189111813681073500825495677960773386249683<219>
219 桁の部分は合成数である，この部分の素因数分解を行った．プログラムを実行した結果，以下のように素因数分解を行うことができた．

91585637851471680049375897339286952218012351<44> ×
4123885777948212640320842802931565219304142056105817360396275265489985689897
5621177864061203593992470947394244850362877403477725271466624752923053042327
56815902519295676657133<175>
実行は VPS で行い，プログラムのパラメータ B1，B2 は ECMNET の Optimal Parameter を参考に素因数の桁数が 50 桁に対応するものを使用した．実行時間としては，221701[s]=2 日 13 時
間 35 分 01 秒となった．
（※文責: 外山拓）

Group Report of 2017 SISP

- 36 -

Group Number 11-A

FUN-ECM Project

第 6 章 まとめ6.1

前期活動成果前期はメンバー全員で楕円曲線法の学習から初め，楕円曲線法の概要を理解した．その後は理論班とプログラム班に分かれた．
理論班は Baby-step Giant-step について理解し，その内容をプログラム班に教えた．また，様々な論文 [4][5] を探して，効率の良い曲線や計算量を少なくするために計算方法の見直し，アルゴリ
ズムについての考察を行った．
プログラム班は昨年度のプログラムの解読を行い，省メモリ化，高速化を行なった．また，理論
班の説明を受け Baby-step Giant-step のアルゴリズムの実装を行った．
（※文責: 外山拓）

6.2

後期活動成果後期では，理論班は Montgomery 曲線を利用した楕円曲線法について理解し，その内容をプログラム班に伝えることができた．また，Baby-step Giant-step をより高速化するため，素数ペアリ
ングの理解をした．また，Pollard’s ρ 法という，新たな Stage2 のアルゴリズムの実装検証や FFTの理解にも取り組んだ．
プログラム班はスクリプトや素数テーブルを作成するグループと Montgomery 曲線を使用した
楕円曲線法の Stage1 と Stage2 を作成するグループに分かれ活動を行った．これらの作業をそれぞれ行い，完成させた．完成後は去年，前期，後期で作成したプログラムの速度比較を行った．その結果，合成数が 20 90 桁の場合，楕円曲線 1 つ分を回す実行速度が去年度のプログラムよりも今年度のプログラムの方が約 80 倍早くなることが分かった．また，前期から VPS で STUDIO

KAMADA での合成数の素因数分解を行っていたプログラムの出力結果を確認した．結果として
2 つの合成数の分解に成功し，STUDIO KAMADA に名前を載せることが出来た．
（※文責: 福永慧）

6.3

今後の展望

最初に今後の課題として，理論班では FFT や符号付き 2 進数展開，Rucus chain などの学習・理解からプログラム班へ伝えることが残っている．プログラム班も，Stage1 で Montgomery 曲線を利用した後，Stage2 で twisted edwards 曲線を利用する曲線変換を導入するということが残っている．それらをすることで，プログラムの高速化がまだまだできることが課題の 1 つとして挙げられる．
また，最終的にできた今年のプログラムは，２ヶ月ほどしか動かすことができなかった．そのため，大きな合成数を試すためには，プログラムを動かすために長い時間が必要だということが分かった．しかし，2 ヶ月という短い期間で STUDIO KAMADA に名前を載せるということがGroup Report of 2017 SISP

- 37 -

Group Number 11-A

FUN-ECM Project
できた．もし，プログラムを動かす時間の確保ができれば，本プロジェクトの目的の一つである，

ECMNET に名前を載せるということができたかもしれないだろう．
以上より，理論班とプログラム班それぞれのやり残したことをやり遂げることでの更なるプログ
ラムの高速化，プログラムを動かすための時間の確保，ECMNET に名前を載せるということが課題である．また，去年作られた本プロジェクトのウェブサイトがあるが，それを編集する権限を引き継いでいなかったので，去年の方から権限を引き継ぐ，または新しくウェブサイトを作ること
で，本プロジェクトの活動をいろんな人たちに知ってもらえるようにしたいと思う．
最後に，本プロジェクトの背景で書いていた，RSA 暗号の安全性を確かめるという部分について，現在どれだけの桁数までが本当に安全であるかということを検証することを新しく行っていきたい．
（※文責: 落合航平）

Group Report of 2017 SISP

- 38 -

Group Number 11-A

FUN-ECM Project

参考文献[1] 伊豆哲也. 楕円曲線暗号入門. https://researchmap.jp/mulzrkzae-42427/, (最終アクセス
2018 年 1 月 19 日)[2] ECMNET. https://members.loria.fr/PZimmermann/ecmnet/, (最終アクセス 2018 年 1 月
19 日)[3] STUDIO KAMADA. http://stdkmd.com/, （最終アクセス 2018 年 1 月 19 日）[4] Kris Gaj, Soonhak Kwon, Patrick Baier, Paul Kohlbrenner, Hoang Le, Mohammed Khaleeluddin, Ramakrishna Bachimanchi. Implementing the Elliptic Curve Method of Factoringin Reconfigurable Hardware. Cryptographic Hardware and Embedded Systems - CHES
2006, 2006
[5] 楕円曲線法（ECM）faireal.net. http://www.faireal.net/articles/6/07/,（最終アクセス 2018
年 1 月 19 日）.

[6] Peter Lawrence Montgomery. Speeding the Pollard and Elliptic Curve Methods of Factorization. Mathematics of Computation. 48 (177): 243264, 1987
[7] Richard P. Brent. Some Integer Factorization Algorithms using Elliptic Curves. AustralianComputer Science Communications 8 (1986), 149-163[8] Peter Lawrence Montgomery. An FFT extension of the elliptic curve method of factorization. University of California at Los Angeles Los Angeles, CA, USA, 1992

Group Report of 2017 SISP

- 39 -

Group Number 11-A