Theory of Computing ------------------- Title : Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields Authors : Swastik Kopparty, Mrinal Kumar, and Michael Saks Volume : 12 Number : 7 Pages : 1-27 URL : https://theoryofcomputing.org/articles/v012a007 Abstract -------- 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, Hastad 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.