プロジェクト報告書 Project Report

提出日 (Date) 2017/1/18

FUN-ECM プロジェクト
FUN-ECM Projectb1014129 池野竜將 Ryusuke Ikeno
1 プロジェクトの目的

プロジェクト開始時点では，メンバー全員が ECM についての理解が不十分だった為，白勢先生・由良先生のご本プロジェクトの目的は，素因数分解を行いより大き指導の下，楕円曲線法の基礎的な学習を行った．6 月ご

な桁数の素因数を発見し，ECMNET にランクインするろから，理論班とプログラム班に分かれて高速化アルゴことである．素因数分解は，40 年ほど前から重要になっリズムの提案と実装を並行して行った．後期では，高速てきている．その理由は，RSA 暗号に大きくかかわっ化アルゴリズムの実装と並行して ECM プログラム評価ている．RSA 暗号とは，現在のインターネット上の通の活動を行った．また，後期からは，今年度初の試みと信で広く使われいる暗号技術である．この暗号は巨大なして広報活動を行う．広報活動の目標である「ECM に合成数の素因数分解が難しいことを安全性の根拠とするついて多くの人に知ってもらう」ということを達成する暗号である．つまり，素因数分解は RSA 暗号の安全性ため，以下の項目を課題とした．

を確認するために重要になっている．この素因数分解のアルゴリズムに楕円曲線法（以下 ECM と記述する）が• 広報媒体の設定ある．私たちは ECM による素因数分解プログラムの高• ターゲットに合わせた内容の設定速化を目指す．また，ECMNET という ECM を利用し広報は，今年度初めて行う活動なので，誰に向けて発信大きな素因数を見つけることを目的とするウェブサイトするかを決めた．主なターゲットを未来大の 1・2 年生がある．記録されている素因数の桁数を超える素因数をとし，サブターゲットとして来年度以降のプロジェクト見つけることでランクインすることができ，名前を載せメンバーとした．また，それに合わせた内容をプロジェることができる．私たちは，このランキングに載っていクトメンバー全員で議論した．

る素因数よりも巨大な素因数の発見を目指す．加えて，今年度のプロジェクトから広報活動を行うことにした．

ECM は多くの人が知っているテーマではなく，未来大3 活動内容
3.1

基礎学習

でも知らない学生が多い．そのため，ECM について解ECM プ ロ グ ラ ム の 改 善 や 前 年 度 か ら 引 き 継 い だ説をする web ページを作成し，多くの人に ECM を知っ

ECM プログラムを理解するために 5 月の中旬ごろまでてもらうと共に，本プロジェクトに興味を持ってもらう

はメンバー全員が教授のご指導の下で ECM の基礎知識ことを目指す．

やアルゴリズムについての基礎学習を行った．具体的な

2 課題の設定と到達目標
本プロジェクトの目的を達成するためには，プログラ

内容は以下のとおりである．

• 楕円曲線法の基礎

ムの改善が必要である．改善のために以下の項目を課題• 剰余（Mod）についてとして達成した．

• 楕円曲線上の点の加算・2 倍算• 楕円曲線法の理解• ECM プログラムの高速化アルゴリズムの理解と実装• ECM プログラムの評価

今年度は，前年度に比べて基礎学習の期間を短くし，ECM プログラムの高速化アルゴリズムの提案・実装・実行の期間をより長く確保した．基礎学習を終えた後，本プロジェクトの目的であるプログラムの高速化のための作業に移った．ECM プログラムの高速化には，多数プログラム班全員で読み進めた．わかりにくい部分はそある高速化アルゴリズムから実装可能であり，大きな効の都度，文献や論文を利用して理解した．多倍長演算を果が期待できるアルゴリズムを選び実装する必要があ

行うライブラリである GMP については，読み進めている．これを 1 つのメンバー全員で一斉に行うことは効率く中で順次調べて理解した．また，これらの活動中に前が悪いと考え，プログラム班と理論班に分かれて作業を年度から引き継いだプログラムに冗長な部分があったた行った．

め，変更しても問題が発生しないことを確認したのち冗3.2 理論班

長な部分を変更した．次に理論班から提示されたアルゴ

3.2.1 活動目的

リズムの実装を行った．アルゴリズムの内容は 3.2.1 に理論班は，プログラミング班の実装のために ECM プ記述した．また，プログラムを読み進める中で，改善でログラムの高速化アルゴリズムを調査し，提案することきると予想された部分についても実装を行った．以下にを目的とする．まず，プログラム班に提案するアルゴリ

プログラム班で実装したアルゴリズムを示す．

ズムを絞り，それを理解しわかりやすくすることを目標とした．以下にそのアルゴリズムを示す．

• Extended twisted Edwards coordinates• 楕円曲線の生成法の変更• Twisted Edwards Curve[1]• Atkin-Morain ECPP

