New algorithms for finding irreducible polynomials over finite fields

摘要

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.