Fast construction of irreducible polynomials over finite fields

Victor Shoup

Research output: Contribution to journalArticlepeer-review


The main result of this paper a new algorithm for constructing an irreducible polynomial of specified degree n over a finite field Fq . The algorithm is probabilistic, and is asymptotically faster than previously known algorithms for this problem. It uses an expected number of O-(n2 + n log q) operations in Fq, where the "soft-O" O- indicates an implicit factor of (log n)O(1). In addition, two new polynomial irreducibility tests are described.

Original languageEnglish (US)
Pages (from-to)371-391
Number of pages21
JournalJournal of Symbolic Computation
Issue number5
StatePublished - 1994

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Computational Mathematics


Dive into the research topics of 'Fast construction of irreducible polynomials over finite fields'. Together they form a unique fingerprint.

Cite this