scientific article; zbMATH DE number 1222354
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].
- Algebraic trace functions over the primes
- Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields
- An alternate construction of the Berlekamp subalgebra
- The trace of 2-primitive elements of finite fields
- scientific article; zbMATH DE number 5066354 (Why is no real title available?)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4217871)