Неприводимый полином в поле F3

[Bolopak]

Как бы найти такой неприводимый в поле $F_3$ полином третьей степени, чтобы его корень являлся образующей в группе $F^*_{3^3}$ ?
Среди неприводимых в $F_3$ полиномов мне удалось найти два:
$x^3+x^2+2$ и $x^3+x^2+x+2$
Как я понимаю, чтобы корень полинома был образующей в $F^*_{3^3}$ достаточно чтобы
$a^{\frac{p-1}{2}}=-1(mod p)$ и вроде как такое число должно быть наименьшим.
$p=3^3=27$
В случае с $f(x)=x^3+x^2+x+2$ начинаю вычислять следующим образом:
$t^3+t^2+t+2=0$
$t^3=-t^2-t-2$
$t^4=t\cdot t^3=2-t$
и так далее (все коэффициенты привожу по модулю 3)
в итоге дохожу до $t^{13}=t\cdot t^{12}=t\cdot (t^2+t+1)=-t^2-t-2+t^2+t = -2$ а должно было быть -1 (если бы корень являлся образующей, так как $a^{\frac{p-1}{2}}=a^{13}$)

Может, есть другие способы или я что-то неправильно делаю?

[Xaositect]

2=-1

[vlad239]

Могу предложить такой способ. Все корни $x^{27}-x$ образуют Ваше поле. В нем корни $x^{13}-1$ не годятся потому что уже в 13 степени дают единицу. Кроме того не годится $-1$ и $0$. Остается многочлен $\frac{x^{13}+1}{x+1}$. Он раскладывается на 4 множителя третьей степени. Все они Вам подойдут.

Влад.

[mkot]

vlad239 в сообщении #218522 писал(а):

Могу предложить такой способ. Все корни $x^{27}-x$ образуют Ваше поле. В нем корни $x^{13}-1$ не годятся потому что уже в 13 степени дают единицу. Кроме того не годится $-1$ и $0$. Остается многочлен $\frac{x^{13}+1}{x+1}$.

То же самое можно получить, сославшись на круговые многочлены и поля деления круга, а именно, легко замечается, что искомый многочлен берётся из разложения кругового многочлена $Q_{3^3-1}$.
Но $Q_{3^3-1}(x) = Q_{26}(x) = Q_{2\cdot 13}(x) = Q_{13}(-x) = \frac{(-x)^{13} - 1}{-x - 1} = \frac{x^{13}+1}{x+1}$.
См. Конечные поля Лидла, Нидеррайтера.

[Bolopak]

Xaositect в сообщении #218518 писал(а):

2=-1

Это была опечатка.. там -2

-- Вс май 31, 2009 16:12:28 --

vlad239 в сообщении #218522 писал(а):

Остается многочлен $\frac{x^{13}+1}{x+1}$. Он раскладывается на 4 множителя третьей степени. Все они Вам подойдут.

Не совсем понятно как он раскладывается на 4 множителя третьей степени. У меня получилось
$\frac{x^{13}+1}{x+1}=x^{12}-x^{11}+x^{10}-x^9+x^8-x^7+x^6-x^5+x^4-x^3+x^2-x+1$
Вот кстати еще один неприводимый над полем $F_3$ многочлен $f(x)=x^3-x+1$
но и его корень не является образующей в $F_{3^3}^*$

[vlad239]

Выпишите ВСЕ неприводимые над $F_3$. Их 8 штук. И поделите этот на них на все.

Влад.

[Schraube]

Вариант.
С помощью какого-нибудь найденного неприводимого полинома постройте поле из 27 элементов.
Найдите (1) перебором элемент порядка 26 и (2) найдите его минимальный многочлен.
п.(1) - быстро, но как повезет.
п. (2) - быстро (работает автоморфизм Фробениуса и теорема Виета).

[Bolopak]

vlad239 в сообщении #218571 писал(а):

Выпишите ВСЕ неприводимые над $F_3$. Их 8 штук. И поделите этот на них на все.

Влад.

Вы меня еще больше запутали. У меня этих неприводимых третьей степени 9 штук получилось:
$x^3+x^2+x+2$
$x^3+x^2+2$
$x^3-x+1$
$x^3-x+2$
$x^3-x^2+1$
$-x^3-x^2+1$
$x^3-x-1$
$x^3-x-2$
$x^3-x^2-2$

[vlad239]

Bolopak в сообщении #218595 писал(а):

Вы меня еще больше запутали. У меня этих неприводимых третьей степени 9 штук получилось:
$x^3+x^2+x+2$
$x^3+x^2+2$
$x^3-x+1$
$x^3-x+2$
$x^3-x^2+1$
$-x^3-x^2+1$
$x^3-x-1$
$x^3-x-2$
$x^3-x^2-2$

Третий совпадает с восьмым, а четвертый с седьмым. Кроме того, второй с шестым.

Вот Вам правильный список (если я не обсчитался):

$x^3+2x+1$
$x^3+2x+2$
$x^3+x^2+2$
$x^3+x^2+x+2$
$x^3+x^2+2x+1$
$x^3+2x^2+2$
$x^3+2x^2+x+1$
$x^3+2x^2+2x+2$

Влад.

[Schraube]

третий и четвертый совпадают с седьмым и восьмым соответственно. т.к. по модулю три
(-1) =2, (-2) = 1.

[mkot]

vlad239 в сообщении #218599 писал(а):

Вот Вам правильный список (если я не обсчитался):
$x^3+2x+1$
$x^3+2x+2$
$x^3+x^2+2$
$x^3+x^2+x+2$
$x^3+x^2+2x+1$
$x^3+2x^2+2$
$x^3+2x^2+x+1$
$x^3+2x^2+2x+2$

$x^3 + 2x^2 + 2 = (x+1)(x^2+x+2)$.

[Bolopak]

mkot писал(а):

в сообщении #218610
$x^3 + 2x^2 + 2 = (x+1)(x^2+x+2)$.

тогда $x^3 + 2x^2 + 1 $

кстати, а почему таких полиномов 8 штук только?

[vlad239]

Потому что в поле $F_{27}$ 27 элементов. Три из них являются корнями многочленов первой степени, а остальные - многочленов третьей, каждый многочлен обслуживает по три корня. Итого $\frac{27-3}{3}=8$.

Влад.

[Bolopak]

vlad239 в сообщении #218619 писал(а):

Потому что в поле $F_{27}$ 27 элементов. Три из них являются корнями многочленов первой степени, а остальные - многочленов третьей, каждый многочлен обслуживает по три корня. Итого $\frac{27-3}{3}=8$.

Вы ранее говорили, что надо полином $\frac{x^{13}+1}{x+1}$ поделить на все неприводимые полиномы. Не понимаю, вот поделю, получу какие то остатки, только для чего? Мне нужно найти полином, корень которого является образующей в $F^*_{3^3}$ и при этом неприводимый в $F_3$ (чтобы потом построить расширение)

[vlad239]

Еще раз. На 4 из них он поделится без остатка. Любой из них Вам сгодится.

Я могу даже сказать на какие.
$(x^3+x^2+2x+1)(x^3+2x+1)(x^3+2x^2+1)(x^3+2x^2+x+1)$

Влад.