GF(P) における3次多項式の高速既約判定アルゴリズム

平本 琢士  野上 保之  森川 良孝  

誌名
電子情報通信学会論文誌 A   Vol.J84-A   No.5   pp.633-641
発行日: 2001/05/01
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: 論文
専門分野: 情報セキュリティ基礎
キーワード: 
既約多項式,  Cardanoの公式,  べき乗剰余,  べき乗剰余記号,  だ円曲線暗号,  

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




あらまし: 
有限体 GF(P) 上のだ円曲線 E(x,y)x3+ax+b-y2=0 を暗号に用いる場合,標数 P が非常に大きく,x に関する3次多項式 E(x,0) は既約であることが要請される.既約判定法として逐次代入法が一般的であるが,この方法は,P が大きい場合非現実的である.そこで本論文では,GF(P) 上の3次多項式 f(x) の高速既約判定として,計算量が log P に比例するアルゴリズムを提案する.3次多項式は,既約であるか,三つの1次既約多項式の積か,それとも1次と2次の二つの既約多項式の積であるか,のいずれかである.本判定法ではまず,Stickelbergerの定理を適用し,f(x) の判別式 D(f) が GF(P) で平方非剰余なら非既約となることを示す.平方剰余なら判別ができないため,次に3次多項式の根に関するCardanoの定理を有限体上の場合に適用し,1の原始立方根ωと補助2次多項式の零点 t1, t2 の立方根 t11/3, t21/3 を用いて f(x) の零点を表現する.f(x) の零点が存在する拡大体を,ωと t11/3, t21/3 の存在する拡大体を綿密に調べることにより決定し,拡大次数が3である場合のみ既約と判定する.この判定には高速べき指数演算法が適用できるため,高速な実装が可能である.