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.