プロジェクト報告書 Project Report

提出日 (Date) 2016/01/20

FUN-ECM プロジェクト
FUN-ECM Project1013186 山本 健太 Kenta Yamamoto
1 プロジェクトの目的
本プロジェクトの目的は、楕円曲線法を並列処理できるプ

3 活動内容3.1 前期

ログラムを作成し、大きな整数の素因数を見つけ、ECMNET

前期では課題の 1 つの楕円曲線法の理解を中心に活動をにランクインすることである。現在のインターネットの通信行った。担当教員の白勢先生・由良先生に作成していただいたにおいて、公開鍵暗号の 1 つである RSA 暗号が広く用いられ授業計画に従い、楕円曲線法のアルゴリズムや基礎知識などをている。RSA 暗号は、巨大な数の素因数分解が困難であるこ学んだ。具体的な内容は以下の通りである。とを利用した暗号である。よって、RSA 暗号の安全性は、巨大な数の素因数分解の困難さで評価される。つまり、素因数分解のチャレンジは、重要なテーマとなっている。素因数分解の優れたアルゴリズムの１つに楕円曲線法がある。私たちは、楕円曲線法による素因数分解のプログラムの並列処理と高速化の実現を目指す。

• 楕円曲線法の基本• 剰余について• Z/nZ の四則演算• ラグランジュの定理と点の位数• 無限遠点と因数発見の関連について

また、ECMNET[1] という楕円曲線法によって大きな素因また、学習した内容をもとに PARI/GP[2] を用いて簡単な数を見つけることを目的とするコンペティションがある。現

ECM プログラムを作成した。今回作成したプログラムは学習在記録されている素因数よりも大きな素因数を見つけることしてきた内容が実際にどのように実装されているのか確認すで、ランキングに名前を載せることができる。私たちは、このるためのプログラムである。よって大きな素因数を見つけるサイトのランキングに載っている素因数よりも大きな素因数ことができなかった。

を見つけたい。

2 課題
本プロジェクトの目的である ECMNET ランクインのためには大きな素因数を見つける ECM プログラムが必要となる。
その ECM プログラムの作成にあたって以下の項目を課題として設定した。

• 楕円曲線法の理解• ECM プログラムの高速化と並列化の実装• ECM プログラムの評価

後期では、残り 2 つの課題、ECM プログラムの高速化と並列化の実装と評価の解決のために、プロジェクト全体を射影班、プログラム班、統計班の 3 班に分け活動を進めた。

3.2 射影班
3.2.1 活動目的
射影班の活動目的は、ECM プログラム内の加算公式部分に射影変換を用いて計算量を削減することである。具体的には今年度から採用したエドワーズ曲線を利用した ECM プログ
ラム内の加算公式、2 倍算公式の中の計算コストを削減することを目標とした。

3.2.2 活動内容

プロジェクト始動時にメンバ全員が楕円曲線法についてのまず昨年度のプログラムの計算コストを削減するために使理解が乏しかった点から、前期では白勢先生・由良先生の指導用した射影変換に着目した。今年度のプログラムにも採用すのもと、楕円曲線法の基礎的な学習に取り組んだ。後期では課るためにまずは射影変換を書籍、論文、白勢先生の講義等で学題達成のため高速化の手法の提案、実装、評価を主軸に活動を習した。その後、各計算の計算コストを算出し、昨年度と今年行った。

度の ECM プログラム内の加算公式の計算コストを調べた。

活動成果

3.2.3

3.3.2 活動内容

乗算を基準として各計算の計算コストを算出した際に、各計目的達成のために大きく分けて 5 つの活動を行った。1 つ算の計算コストは乗算を基準とした際に、二乗算は 0.8 倍、逆目は GMP の学習である。GMP とは任意精度演算を行える元計算は 27.5 倍であることが判明した。また、昨年度と今年算術ライブラリである。GMP を用いることで、計算の桁数が度の加算公式一回分の計算コストの比較は以下のようになっハードウェアのメモリ容量以外に制限されなくなるため、楕た。表記の際は乗算を M、二乗算を S、逆元計算を I とした。

円曲線法のような非常に大きな桁数を扱う計算に適している。

