判定有限域上不可约多项式及本原多项式的一种高效算法

An Efficient and Deterministic Algorithm to Determine Irreducible and Primitive Polynomials over Finite Fields

提出了一个判定有限域上任一多项式是否为不可约多项式、本原多项式的高效的确定性算法。分析了多项式次数与其不可约因式之间的内在联系,给出了有限域上任意n次多项式是否为不可约多项式、本原多项式的一个充要条件。通过利用欧几里得算法,该判定仅需做O((log2n)n3)次域上乘法,属于多项式时间,易于硬件实现。为扩频通信与序列密码寻找和利用不可约多项式构造线性反馈移位寄存器提供了一种有效算法。

An efficient and deterministic method is proposed to determine whether a polynomial over finite fields is irreducible （primitive） or not. The correlation between the degree of the polynomial and its irreducible factors is analyzed, and then a sufficient and necessary condition on judging whether a polynomial of arbitrary degree n over finite fields is irreducible （primitive） or not is presented. By applying the Euclidean Algorithm, this judgment can be verified with 0（（log2n） n^3） muhiplieative operations over finite fields. The proposed algorithm is accomplished in polynomial time and easy to be implemented on hardware. And it is an efficient method for construction of the Linear Feedback Shift Register for spread communication and the stream cipher to find and use irreducible polynomials.