Fast construction of irreducible polynomials over finite fields
Victor Shoup · 1993
The main result of this paper is a new algorithm for constructing an irreducible polynomial of specified degree n over a finite field F q . The algorithm is probabilistic, and is asymptotically faster than previously known algorithms for this problem. It uses an expected number of O~(n 2 + n log q) operations in F q , where the "soft-O" O~ indicates an implicit factor of (log n) O(1) . In addition, two new polynomial irreducibility tests are described. 1 Introduction 1.1 Statement of main result Let F q be a finite field with q elements, where q is a prime-power. A theorem due to Moore (1893) states that for every positive integer n, there exists a field extension F q n , unique up to isomorphism, with q n elements. Such extensions play an important role in coding theory (implementing error correcting codes), cryptography (implementing cryptosystems), and complexity theory (amplifying randomness). In this paper, we consider the algorithmic version of Moore's theorem: how to ...