• 昨年度射影変換前 : I+2M+S ≒ 30.3M• 今年度射影変換前 : 2I+6M ≒ 61M• 昨年度射影変換後 : 12M+2S ≒ 13.6M• 今年度射影変換後 : 11M+S ≒ 11.8M

インストールや使用方法などを GMP のマニュアルを読み、小規模のプログラムを作成しながら学んでいった。2 つ目は並列処理である。楕円曲線法で大きな桁数の数の素因数分解を行うと処理に莫大な時間がかかる。そこで、並列実行して素因数分解の処理の高速化、効率化を行った。並列処理部分に、これらを全て M に統一して比較すると上記より、昨年度射影

OpenMP を用いたプログラムを Xeon Phi 上で実行した。3

変換前が 30.3M、今年度射影変換前が 61M、昨年度射影変換

つ目はプログラム制作である。アルゴリズム担当とインター後が 13.6M、今年度射影変換後が 11.8M となった。これらのフェース担当に分けコーディング、テスト、実装を行った。不ことから射影変換前の計算コストに比べ射影変換後の計算コ具合に適切に対応できるよう気を付けるなど工夫しながらプスト、昨年度の射影変換後のプログラムの計算コストに比べ今ログラム作成を行った。4 つ目は運用である。効率的に Xeon

年度の射影変換後の計算コストがそれぞれ少なくなっている

Phi を使って運用するために、オンライン作業できるような設ことがわかった。

定をした。5 つ目はマニュアル作成である。Xeon Phi の操作

3.3

プログラム班

3.3.1

活動目的

プログラム班の活動目標は 2 つあった。１つ目は、昨年度は複雑な手順を要するため、他のプロジェクトメンバや次のプロジェクトのためにわかりやすいマニュアルを作成した。

3.3.3 活動成果の ECM プログラムよりも高速に処理ができる ECM プログ

エドワーズ曲線の加算公式に射影変換を適用し、Xeon Phiラムの実装を行うことであった。ECM プログラムを用いて大上で並列処理できるようなプログラムを完成した。そして、昨

きな桁数の素因数を見つけようとした場合、プログラムを長期年度と今年度のプログラムの比較を行った結果、昨年度よりもにわたって動かし続ける必要がある。また、ECM プログラム

15% の高速化ができた。また、プログラム班以外でも簡単には、加算公式の計算処理を繰り返すことで素因数分解を行っ利用できるような簡単なマニュアルの作成もした。ている。よって、加算公式の計算処理コストを減らすことで、

3.4 統計班

ECM プログラムの処理が高速になり、大きな桁数の素因数発3.4.1 活動目的

見の効率化を図れると考えた。そこで、プログラム班は昨年度

統計班は、射影班によって取り入れた理論、プログラム班にのプログラムの加算公式の計算処理部分を中心に改良を行う実装された機能によりプログラムがどれほど高速化したのかことした。具体的には、後期に理論班が作成した射影座標系の検証を目的とした。昨年度の ECM プログラムと今年度作を導入したエドワーズ曲線を用いた楕円曲線法のアルゴリズ成したプログラムの大きな違いは、楕円曲線の形式と射影変換ムを基に、昨年度の ECM プログラムの改良を行った。2 つ式を変更したことである。この違いがプログラムにどのよう目は、ECM プログラムを XeonPhi 実行するための簡単なマな効果をもたらすのかを知ることで、今後のプログラムの改良ニュアルの作成を行うことであった。ECM プログラムは Cに役立てることができる。

言語で記述したが、OpenMP を導入し XeonPhi 上で並列処3.4.2 活動内容理できるようなものにした。よって、XeonPhi 上で ECM プ

どのようにして高速化を検証するのかを話し合い、今回はログラムを実行するために、いくつかの特殊な操作を行う必要プログラムの処理性能の評価をしたいと考えた。合成数を入があった。そこで、特殊な操作の手順をマニュアルにすること力したときの出力までの時間は素因数の大きさなどに左右さで、誰でも XeonPhi 上で ECM プログラムを動かせるようにれるため正確な処理速度の測定には適さない。作成した ECMした。

