Fp上不可约与本原多项式的高效确定算法

对于一大类整数n(n为素数乘于素数或1的积),分别给出有限域Fp上n次多项式是不可约多项式与本原多项式的一个充要条件,该条件可通过O(n3)次Fp上乘法加以验证,易于硬件实现.提出可约多项式一个充分条件,借此减少验证时间,并得到用O(n4)次Fp上乘法确定一个n次不可约多项式及一个n次本原多项式的高效算法.对于ECC中构造Fnp上椭圆曲线、序列密码中构造LFSR,有重要的应用价值.

Highly Efficient Deriving Calculation Method of Irreducible Polynomial and Primitive Polynomial Over Fp

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.