Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-047 | 2nd April 2015 16:16

Efficient indexing of necklaces and irreducible polynomials over finite fields


Authors: Swastik Kopparty, Mrinal Kumar, Michael Saks
Publication: 3rd April 2015 22:51
Downloads: 1909


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, ... , |S|} and the set S of all irreducible, monic, univariate polynomials of degree n over a finite field F_q. This has applications in pseudorandomness, and answers an open question of Alon, Goldreich, H{\aa}stad and Peralta[AGHP].

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.

ISSN 1433-8092 | Imprint