研究者情報 | 神奈川大学

マツオ　カズト Matsuo Kazuto 松尾　和人所属神奈川大学情報学部計算機科学科神奈川大学大学院理学研究科理学専攻（情報科学領域）職種教授
言語種別	日本語
発行・発表の年月	2014/01
形態種別	その他論文
標題	既約因子の次数に制限がある多項式の因数分解について
執筆形態	共著
掲載誌名	電子情報通信学会2014年暗号と情報セキュリティシンポジウム予稿集、1C2-3
著者・共著者	小崎俊二、松尾和人
概要	有限体上の多項式の因数分解は超楕円曲線暗号の構成法や攻撃の中で必須なアルゴリズムの一つである。効率的な因数分解アルゴリズムとして知られるCantor-Zassenhausアルゴリズムは多項式の既約因子の最高次数が小さいほど高速に動作する。応用においても多項式が可約であり既約因子の最高次数が既知である場合もある。種数2の超楕円曲線の等分多項式の既約因子の最高次数は等分多項式の次数の3/4乗程度になることが知られている。したがって、既約因子の最高次数が小さいとき高効率なアルゴリズムを利用することで、等分多項式の因数分解が高速化され安全な超楕円曲線暗号の構成が効率化される。Cantor-Zassenhausアルゴリズムには、より効率的な改良がいくつか知られているが、これらは既約因子の最高次数がその効率に影響を与えない。そこで本論文では、Cantor-Zassenhausアルゴリズムの改良アルゴリズムを既約因子の最高次数が与えられた場合に拡張し、既約因子の最高次数が小さいときに一層効率化するアルゴリズムを構成した。さらに、拡張アルゴリズムが現実的な問題に対して効率的に動作することを実装実験により示した。