Факторизация многочленов над конечными полями может быть решена за вероятное полиномиальное время с помощью рандомизированного алгоритма (который намного проще, чем факторизация целых чисел). Для фиксированного поля земли, такого как $\mathbb F_2$, это можно сделать детерминированным. Естественно, это позволяет проводить проверку на неприводимость за одинаковое время.
Если нас интересует просто тест на несводимость да/нет, есть небольшая экономия и алгоритм выглядит следующим образом. Обратите внимание, что мы можем вычислить $X^{2^k}-X\mod{f(X)}$ с $к$ повторные возведения в квадрат и вычитание и т.д. вычисления $\mathrm{НОД}(X^{2^k}-X,f(X))$ можно сделать за полиномиальное время $к$ и степень $ф(Х)$.
Шаг 1. Вычисляем $\mathrm{НОД}(X^{2^d}-X,f(X))$ куда $d=\mathrm{градус}f$. Если это не $ф(Х)$ тогда $f$ не является неприводимым, поскольку он либо имеет повторяющиеся корни, либо корни вне $\mathbb F_{2^d}$. Если это $ф(Х)$ переходим к шагу 2.
Шаг 2. Для каждого простого числа $p|d$ мы позволяем $d'=d/p$ и вычислить $\mathrm{НОД}(X^{2^{d'}}-X,f(X))$. Если это не 1, то $ф(Х)$ имеет корень в подполе $\mathbb F_{2^{d'}}$ и $ф(Х)$ не является неприводимым.
Если шаг 2 пройден для всех $p|d$ то все корни лежат в $\mathbb F_{2^d}$, а не в подполе, чтобы $ф(Х)$ является неприводимым.
