多項式の既約判定アルゴリズム

杉村 立夫  末次 康徳  

誌名
電子情報通信学会論文誌 A   Vol.J72-A   No.8   pp.1345-1352
発行日: 1989/08/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: 論文
専門分野: 情報セキュリティ基礎
キーワード: 


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




あらまし: 
多項式の既約性の判定法は,従来から多項式の因数分解の一つの結果として与えられ,それを判定すべき多項式の形(3項式等)に応じて改良が加えられてきた.本論文では,従来の手法とはまったく異なる観点すなわち既約判定すべき多項式を法とした剰余類の要素の乗法に関する位数に注目することにより,最大計算時間がO(m4)となる一般的な既約判定アルゴリズムを与える.また,多項式の次数がある条件を満たすならば,最大計算時間がO(2(P-1)m3)となる簡略型既約判定アルゴリズムを与える.そして,これら二つのアルゴリズムと従来の手法を計算時間という観点から比較・検討し,十分に実用性のあることを示す.