ECCC-Report TR15-047https://eccc.weizmann.ac.il/report/2015/047Comments and Revisions published for TR15-047en-usFri, 03 Apr 2015 22:51:26 +0300
Paper TR15-047
| Efficient indexing of necklaces and irreducible polynomials over finite fields |
Mrinal Kumar,
Swastik Kopparty,
Michael Saks
https://eccc.weizmann.ac.il/report/2015/047We 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.
Fri, 03 Apr 2015 22:51:26 +0300https://eccc.weizmann.ac.il/report/2015/047