Определяющий полином конечного поля

[NellyOhNell]

Добрый день, мне нужно было найти для поля $F_{81}$ неприводимый полином из $F_3[x]$, корень $t$ которого порождает группу $F^*_{81}$, а затем выписать все степени $t$ как полиномы от $t$ степени меньше 4.

Я взяла неприводимый полином $x^4+x+1$. Насколько я понимаю, $F^*_{81}$ будет содержать 81 полином меньше 4-ой степени... т.к. по модулю $x^4+x+1$.. И что же, мне искать все 81 степени $t$, все 81 полином? или можно это как-то короче сделать?

Спасибо.

[AV_77]

А вам обязательно самостоятельно этот многочлен найти нужно или можно воспользоваться готовыми таблицами примитивных многочленов?

[Joker_vD]

Не, я балдю: дано задание "выписать все 81 элементы поля как степени примитивного элемента". Вопрос: "А все 81 элемент надо выписывать?" Да, все 81.

Или у вас проблема найти примитивный многочлен? Ну можно брать многочлены четвертой степени и считать их порядки...

[NellyOhNell]

Да можно взять любой примитивный многочлен, только что-то мои мне не помогли)

когда я беру $t^4+t+1$ или $t^4+t+2$, то $t^{13}$ уже 1. С $t^4+t^2+2t+1$ - $t^{26}=1$. хотя вроде все эти три неприводимы... ну, нет вещественных корней. Или как надо выбирать?

[AV_77]

Это вы как-то неправильно считаете. В $\mathbb{F}_{81}$ не может выполняться равенство $t^{13} = 1$ для $t \neq 1$. А многочлен берите $x^4+x+2$.

[NellyOhNell]

Спасибо, а можно узнать почему именно этот?

[Xaositect]

Цитата:

хотя вроде все эти три неприводимы... ну, нет вещественных корней. Или как надо выбирать?

Во-первых, не всякий неприводимый многочлен примитивен.
Во-вторых, для проверки многочлена 4 степени на неприводимость недостаточно того, что у него нет корней.
В-третьих, вещественные корни уж точно никакого отношения к $\mathbb{F}_3$ не имеют.

[NellyOhNell]

Xaositect, спасибо, так может скажете, какой проверки на неприводимость достаточно?

[Joker_vD]

Достаточно взять неприводимый многочлен четвертой степени с порядком $80$.

[NellyOhNell]

То есть мне нужен полином 4й степени, который делит $x^{80}-1$ без остатка, так?

[Xaositect]

Для проверки на неприводимость достаточно того, что нет корней из $\mathbb{F}_3$ и еще многочлен не раскладывается в произведение двух квадратных.ти
Но вам надо примитивный многочлен. Примитивность - это значит, что $x^{p^n - 1} \equiv 1 (\mathrm{mod} f)$, а ни для какого делителя $p^n - 1$ это не верно. Примитивных многочленов достаточно много, так что обычно берут случайный многочлен и проверяют на неприводимость и примитивность.

[AV_77]

NellyOhNell в сообщении #579175 писал(а):

Спасибо, а можно узнать почему именно этот?

Подсмотрел в таблице примитивных многочленов.

[Joker_vD]

Как можно считать порядок многочлена? Пусть $f(x)$ — неприводимый, тогда $\operatorname{ord}(f)|q^{m}-1$, где $m$ — степень многочлена $f(x)$. Давайте разложим $q^{m}-1$ на множители: $q^{m}-1=\prod_{j=1}^s p_j^{r_j}$ и воспользуемся замечательным свойством:

$$p_j^{r^{j-k+1}}\big|\operatorname{ord}(f)\Longleftrightarrow x^{\frac{q^m-1}{p_j^k}}\not\equiv1\pmod{f(x)}.$$

В вашем конкретном случае вы $80=2^4\cdot5$; смотрите на табличку:

$$\begin{array}{c|c|c|c|c}x^{40} & x^{20} & x^{10} & x^{5} &x^{16}\\ \hline 2 & 4 & 8 & 16 & 5\end{array}$$

ищете остатки от деления указанных в верхней строке одночленов на $f(x)$ — если получилась не единица, значит, порядок делится на число под этим многочленом, если единица — порядок не делится. Сопоставляете, перемножаете, вуаля — вы получили $\operatorname{ord}(f)$!

[NellyOhNell]

теперь понятно... Большое спасибо!

[NellyOhNell]

Для тех, кого заинтересует задача: примитивным полиномом будет полином $x^4+2x+2$, а чтобы проверить, достаточно возвести корень в 40-ую степень и получить 2 (как элемент $F_3$)