F2 上の既約All One Polynomialを用いた素数次の既約多項式の組織的な生成法

牧田 慶  野上 保之  杉村 立夫  

誌名
電子情報通信学会論文誌 A   Vol.J87-A   No.7   pp.976-984
発行日: 2004/07/01
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: 論文
専門分野: 情報理論
キーワード: 
自己相反既約多項式,  TypeI/TypeII Optimal Normal Basis,  楕円曲線暗号,  

本文: PDF(296KB)>>
論文を購入




あらまし: 
近年考案されている公開鍵暗号方式には,位数の大きな有限体を定義体とするものが多い.これに対して,ハード化しやすいなどの理由から標数を2として高次拡大体を高速実装する研究報告が多く,それに必要となる高次既約多項式の生成法,Optimal Normal Bases(ONB)など高速実装に適した基底の構成法に関する研究報告が多くなされている.高次既約多項式の一生成法として,m 次既約多項式から 2m 次の自己相反既約多項式を簡単な多項式変換(自己相反変換と呼ぶ)により生成する手法が知られており,本論文では,その m 次既約多項式の零点集合が正規基底をなす場合には,生成される 2m 次自己相反既約多項式の零点集合も正規基底をなすことを示す.続いて自己相反変換において,変換を施される既約多項式と生成される自己相反既約多項式が1対1の関係にあることを明確に示し,自己相反既約多項式には自己相反変換の逆変換(自己相反逆変換)が行えることを示す.そして自己相反逆変換により,2m 次の自己相反既約多項式から m 次の既約多項式が必ず生成されることを示し,1/2倍の次数の既約多項式生成につながることを述べる.自己相反逆変換による1/2倍の次数の既約多項式生成の応用として,TypeII ONBを零点にもち,かつ素数次の既約多項式を生成する手法を与える.