Неприводимые многочлены над полем GF(3)

[Everest]

Очень прошу дать мне совет насчет задачки:
Составить таблицу неприводимых полиномов, до третьей степени включительно, над полем $GF(3)$.

Вот, изложу свои мысли: Представителями классов вычетов по модулю 3 могут быть как числа $0, 1, 2$, так и числа $-1, 0, 1$. Разницы нет, я рассмотрю вариант для чисел $-1, 0, 1.$. Всякий многочлен первой степени неприводим. Следовательно, многочлены $x, x+1, x-1$ неприводимы. А вот дальше я просто подбором нашел оставшиеся: $x^{2}+1, x^{2}+x-1, x^{2}-x-1, x^{3}-x+1, x^{3}+x^{2}-x+1, x^{3}-x^{2}+1$, $x^{3}-x^{2}+x+1, x^{3}-x-1, x^{3}-x^{2}-x-1, x^{3}+x^{2}-1, x^{3}+x^{2}+x-1$
А можно это было найти не подбором, существует ли какой-нибудь способ. Подскажите, пожалуйста.

[Brukvalub]

Everest в сообщении #168737 писал(а):

А можно это было найти не подбором, существует ли какой-нибудь способ. Подскажите, пожалуйста.

Да, такой способ есть. Только этот способ не очень прост. Например, в первом томе двухтомника Лидл Р., Нидеррайтер Г. — Конечные поля (том 1, 2) вопросу построения неприводимых нормированных многочленов над конечными полями посвящен параграф 3 из главы 3, который содержит 14 стр. Так что в двух словах этот алгоритм изложить не удастся

[Everest]

Спасибо, сейчас скачаю буду смотреть

[Yakov]

Известна формула

$$ X^{q^n} - X = \Pi f_d(X), $$

где произведение берётся по всем неприводимым многочленам степеней $d$, делящих $n$. Поэтому имеет смысл искать неприводимые многочлены заданной степени в этом разложении.