プログラムは、素数を入力することによってプログラムのすべての処理を終了するまで時間を計測することができるため素するなどの工夫も行った。楕円曲線法についての説明は難解数を入力することにした。実際のプログラムには素数判定のなため、聴講者にできるだけわかりやすくするために時間をか機能が組み込まれているが今回はプログラム班に依頼してそけて丁寧に説明した。また、スライドには Prezi[3] を使い聴の機能を削除して実測に臨んだ。また、処理速度のデータの信講者が飽きないような動きのあるスライドを作成した。ポス

頼性を得るためいくつかの統計方法を模索し実行した。

ターは一目で内容が伝わるように見やすい配置などを心掛け

3.4.3

統計方法た。本番当日ではプロジェクターの不具合などに見舞われた

今年度と昨年度の ECM プログラムの性能を計る為にそれが、準備してきた内容は発表することができた。聴講者の評

ぞれ 5 ∼ 40 桁の素数を入力として実行時間を計測した。各桁価は発表技術・発表内容ともに約 6 点だった。専門的な内容の素数はその桁の素数をランダムに抽出するプログラムを作は理解が難しいということが聴講者のコメントでよく理解で成した。a 桁の素数を抽出する時、その素数の範囲は [1010a−1 + 10⌈ a−1⌉
2a−1,] とした。これによって抽出された素数を用きた。

3.5.2 最終発表

いて計測に使用した。各桁の計測数は今回は 4 人で計測をし最終発表では、前期の反省を踏まえて聴講者にとって理解たが、１人 4 回ずつの計 16 回計測した。私たちは今回データが難しいような専門知識や理論の内容は減らした。代わりに、を計測するにあたり、4 人で同じ性能の 4 台のパソコンを使用聴講者に伝えたい本プロジェクトの成果の射影変換を用いてした。パソコンの性能は以下の通りである。

計算コストを 15% 削減したこと、処理速度を 15% 向上した

• ホスト OS : Windows8.1• ゲスト OS : CentOS6.3• プロセッサ :Intel(R) Core(TM)i3-3120M CPU@2.50Ghz 2.50Ghz• 実装メモリ (RAM) : 8.00GB• システムの種類 : 64 ビット オペレーティングシステム
x64、 ベースプロセッサ

3.4.4

活動成果

今年度と昨年度のプログラムの処理速度を計測した結果、桁数が 10 桁の時の今年度のプログラムの処理速度は 43.562 秒となっている。また、桁数が 40 桁の時の新プログラムの処理ということについて詳しく説明をした。スライドはグラフや表を載せるなど見やすくわかりやすいものにした。ポスター
ではプロジェクト全体について 1 枚、班ごとの活動について 2枚の計 3 枚作成した。発表と併せて読むことで、より理解してもらえるよう専門的な内容をわかりやすくし画像とともに説明をした。聴講者の評価は発表技術・発表内容ともに 7 点で、前期の評価を共に上回ることができた。明確でわかりやすかったという聴講者からのコメントが多かったため、こちらの狙い通りの発表ができていたと判断できる。

4 成果
4.1 射影班

速度は 96.555 秒となり、桁数が 10 桁の時と比べると約 2.2

射影班は射影変換に関する学習を行い、各計算の計算コス倍処理に時間がかかっている。向上率が最大になったのは桁

トを C 言語環境下で各計算を 1 億回行うプログラムを作成

数が 10 桁の時で、約 18% も処理速度が速くなった。各桁数し、そのプログラムをそれぞれ動かし調べて比較した。また射の向上率の平均を出したところ、約 15% 処理速度が向上した。

影変換前後の計算コストの算出を行った。今年度のプログラ

射影班が導入した射影変換により今年度の ECM プログラムに射影変換を用いた結果、昨年度の完成したプログラムの加ムは昨年度使用した ECM プログラムよりも計算コストが約

算公式一回の計算コストが 13.6M だったのに対し、今年度の15% 削減することに成功したことが分かっている。つまりこプログラムの加算公式一回の計算コストが 11.8M だったことの結果は、射影変換によって削減された計算コストが理論通りから、理論上プログラムを約 15% の高速化をすることに成功に処理速度を向上させたことを示している。

したと考えられる。

3.5
3.5.1

発表
中間発表

