New algorithms for finding irreducible polynomials over finite fields
New algorithms for finding irreducible polynomials over finite fields
复制标题
DOI：
10.1109/sfcs.1988.21944
复制
发表时间：
1988-10
期刊：
影响因子：
--
通讯作者：
V. Shoup
中科院分区：
文献类型：
--
作者：
V. Shoup
给出了求有限域上指定次数的不可约多项式的一个算法。它是确定性的，对于小特征的田块以多项式时间运行。证明了有限域K上寻找指定次数的不可约多项式的问题是确定性多项式时间可约为K>的素域上多项式的因式分解问题；
An algorithm is presented for finding an irreducible polynomial of specified degree over a finite field. It is deterministic and runs in polynomial time for fields of small characteristics. A proof is given of the stronger result, that the problem of finding irreducible polynomials of specified degree over a finite field K is deterministic-polynomial-time reducible to the problem of factoring polynomials over the prime field of K.>