pdf icon
Volume 12 (2016) Article 7 pp. 1-27
Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields
Received: April 2, 2015
Revised: March 6, 2016
Published: August 13, 2016
Download article from ToC site:
[PDF (323K)] [PS (1739K)] [Source ZIP]
Misc.:
[About the Authors] [HTML Bibliography] [BibTeX]
Keywords: indexing algorithms, necklaces, irreducible polynomials, explicit constructions
Categories: algorithms, enumeration, necklaces, polynomials - univariate, irreducible polynomials, explicit construction
ACM Classification: F.2.1, G.2.1, I.1.2
AMS Classification: 11T06, 68R15, 68W40

Abstract: [Plain Text Version]

$ \newcommand{\poly}{\mathsf{poly}} \newcommand{\F}{\mathbb{F}} $

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.