Enumeration of special sets of polynomials over finite fields (Q1290925): Difference between revisions

The author determines the number of square-free self-reciprocal polynomials (palindromes) of degree \(d\) over the finite field \(\mathbb{F}_q\). She also estimates the number of polynomials of degree \(d\) for which \(\gcd(f,\hat{f})=1\) or \(\gcd(f,f^\#)=1\), respectively, where \(\hat{f}\) is the monic reciprocal of \(f\) and \(f^\#\) the Frobenius conjugate polynomial of \(f\). As a consequence she shows that for large \(q\), the probability that \(\gcd(f,\hat{f})\) or \(\gcd(f,f^\#)\) is nontrivial is very small and a prefactorization of \(f\) by determining \(\gcd(f,\hat{f})\) or \(\gcd(f,f^\#)\) is inefficient.