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

概要

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