TY - GEN

T1 - Efficient indexing of necklaces and irreducible polynomials over finite fields

AU - Kopparty, Swastik

AU - Kumar, Mrinal

AU - Saks, Michael

PY - 2014

Y1 - 2014

N2 - We study the problem of indexing necklaces, and give the first polynomial time algorithm for this problem. Specifically, we give a poly(n, log|∑|)-time computable bijection between {1,...,|N|} and the set N of all necklaces of length n over a finite alphabet ∑. Our main application is to give an explicit indexing of all irreducible polynomials of degree n over the finite field double-struck Fq in time poly(n, logq) (with n logq bits of advice). This has applications in pseudorandomness, and answers an open question of Alon, Goldreich, Håstad and Peralta [2].

AB - We study the problem of indexing necklaces, and give the first polynomial time algorithm for this problem. Specifically, we give a poly(n, log|∑|)-time computable bijection between {1,...,|N|} and the set N of all necklaces of length n over a finite alphabet ∑. Our main application is to give an explicit indexing of all irreducible polynomials of degree n over the finite field double-struck Fq in time poly(n, logq) (with n logq bits of advice). This has applications in pseudorandomness, and answers an open question of Alon, Goldreich, Håstad and Peralta [2].

UR - http://www.scopus.com/inward/record.url?scp=84904216202&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84904216202&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-43948-7_60

DO - 10.1007/978-3-662-43948-7_60

M3 - Conference contribution

AN - SCOPUS:84904216202

SN - 9783662439470

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 726

EP - 737

BT - Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings

PB - Springer Verlag

T2 - 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014

Y2 - 8 July 2014 through 11 July 2014

ER -