2013年連合発表会
「数論アルゴリズムとその応用」 (JANT) 講演要旨

講演者は登壇者v学会員o非学会員x

「GF(p^12) 上の離散対数問題に対する数体篩法の計算機実験」
早坂健一郎vx (九州大学, k-hayasaka(at)math.kyushu-u.ac.jp)
青木和麻呂x (NTT) 小林鉄太郎x (NTT) 高木剛o (九州大学)

利便性の高い次世代公開鍵暗号であるペアリングの一つ，BN曲線を用いた Optimal Ateペアリングの安全性は，GF(p^12)上の離散対数問題の計算困難性に よって保たれる．CRYPTO2006においてJouxらは，素体GF(p)上の離散対数問題に 対する数体篩法を拡大体GF(p^n)上に拡張したが、この数体篩法による12次拡大 体GF(p^12)に対する実装実験は未だ報告がない．本稿では，素体GF(p)上の数体 篩法で用いられる2次元篩領域における篩を拡張することで得られた多次元篩領 域における篩を提案する．また篩領域の次元などの篩が高速となるようなパラ メータを，見積り式を用いた数値実験により考察した．そして計算機1台により 実験し，203ビット位数の拡大体GF(p^12)上の離散対数問題を43時間 で求める ことができた．

「楕円DH問題と計算量的に等価な問題について」
鑓水 淳一vx (首都大学東京, yarimizu-junichi(at)ed.tmu.ac.jp)
内山 成憲o (首都大学東京)

楕円曲線の等分多項式の持つ性質と同様の性質を持つ数列としてElliptic Divisibility Sequence（以下、EDS）と呼ばれるものがある。2008年にLauter、 StangeによるEDSを用いた有限体上の楕円離散対数問題と計算量的に等価な問題 に関する先行研究はあるが、楕円DH問題との考察はなかった。今回、EDSを用い た有限体上の楕円DH問題と計算量的に等価な問題とその等価性の証明を与えた ので、これについて報告する。

「GF(p)上の超特異楕円曲線におけるHashToPointの高速化」
富田 琢巳vx (日立製作所/九州大学, t-tomita(at)math.kyushu-u.ac.jp)
高木 剛o (九州大学)

RFC5091で提案されたBoneh-FranklinによるIDベース暗号方式 (BF方式) におけ るHashToPointの高速化について考察する．このBF暗号方式では，標数p>5の素 体GF(p)上定義された超特異楕円曲線E:y^2=x^3+x (p=3mod4) と，その曲線Eの q-torsion E[q]が利用される．ここでqはSolinas素数と呼ばれる2^a±2^b±1 (0<b<a) の形をした素数が用いられる．この時，コファクターc= #E/qが低 Hamming重みであれば，HashToPointで必要な楕円曲線のスカラー演算が高速化 可能となる．低Hamming重みのcを探索したところ，1024ビットのp (352ビット のc)に対してHamming重み2のcが存在した．このcを用いてHashToPointを標準的 なPC上でC言語で実装したところ，15%の高速化が確認できた．

「奇数の完全数の最大素因子について」
石井大輔vx (岡山理科大学, s12mm01id(at)std.ous.ac.jp)
青木美穂o (島根大学) 澤江隆一? (岡山理科大学) 森義之? (岡山理科大学)

奇数の完全数の研究の重要なもののひとつとして「奇数の完全数の最大素因子」 があります.最大素因子について,1998年にHagis and Cohen は10^6以上である こと,2003年にJenkinsが10^7以上であること,そして,2008年にGoto and Ohnoは 10^8をいずれも計算機を用い証明しました.Goto and OhnoはJenkinsのアルゴリ ズムを改良し証明を与えています. 2012年に我々はGoto and Ohnoのアルゴリ ズムと手法を改良し,奇数完全数の最大素因子が10^9以上であることを証明しま した.最大素因子を一桁更新するためには約100倍の計算時間が必要ですが,我々 はこの改良によりその計算時間を大幅に短縮しています.今回この証明を講演内 容といたします.

「Woodall数の素数判定について」
浅見 和輝vx (首都大学東京, azami-kazuki(at)ed.tmu.ac.jp)
内山 成憲o (首都大学東京)

1969年にRieselによってN = h*2^{n}-1という形の自然数に対する素数判定法が 提案された。本講演では、Rieselによる素数判定法をWoodall数(W_{n} = n*2^{n}-1)の場合に考察し、高速化を提案する。さらに、実装結果についても 紹介する。

「Ramification of Artin-Scherier extensions of surface over algebraically closed field of characteristic p」
大井 理生vx (京都大学, ooimasao(at)math.kyoto-u.ac.jp)

加藤和也氏によって導入された（SurfaceのArtin-Scherier拡大について定義さ れている）分岐に関する重要な$R$という量を計算するアルゴリズムについて述 べる。$R$の計算がどのように応用されるのかについても述べる。

問い合わせ先

中村憲 (首都大学東京)
nakamula(at)tnt.math.se.tmu.ac.jp