An Efficient and Deterministic Algorithm to Determine Irreducible and Primitive Polynomials over Finite Fields
Xin Wang, Xinmei Wang, Baodian Wei · Acta Scientiarum Naturalium Universitatis Sunyatseni · 2009
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 O((log2n)n3) multiplicative 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.