Revised: March 6, 2016

Published: August 13, 2016

**Keywords:**indexing algorithms, necklaces, irreducible polynomials, explicit constructions

**Categories:**algorithms, enumeration, necklaces, polynomials, irreducible polynomials, explicit construction

**ACM Classification:**F.2.1, G.2.1, I.1.2

**AMS Classification:**11T06, 68R15, 68W40

**Abstract:**
[Plain Text Version]

We study the problem of *indexing* irreducible polynomials over
finite fields, and give the first efficient algorithm for this problem.
Specifically, we show the existence of $\poly(n, \log q)$-size
circuits that compute a bijection between $\{1, \ldots, |S|\}$ and the set
$S$ of all irreducible, monic, univariate polynomials of degree $n$ over
a finite field $\F_q$.
This has applications to pseudorandomness, and answers
an open question of Alon, Goldreich, Håstad, and
Peralta (1992).

Our approach uses a connection between irreducible polynomials and necklaces (equivalence classes of strings under cyclic rotation). Along the way, we give the first efficient algorithm for indexing necklaces of a given length over a given alphabet, which may be of independent interest.

A conference version of this paper appeared in the Proceedings of the 41st ICALP, 2014.