日本応用数理学会2011年度年会
JANT オーガナイズド・セッション
「数論アルゴリズムとその応用」研究集会
プログラム

日時

場所

プログラム

9:00--9:40 (招待講演)

Computational Method and Weber's Class Number Problem
岡崎龍太郎(同志社大学) (講演のアブストラクト[PDF])

9:40--10:00

数論システム NZMATH の有効活用について(2)(要旨1)
☆田中 覚(首都大学東京) 中村 憲(首都大学東京) 宮本 泰徳(首都大学東京) 平野 正樹(首都大学東京)

10:30--10:50

Elliptic Divisibility Sequence を用いた素因数分解アルゴリズムの計算量評価と高速化(要旨2)
☆櫻田尚寿(首都大学東京) 鑓水淳一(首都大学東京) 小椋直樹(首都大学東京) 内山成憲(首都大学東京)

10:50--11:10

GPUを用いた2次元FFT乗算とnegacyclic convolution(要旨3)
○谷口哲也(学習院大学)

11:10--11:30

非可換環の多変数公開鍵暗号への応用(要旨4)
☆安田貴徳(九州先端科学技術研究所)，櫻井幸一(九州大学大学院)，高木剛(九州大学 マス・フォア・インダストリ研究所)

講演要旨

(要旨1) 数論システム NZMATH の有効活用について(2)
☆田中 覚(首都大学東京) 中村 憲(首都大学東京) 宮本 泰徳(首都大学東京) 平野 正樹(首都大学東京)

我々が開発している数論システム NZMATH の性能を評価する為に, これ迄に実装した各種数論アルゴリズムの性能を, 他システムによるものと比較する. 入力データのサイズや実行環境による差異等, 色々な側面から検証する. それにより NZMATHの上手な活用法を探る. 前回は基本算法と初等整数論アルゴリズムを扱い, 整数の試し割算についてNZMATH(Python)は他のシステムと遜色ない程度に速く実行できることを示した. 今回はさらに掘り下げて, 整数分解と離散対数問題のアルゴリズムを扱い, 時間に余裕があれば, 有理数の計算効率について考察する.

(要旨2) Elliptic Divisibility Sequence を用いた素因数分解アルゴリズムの計算量評価と高速化
☆櫻田尚寿(首都大学東京) 鑓水淳一(首都大学東京) 小椋直樹(首都大学東京) 内山成憲(首都大学東京)

楕円曲線の等分多項式の持つ性質と同様の性質を持つ数列としてElliptic Divisibility Sequence（以下，EDS）と呼ばれるものがある． 我々は，日本応用数理学会2011年連合発表会で，このEDSを用いた素因数分解アルゴリズムを提案した． ここでは，この素因数分解アルゴリズムの計算量評価や高速実装等について述べる．

(要旨3) GPUを用いた2次元FFT乗算とnegacyclic convolution
○谷口哲也(学習院大学)

多倍長整数係数多項式に関する2次元FFT乗算を，GPU (Tesla C2050：メモリ3GB) で実装した結果について報告する． 限られたGPUメモリで大きな乗算を行うため，2次元の negacyclic convolution を利用した． その結果，0-padding を用いた2次元FFT乗算に比べ，メモリ使用量のピークを 1/4 に下げることが出来た． また，CPUとGPUの乗算の速度比較についても述べる．（中島匠一氏，市村文男氏との共同研究の一環）

(要旨4) 非可換環の多変数公開鍵暗号への応用
☆安田貴徳(九州先端科学技術研究所)，櫻井幸一(九州大学大学院)，高木剛(九州大学 マス・フォア・インダストリ研究所)

多項式公開鍵暗号（MPKC）はポスト量子暗号の候補の一つであり，暗号化および復号化の処理が高速であるという利点を持つ． 一方で，その安全性は多変数方程式の求解問題の困難性に基づいており，暗号学的に安全なパラメータを選択すると鍵長がRSA暗号と比較して大きくなる問題がある． 講演者らは非可換環を従来のMPKCに応用することにより，この問題を解決した． 実際に，1024ビットRSA署名と同等の安全性を持つとされる署名方式に対し，秘密鍵長を約75%削減できることを説明する．

問い合わせ先

光成滋生(サイボウズ・ラボ株式会社)
herumi@nifty.com