Factorizarea polinoamelor pe câmpuri finite poate fi rezolvată în timp polinomial probabil cu un algoritm randomizat (care este mult mai ușor decât factorizarea numerelor întregi). Pentru un câmp de pământ fix, cum ar fi $\mathbb F_2$, acest lucru poate fi făcut determinist. Desigur, acest lucru permite testarea ireductibilității în timp similar.
Dacă suntem doar interesați de testul de ireductibilitate da/nu, există câteva mici economii și algoritmul după cum urmează. Rețineți că putem calcula $X^{2^k}-X\mod{f(X)}$ cu $k$ pătrate repetate și o scădere și deci calcul $\mathrm{GCD}(X^{2^k}-X,f(X))$ se poate face în timp polinom în $k$ iar gradul de $f(X)$.
Pasul 1. Calculăm $\mathrm{GCD}(X^{2^d}-X,f(X))$ Unde $d=\mathrm{deg}f$. Dacă aceasta nu este $f(X)$ atunci $f$ nu este ireductibil deoarece are fie rădăcini repetate, fie rădăcini în exterior $\mathbb F_{2^d}$. Dacă este $f(X)$ trecem la pasul 2.
Pasul 2. Pentru fiecare prim $p|d$ noi lăsăm $d'=d/p$ și calculează $\mathrm{GCD}(X^{2^{d'}}-X,f(X))$. Dacă acesta nu este 1, atunci $f(X)$ are o rădăcină în subcâmp $\mathbb F_{2^{d'}}$ și $f(X)$ nu este ireductibil.
Dacă pasul 2 trece pentru toți $p|d$ apoi se află toate rădăcinile $\mathbb F_{2^d}$, dar nu într-un subdomeniu astfel încât $f(X)$ este ireductibil.
