Analogue of Fermat's primality test for polynomials and irreducibility

Solution 1:

Part of the point of Fermat's primality test is that $n$ is prime if and only if $\mathbb{Z}/(n)$ is a field. When the latter is a field, its multiplicative group has order $n - 1$, so any representative from ${1,\dots,n-1}$ should have order dividing $n - 1$ mod $n$.

Analogously, a polynomial $f \in \mathbb{F}_q[x]$ ($q = p^n$) is irreducible if and only if the ring $\mathbb{F}_q[x]/(f)$ is a field. The latter has order $q^m$, with a unique set of representatives being given by the polynomials of degree strictly less than $m$ (thanks to the Euclidean algorithm). So if it's a field, then its multiplicative group has order $q^m - 1$, and the order of every element divides this value. (Notice that every nonzero constant polynomial has order $q-1 = |\mathbb{F}_q^*|$, which divides $q^m - 1$, so there would be no need to test these.)

Thus it seems to me that the best analogue for Fermat's primality test would be:

• Randomly choose a polynomial $a(x) \in \mathbb{F}_q[x]$ with $\deg(a)\in \{1,\dots,m-1\}$.
• If $a^{q^m-1} \not\equiv 1 \pmod{f}$, meaning $f \nmid (a^{q^m-1}-1)$, then $f$ is composite.

Solution 2:

Yes, over finite fields there is a polynomial irreducibility test that is an an efficient analog of the impractical Pocklington-Lehmer integer primality test (see also Section 3.4.3 and Section 8.3.1 of Henri Cohen's book A Course in Computational Algebraic Number Theory). Below is a description of one form of this algorithm, from this Wikipedia page.