Highly Efficient Deriving Calculation Method of Irreducible Polynomial and Primitive Polynomial Over F-p
Zehui Wang · Acta Scientiarum Naturalium Universitatis Sunyatseni · 2004
For a wide range of integers n (n is the product of prime number and prime number or 1),a necessary and sufficient condition is given for a polynomial of degree n over the finite field F_p being an irreducible polynomial or primitive polynomial. Such kind of condition can be verified by multiplication of O(n~3) over F_p and easy to be realized by hardware.A sufficient condition of reducible polynomial is proposed to cut down the validating time.A highly efficient calculation method is derived via confirming the irreducible polynomial of degree n or primitive polynomial of degree n using multiplication of O(n~3) over F_p.The result has important application in constructing the elliptic curve of the Elliptic Curve Cryptosystem over F~n_p, and in constructing the Linear Feedback Shift Register of the stream cipher.