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 -