4.2 プログラム班
プログラム班は初めにコーディングを担当する箇所を振り中間発表では楕円曲線法の基本的なアルゴリズムなどを説分けることでソースコードの共有における食い違いを防いだ。

明し、PARI/GP を使った ECM プログラムの実演などを披

また、コーディングの際には今後の改良やメンテナンスがしや露した。ホワイトボードを使ってアルゴリズムの流れを説明すいよう書くことを心掛けた。こうして新しいアルゴリズムを適用した素因数分解プログラムを完成させた。主な改良点

2 つ目は論文の輪読である。論文を読む時間があまりとれは新アルゴリズムによる高速化、ループ実装による効率化であなかったため、特に楕円曲線法に関する論文をプロジェクトメる。また、学内ネットワークを通じてプログラムを実行できるンバ全員で輪読し、理解を深めたい。

ようにしたことで効率的な素因数探しを行えるようになった。

4.3

統計班

昨年度のプログラムと今年度のプログラムを比較する為に、

5 ∼ 40 桁の素数を 5 桁毎に 16 個ずつ入力し、プログラム内3 つ目はプログラムの試行回数である。プログラムを実際に動かす時間があまりとれなかったため、プログラムの動作回数を稼ぎ、目標とする桁数の素因数分解など、ECMNET への登録に向けた活動をしたい。

部で 1 万回計算を行った時の処理速度の結果を図と表に出力

4 つ目は社会との関連性である。成果発表会で何のためにした。その結果、昨年度のプログラムよりも、今年度のプログ素因数分解をするのかわからないという意見が多かったため、ラムの方が約 15% 処理速度が向上した。射影班が算出した、楕円曲線法や素因数分解がどのように現代社会に関係してい昨年度のプログラムと今年度のプログラムの計算コストを比るかをよく学びたい。また、プロジェクト学習を行う背景や概較した時に、計算コストが今年度のプログラムの方が 15% 削

要などに関係することについて簡潔にまとめ、発表する。特減されていたことがわかる。よって、射影変換によって、理論に、公開鍵暗号や RSA 暗号は素因数分解と密接に関係してい通りに計算処理速度が向上したことが言える。

るため、成果発表会でプロジェクト学習との関連性を示せるよ

5 まとめうにしたい。

本プロジェクトの今年度の目的は楕円曲線を理解し、ECM-NET へランクインすることであった。目的達成のために楕円参考文献[1] ECMNET

曲線法の理解、 ECM プログラムの高速化と並列化の実装、

http://www.loria.fr/~zimmerma/records/ECM プログラムの性能評価の 3 つを主軸において活動を進

ecmnet.html (最終アクセス 2016 年 1 月 5 日)

め、以下のことを達成した。1 つ目は前期に基礎学習を行い楕[2] PARI/GP Development Headquarters

円曲線への理解を深めた。2 つ目は従来のヴァイエルシュトラ

http://pari.math.u-bordeaux.fr/ (最 終 ア ク セ ス

ス方程式からエドワーズ曲線に変更し射影変換を導入するこ2015 年 12 月 11 日)とで計算コストを約 15% 削減し、Xeon Phi 上で並列化処理[3] プレゼンソフト — オンラインプレゼンツール — Preziを施した ECM プログラムを完成させた。3 つ目は昨年度とhttps://prezi.com/ (最終アクセス 2015 年 12 月 11

今年度の ECM プログラムを比較し、約 15% 処理速度を向上日)したことを実証した。

6 反省と展望
基本的な理論の学習、プログラムの学習、発表の準備などが主な活動だったため、他の活動に手が回らなかった。来年度のプロジェクト学習に向け、今後の反省と展望を以下に示す。

1 つはステージ 2 の実装である。素因数分解を 2 つのステージに分けて行う方法があり、その場合、今年度行っているECM はステージ 1 で使用される。ステージ 2 では、誕生日攻撃法を利用したロー法による素因数分解を行う。まず、ステー
ジ 1 で素因数分解に失敗した場合、座標が算出される。その座標をステージ 2 で使用することで、素因数分解が成功する場合がある。それにより、素因数分解が成功する確率を高めることができる。今年度の活動では手を付けることができなかったため、今後の活動ではステージ 2 のプログラムを実装し、ステージ 1 と連携をさせたい。