Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields

We study the problem of indexing necklaces, and give the first polynomial time algorithm for this problem. Specifically, we give a poly(n, log vertical bar Sigma vertical bar)-time computable bijection between {1,..., vertical bar N vertical bar} and the set N of all necklaces of length n over a finite alphabet Sigma. Our main application is to give an explicit indexing of all irreducible polynomials of degree n over the finite field F-q in time poly(n, log q) (with n log q bits of advice). This has applications in pseudorandomness, and answers an open question of Alon, Goldreich, Haastad and Peralta [2].