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 : http://www.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.