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

摘要

有限体GF（P）上のだ円曲線E（x，y）≡x~3+αx+b-y~2＝0を暗号に用いる場合，標数Pが非常に大きく，xに関する3次多項式且（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の立方根(t_1)~(1/3)，(t_2)~(1/3)を用いてf（x）の零点を表現する．f（x）の零点が存在する拡大体を，ωと(t_1)~(1/3)，(t_2)~(1/3)の存在する拡大体を綿密に調べることにより決定し，拡大次数が3である場合のみ既約と判定する．この判定には高速べき指数演算法が適用できるため，高速な実装が可能である．