Irreducibility testing

Fact. A polynomial $f\in F_q[x]$ of degree $n\geq 1$ is irreducible if and only if
1) $x^{q^n}\equiv x \mod f$ and
2) $\gcd (x^{q^{n/t}}-x, f)=1$ for all prime divisors $t$ of $n$.

From this fact one can get the Rabin's irreducibility test:

Irreducibility test (Rabin)
Input and Output  On input we have $f\in F_q[x]$ of degree $n$. On output test gives an answer "reducible" or "irreducible".
Step 1.  Compute $a=x^{q^n} \mathrm{rem} f$. If $a\neq x$ return "reducible".
Step 2. Find prime divisors of $n$.
Step 3. For all prime divisors $t$ of $n$ compute $b=x^{q^{n/t}} \mathrm{rem} f$. If $\gcd(b-x, f)\neq 1$ return "reducible".
Step 4. Return "irreducible".

Another possibility is to use distinct-degree factorisation to test irreducibility.

Irreducubility test (ddf)
Step 1.  Check if $f$ is squarefree (by computing it's derivative). If not, return "reducible".
Step 2. Build ddf $f^{[1]},...,f^{[n]}$ for $f$.
Step 3. If $\deg f^{[n]}=n$ return "irreducible", else return "reducible".

Since fmpz_mod_poly doesn't have fast gcd computation and fast modular composition implemented, the ddf-based algorithm turns out to be faster for it.