No label defined (Q4217871)

Let \(r\) and \(p\) be distinct primes. The paper under review deals with factoring the \(r\)th cyclotomic polynomial \(\phi_r\) over the prime field \(\mathbb F_p\). Using methods developed in the author's Ph.D. thesis, it can be shown that one can completely factor \(\phi_r\) over \(\mathbb F_p\) in time polynomial in \(r\) and \(\log p\) provided all of the traces of the primitive \(r^{\text{th}}\) roots of unity over \(\mathbb F_p\) are known or if the trace of one primitive \(r^{\text{th}}\) root of unity is known and is distinct from all the rest. In order to get some feeling for how likely it is for duplicate traces to occur, the author lists all 411 cases with \(r < p < 1000\) in which two different primitive \(r\)th roots of unity over \(\mathbb F_p\) have the same trace. The author points out this about 5.77 standard deviation is below the expected value if one assumed traces fell ``randomly'' in \(\mathbb F_p\). Another table similarly shows that zero appears as a trace less often than one would expect in a random distribution. For the entire collection see [Zbl 0899.00028].