各講演20分（質疑応答時間を含む）
○印は登壇者
確率的素数判定テストとして,一般的によく用いられているMiller-Rabinテストや, Miller-Rabinテストよりも誤り率の小さい2次強Frobeniusテストがある. この2つの素数判定テストを組み合わせ,パラメータを小さい素数から順に動かしたときに, 連続してテストを通過する最小の合成数を探索する研究が行われている. この先行研究を受け,今回2次強Frobeniusテストのみを用いて同様の実験を行い, 4*10^11までの奇合成数において,x^2-x+2とx^2-x+3の双方に関する 2次強Frobenius擬素数となるものは存在しないことが分かった. 本発表では,先行研究の素数判定テストとの判定効率の比較や,実験結果に関する考察を述べる.
グレブナー基底を効率的に計算する代表的なアルゴリズムとしてF4アルゴリズムが挙げられる。F4アルゴリズムに限らず、グレブナー基底を計算するアルゴリズムの効率は、使用する項順序やS項式の選択、多項式の計算順序などに関係することが知られている。本発表では、多変数公開鍵暗号の暗号方式で利用される種類の多項式集合に注目し、F4アルゴリズムを用いて、そのグレブナー基底の計算における多項式の計算順序の考察について述べる。
Signatureを用いたグレブナ基底を求めるアルゴリズムは、2001年に J.-C. Faugèreが提案したF5アルゴリズムを起源としており、これまでのアルゴリズムと比べて無駄な計算(zero reduction)を多く省くことが可能なアルゴリズムとして知られている。今回、連立二次変数代数方程式の解を求める問題（MQ問題）を対象とし、signatureを用いたアルゴリズムの有効性を考察した。
有限体上の多変数二次多項式の集合を公開鍵としてもつ署名方式の一つであるUOVは、適切にパラメータを選ぶことで十分な安全性を確保できるとともに、署名認証・生成を効率的に行うことができると考えられている。その一方で、鍵のサイズが比較的大きくなりがちであることから、鍵のサイズを小さくする取り組みが行われてきている。Hufu-UOVはそのような小さい鍵をもつUOVのひとつで、Circulant行列やToeplitz行列を利用して鍵サイズの圧縮に成功している。ただし、このような「特殊な」構造を導入することで脆弱性が 生じた例は枚挙にいとまがない。本講演では、Hufu-UOVの特殊な構造によってどの程度 安全性が損なわれたかを説明する。
Modular Magic Sudokuは、数独に条件「各小方陣において、行和、列和、対角線和が法n^2で0と合同」を加えたものである。 位数が最小の9の場合には、Lorch and Weld (2012)により、その構造が解明されている。 そこで、本発表では、ある条件を満たす一つの小方陣からModular Magic Sudokuを構成する方法を提案する。
ナップザック暗号は部分和問題や部分積問題などのナップザック問題の求解困難性を安全性の根拠を置いている公開鍵暗号（暗号方式／署名方式）の総称である．これらのナップザック問題は組合せ論的整数論における問題であると同時にNP困難な問題でもある．多くのナップザック暗号は部分和問題の特徴を利用した低密度攻撃と呼ばれる攻撃法により解読が可能である．解読方法が未知の数少ない暗号方式としてOkamoto-Tanaka-Uchiyama (OTU)暗号 (2000) が知られている．本講演では，等差数列についての Szemer\\'{e}di の定理を真似た言明として Szemer\\'{e}di 型仮定を導入し，平均的な場合と最悪の場合の求解困難性はどのように解釈すべきかをまず述べる．次に，平均的な場合の低密度攻撃における直交格子の最小ノルムの分布についての実験結果から，低密度攻撃の失敗に必要な密度が先行研究の理論的結果よりも広いことを示す．最後に，展望としてOTU暗号の安全性評価を厳密に行うためには何が必要になりそうかについて，組合せ論的整数論の視点から述べる．
金沢工業大学 基礎教育部 数理基礎教育課程
谷口哲也
t.tani@neptune.kanazawa-it.ac.jp