• Atkin-Morain ECPP[2]• 移動窓法 [3]3.2.2 活動内容
まず，提案するアルゴリズムを決定するために，CiNiiや Google Scholar を利用して高速化アルゴリズムの提案をしている文献を探し，それぞれ理解を進めた．その中で 3.2.1 で挙げた 2 つのアルゴリズムに注目した．このアルゴリズムに関しての文献を輪読し，アルゴリズムをわかりやすく書き起こしてプログラム班に提案した．

3.2.3 活動成果
Twisted Edwards Curve は早い段階で提案することができたため，プログラム班によって前期中に実装し高速化させることができた．Atkin-Morain ECPP は前期の終わりごろに提案を行ったため，実装は後期になってしまったが，実装できた．しかし，発見確率の検証は行えなかった為，効率が改善したかは不明である．

3.3 プログラム班
3.3.1 活動目的
プログラム班は，ECM プログラムの高速化アルゴリズムを実装し実行速度，素因数発見効率の改善を行うことを目的とする．そのために以下の項目を課題として設定した．

• Stage2 [4]それぞれのアルゴリズムを実装するごとに，前年度のプログラムとの簡易的な比較を行った．比較項目は楕円曲線 1 つの処理を終える時間と，全処理が終了した際に発見できた素数の桁数とした．改善されたことが確認して次のアルゴリズムを実装した．Atkin-Morain ECPP は素因数の発見効率を上げるアルゴリズムであるため，検証ができなかった．そのため，このアルゴリズムは使用するかをコンパイル時のオプションで設定できるように実装した．

3.3.3

活動成果

それぞれのアルゴリズムでプログラムの処理速度が高速化されたことが確認され，昨年度より優れた ECM プログラムが完成した．詳細な検証は次の章で記述する．

3.4

検証

後期から，前年度作成した ECM プログラムとの詳細な比較を行うため，理論班の中でプログラムの検証を行うグループ（以下検証班と記述する）を作成した．

3.4.1

活動目的

検証班の目的は，前年度と今年度のプログラムの詳細• 前年度の ECM プログラムの理解な比較評価を行うことである．高速化のために取り入れ• 理論班の提案したアルゴリズムの実装たアルゴリズムが処理時間にどのような影響がでるのかを調査することは，今後もプログラムを改善していくう

3.3.2 活動内容
まず，前年度の ECM プログラムの理解から始めた．

ECM プログラムは C 言語を利用して記述されており，えで重要である．今年度のプロジェクトでは，ECM プログラムの高速化に加えて素因数発見効率の改善を行ったため，前年度のプロジェクトとは比較方法を変更する善することを中心に活動しており，継続性の強いプロ必要があった．そのため，以下の項目を課題として設定

ジェクトである．そのため，今年度ならではの活動をしした．

たいと考えた．新奇的な活動を行うにあたり，未来大生• 検証方法の調査・提案• 実際に検証を行う• 検証結果の可視化
3.4.2 活動内容
まずは，検証結果に統計的な信憑性を持たせるために検証方法の調査を行った．しかし，どの検証方法も今回の検証には適切でない，または実行するだけの時間が足でも ECM について知らない生徒が多いことからより多くの人に ECM を伝えられるように広報的活動を行うことにした．広報を行うにあたり，以下の項目を課題とした．

• 広報媒体の設定• ターゲットに合わせた内容の設定
3.5.2

活動内容りないなどの理由で使用しなかった．今年度は 20 桁か

まず，広報を行うターゲットを設定した．メインター

ら 50 桁の合成数を 5 桁刻みで各 5 回ずつ入力し，処理ゲットは，未来大を中心とする情報系の大学生とした．

時間のトータルタイムの平均を比較した．検証環境は以加えて，サブターゲットとして ECM に興味を持った方下の通りである．

や，来年度のプロジェクトメンバーを設定した．今年度• コンパイラ:icc 14.0.1• OpenMP:301• GMP:6.0.0• CPU:Intel Xeno Phi 5110P(60 コア)• RAM:64GB(DDR3L-1600 8GB DIMM×8)
3.4.3 活動成果

は，昨年度のプログラムを理解する為に実装してあるアルゴリズムについて文献を利用して調べた．これを事前に簡単にまとめておくことで来年からの活動をスムーズに進めることができると考えサブターゲットをこのように設定した．次に広報媒体の設定を行った．中間発表の意見で，プレゼンだけでは理解しにくかったという意
見をいただいたことから，手軽に閲覧することができ，今年度と昨年度のプログラムのトータルタイムの平均よりわかりやすく伝えることができる媒体として webを比較した結果，20 桁から 30 桁では今年度の結果の方ページを採用した．サブターゲット向けのページはプロが下回る結果になったが，35 桁以降は徐々に上がってグラム班と協力して作成した．

いき，最大 15% ほど改善し，処理速度が上がったこと

3.5.3

