Type-II All One Polynomial Field上での平方根導出アルゴリズムの高速実装

摘要

近年，WeilペアリングやTateペアリング等のペアリング技術を用いたグループ署名の研究が行われており，このペアリングには有限体上で定義される楕円曲線が用いられている．この楕円曲線上の有理点を求めるために定義体上の平方根導出が必要となるが，一般に平方根導出は他の計算に比べて時間がかかることが知られている．著者らは，F_(p~m)における高速な平方根導出アルゴリズムを提案しており，高速な四則演算が行える拡大体AOPF(all one polynomial field)を提案している. 上述の平方根導出アルゴリズムでは，計算にフロペニアス写像を用いている. また，AOPFはフロペニアス写像に計算を一切必要としないので上述の平方根導出アルゴリズムの実装に適している．本稿では，具体的にはF_(p~6)等の拡大次数において実装高速な平方根導出アルゴリズムを実装し，計算機シミュレーションを行った結果について報告する．