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 F_q in time poly (n, log q) (with n log q bits of advice). This has applications in pseudorandomness, and answers an open question of Alon, Goldreich, Hastad and Peralta.
展开▼
机译：我们研究了索引项链的问题，并给出了解决该问题的第一个多项式时间算法。具体来说，我们在{1，...，| N |}与有限字母Σ上长度为n的所有项链的集合N之间给出一个可乘的可计算双射数（n，log |Σ||）。我们的主要应用是在时间poly（n，log q）中给出所有有限域F_q上阶次为n的所有不可约多项式的显式索引（建议使用n log q位）。这在伪随机性中有应用，并回答了Alon，Goldreich，Hastad和Peralta的公开问题。
展开▼
