講演日時：　　平成12年11月17日(金)
講演者氏名：　静谷 啓樹
　　　　　東北大学・情報処理教育センター・教授

講演題目：関数計算の複雑さについて
講演内容：

形式言語の複雑さに対応して様々なクラスがあるように、関数を計算する 複雑さについても様々なクラスが定義され、構造の解明が進んでいる。 それらのクラスの構造を概観した後、暗号理論の立場から興味のある関数に ついて、その関数の位置付けを確認する。特に、素数と位数が与えられた とき、その位数をもつ素体上の楕円曲線を構成する問題に注目し、その問題を 関数として定式化するとともに、この関数を決定性多項式時間で計算する アルゴリズムが発見されても不思議ではないこのとの状況証拠を与える。