日本応用数理学会研究部会連合発表会

13：00−13：30 ○長尾孝一(関東学院大学 工学部)
クイックソート アルゴリズムの計算量について
ここでは、まず、クイックソートとマージソートの計算量について数値実験では なく理論的な観点から述べ、実際に全てのデータが異なる場合にはクイックソー トの方が早いことを示す.次にハッシュソートアルゴリズムについて紹介する.こ のソートアルゴリズムは数値データのソートにのみつ使える方法であるので、厳 密な意味ではソートアルゴリズムではないが、n個のデータソートにO(n)の計算 量しかかからない.次に、ハッシュソートの考え方を一般のデータに用いて、n個 の一般のデータを同じデータを一まとめにした集合に分割することがO(n)の計算 量でできることを示す.これを使って、クイックソートが苦手とする同一データ をたくさん含むデータのソートに応用する.

13:30 --13:55 ○平野貴人 (東京都立大学理学研究科 M2)
特殊数体篩の効率的なパラメータ選択について
特殊数体篩法を数論システム NZMATHに実装を行い, それを用いて数値実験を行った.具体的な実験内容としては , 理論的に必要とされているパラメータの予想値と実際の計算で必要とするパラメータの値とのギャップを考察することである .その考察によって実際に計算するときのパラメータの値は 4つあるパラメータのうち2つは理論的に予想とされている値から5, 6割り程度減らすことができるとわかった ,などの結果を述べる. 特に代数体の拡大次数が固定されたパラメータについての考察や評価は他に例はない

14:10--14:30 ○名迫健(大阪電気通信大学工学部 M1), 村上 恭通（大阪電気通信大学情報通信工学部通信工学科）
トラップドア複合型高密度ナップザック暗号の提案
近年，量子コンピュータの実現に向けて研究および開発が活発に行われている． 量子コンピュータが実現すると現在使われている多くの公開鍵暗号が解読されることが示されたため， 量子コンピュータにも対応し得る安全な公開鍵暗号を構築することは非常に重要な意味を持つ． 本講演では， 量子コンピュータによる多項式時間解法が発見されていないナップザック問題に再注目し， 従来使用されていた超増加性および偶奇性の両トラップドアを複合して使用した複合トラップドアを用いた新たなナップザック公開鍵暗号を提案する．提案方式は既存のナップザック暗号に対する攻撃法に高い耐性を有する方式である．

14:30--15:00 ○篠原直行(九州大学大学院数理学府 D2)
Frobenius Pseudoprimes and Cyclotomic Polynomials
奇合成数 $n$ が必然的に Frobenius pseudoprime になるときの $n,a,b$ の条件を bad condition of Frobenius test ($bcf$) と名づけた .いくつかの $bcf$ を定義し解析することで以下の事実を示せた。 $b=\pm 1$ に対する Frobenius pseudoprime は無限に多く存在する。 任意の個数の素因子を持つ Frobenius psuedoprime が無限に多く存在する 任意の奇素数が、ある Frobenius pseudoprime の素因子になりうる。 奇合成数 n に対していくつかの $bcf$ の条件がそろえば、 n が Frobenius pseudoprime となる $(a,b)$ を求める.

15:15--15:35 ○五十嵐育弘（岩手県立大学大学院ソフトウエア情報学研究科 M2）、児玉英一郎、 高田豊雄（岩手県立大学大学院ソフトウエア情報学研究科）
位数 a^n の巡回群上の階層的暗号について
複数の任意な暗号鍵で暗号化された複数の暗号文を、 １つのマスター鍵で復号できる暗号・復号関数を、位数 a^n の巡回群上で構成する手法を提案する。また、 巡回群の性質を利用した階層的暗号の実現方法を提案する。

15:35--16:05 知識友輔 (近畿大学理大学院総合理工学研究科理学専攻 M2)、大野泰生 (近畿大学理工学部理学科助教授), 後藤丈志 (東京理科大学理工学部数学科助手)
完全数と調和数の最大素因子について
奇数の完全数が存在するか否かは未だ不明であるが ,もし存在した場合の必要条件は多く知られている .近年, 奇数の完全数の最大素因子は 10^7以上でなければならないことが示された. 本講演では ,この記録を更新するための新しいアルゴリズムについて述べる. また , 完全数の拡張である調和数については,最大素因子についての結果が発表されていなかったが ,本講演では, この方面についての結果も報告する

16:20--16:50 ○飯島 努（中央大学情報工学科、 D4）趙晋輝（中央大学情報工学科）辻井 重男（情報セキュリティ大学院大学）
Security Analysis of Superelliptic Curves against Diem's Algorithm Combined with Weil Descent
Weil descent attackは、ある曲線上の離散対数問題(DLP)を攻撃する代わりに、 Weil restrictionによって新たに生成された曲線のDLPに対して、 攻撃を行う方法である。 一方、Pollard's rho methodは、 DLPを解くための一般的なアルゴリズムとして知られている。 更に、 これよりも速く解ける可能性のある攻撃法としてGaudryによるhyperelliptic curve discrete logarithm problemを解くアルゴリズムがある。 近年、このGaudryのアルゴリズムに関しては、様々な改良が提案されている。 最近の結果として、 hyperelliptic curveに対しては、Nagao, Gaudry-Theriault-Thomeらによるdouble-large-prime variationを用いたアルゴリズムとgenus 3以上のnon-hyperelliptic curveに対しては、Diemによるアルゴリズムがある。 本発表では、これらのアルゴリズムがWeil descent attackと組み合わさった場合の有効性について議論をする。 そのために、元の曲線が有理関数体上tame cyclic extensionであった場合に、 Weil restrictionによって生成された曲線のupper, lower boundの式を用いることで、 特に、genus 3 ,4のsuperelliptic curveに対して、Weil descentを行い、 元の曲線と新たに生成された曲線上の２つのDLPに対して、 コストの比較を行い、実際に、有効になる例とそうでない例を考察したい。