Nhân tử hóa của đa thức trên các trường hữu hạn có thể được giải quyết trong thời gian đa thức có thể xảy ra bằng một thuật toán ngẫu nhiên (dễ dàng hơn nhiều so với phân tích các số nguyên). Đối với một trường mặt đất cố định như $\mathbb F_2$, điều này có thể được thực hiện xác định. Đương nhiên, điều này cho phép kiểm tra tính bất khả quy trong thời gian tương tự.
Nếu chúng ta chỉ quan tâm đến phép thử có/không về tính bất khả quy, thì có một số khoản tiết kiệm nhỏ và thuật toán như sau. Lưu ý rằng chúng ta có thể tính toán $X^{2^k}-X\mod{f(X)}$ với $k$ bình phương lặp đi lặp lại và một phép trừ và do đó tính toán $\mathrm{GCD}(X^{2^k}-X,f(X))$ có thể được thực hiện trong đa thức thời gian trong $k$ và mức độ của $f(X)$.
Bước 1. Chúng tôi tính toán $\mathrm{GCD}(X^{2^d}-X,f(X))$ ở đâu $d=\mathrm{deg}f$. Nếu đây không phải là $f(X)$ sau đó $f$ không phải là bất khả quy vì nó có nghiệm lặp lại hoặc nghiệm ngoài $\mathbb F_{2^d}$. Nếu nó là $f(X)$ chúng ta tiến hành bước 2.
Bước 2. Với mỗi số nguyên tố $p|d$ chúng tôi để $d'=d/p$ và tính toán $\mathrm{GCD}(X^{2^{d'}}-X,f(X))$. Nếu đây không phải là 1 thì $f(X)$ có gốc trong trường con $\mathbb F_{2^{d'}}$ và $f(X)$ không phải là không thể giảm được.
Nếu bước 2 vượt qua cho tất cả $p|d$ sau đó tất cả các gốc nằm trong $\mathbb F_{2^d}$, nhưng không phải trong một trường con để $f(X)$ là không thể giảm được.