活動成果が確認できた．少ない桁数の場合に処理速度が低下してメインターゲット向けのページとして，ECM についしまった原因は，今年度新たに実装した移動窓法の事前て解説したページが完成した．このページでは ECM の計算のコスト大きく，高速化した分のコストを超えてし基礎理論ページ，FUN-ECM の活動目的に分かれていまったことが原因だと考えられる．上記の通り，本プロる．章ごとに分けて詳細な説明を行い，段階的に読み進ジェクトの目的である巨大な合成数の素因数分解を行うめることができるようにした．また，プレゼンテーショのに昨年度よりも優れた ECM プログラムが完成したこ

ンでは使用することのできなかったグラフの gif 画像なとがわかる．

どを利用し，より理解しやすいように工夫したはっき．

3.5 広報サブターゲット向けのページとして，プログラムの解説

後期から，FUN-ECM の活動を発信するため，理論ページが完成した．現在実装してあるアルゴリズムの簡班の中で広報活動を行うグループ（以下広報班と記述す単な解説を載せている．また，来年のプロジェクトメンる）を作成した．

バー向けに，プログラムの実行手順を載せた．

3.5.1 活動目的

3.6 発表広報班の目的は，FUN-ECM の活動を外部に発信し，3.6.1

中間発表会

ECM について多くの人に認知してもらうことである．

中間発表会では，楕円曲線法の基本的なアルゴリズム

本プロジェクトは，前年度からプログラムを引き継ぎ改や，前期中に実装したアルゴリズムについてプレゼンテーションを行った．ECM についての解説は数学の要の検証では，50 桁の合成数を入力した際に 3 時間素を多く含み難解なため，専門的な単語を避けて時間をほど時間がかかっている．巨大な合成数の分解にはかけて説明した．ポスターは，前年度の構成を参考にし多くの時間が必要なため，検証方法を早い段階で決ながら作成した．本番ではプロジェクターの電源が落ち定して検証を行いたい．

るアクシデントもあったが，用意した内容をすべて発表• 新たな活動を行う場合は，前期から行うべきであすることができた．聴講者の評価は発表技術が 7.1 点，る．今年度から，広報活動を行ったが前期中は基礎発表内容が 7.5 点だった．コメントは内容を理解できた

学習と実装を中心に行ったため，広報活動は行わな人とできなかった人に分かれていたため，さらに前提知かった．そのため，アンケートをとる時間が不足し識のない聴講者にもわかりやすい内容にしていく必要がてしまった．新たな活動をする場合は前年度の活動あることがわかった．の流れを大きく変える必要がある．

3.6.2 成果発表会• 発表の際には，素因数分解がどのように実世界で利成果発表会では，中間発表会のレビューを元に，さら用されているかを説明するべきである．最終発表会に前提知識のない聴講者でもわかりやすい内容を目指の評価では，素因数分解が重要なことはわかるが，した．中間発表会に引き続き専門的な用語は極力減らしどこで使われているかもっと具体例が聞きたいといた．加えて，最も大事なところを枠で囲み，その中身をうコメントがあった．公開鍵暗号との関係などを発見るだけで大まかな内容を理解できるように変更した．

表で絡めて説明できるようにしたい．

また，数学に抵抗のある人でも触れやすいように，例示を多く含める，長い数式に関しては説明を省きスライドに載せるだけにとどめるなどの工夫を行った．聴講者の参考文献[1] Hisil, H., Wong, K.K.-H., Carter, G., Dawson,

評価は発表技術が 7.9 点，発表内容が 7.9 点だった．中E. Twisted Edwards curves revisited. Advances

間発表会に比べて大きく点数が伸びており，工夫の効果が表れていることがわかった．しかし，発表内容を省きin Cryptology - ASIACRYPT 2008, 2008[2] Bernstein, D.J. , Birkner, P. , Lange, T. , Peters,

すぎている，数式の説明を省略するのは良くないなどのC. ECM USING EDWARDS CURVES. Mathe-

意見もあった．

matics of Computation, 2013.

3.7 まとめ本プロジェクトの目的は，ECM を利用して素因数分解を行い，より大きな桁数の素因数を発見することであった．これを達成するために，ECM の理解，高速化アルゴリズムの実装を中心に活動を行った．その結果，ECM への理解を深め，ECM プログラムを前年度と比較して最大 15% ほど高速化することに成功した．また，今年度の新たな活動として広報活動を行った．後期のみの活動だったが，web ページを完成させることができた．しかし，web ページがわかりやすいかどうかのアンケートをとることはできなかった．

3.8 今後の展望
今年度は前年度の反省を踏まえて，1 年間の活動計画を大きく変更して行った．改善された点もあったが，問題も発生した．来年度に向けて，今後の反省と展望を示す．

• 検証は時間に余裕をもって行うべきである．今年度[3]

シ ニ ア エ ン ジ ニ ア の 庵.

http://sehermitage.web.fc2.com/index.html,（最終アクセス 2017 年 1 月 13 日）.

[4] Gaj, Kris, et al. Implementing the elliptic curve
method of factoring in reconfigurable hardware.
International Workshop on Cryptographic Hardware and Embedded Systems. Springer Berlin
Heidelberg, 2006