Name
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, logq)-size circuits that compute a bijection between {1, . . . , vertical bar S vertical bar} 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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.4086/toc.2016.v012a007 | THEORY OF COMPUTING |
Keywords | DocType | Volume |
indexing algorithms,necklaces,irreducible polynomials,explicit constructions | Journal | 12 |
Issue | ISSN | Citations |
1 | 1557-2862 | 0 |
PageRank | References | Authors |
0.34 | 6 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Swastik Kopparty | 1 | 384 | 32.89 |
| Mrinal Kumar 0001 | 2 | 64 | 9.94 |
| Michael Saks | 3 | 2595 | 302.11 |