Найти и разложить неприводимый многочлен в поле расширения

[gagauz805]

Задача выглядит так :
$f(x)=x^4+x+e$ многочлен над полем $P=\mathbb{Z}_2$ и $P'=P(\alpha)$ - расширение поля $P$ корнем $\alpha$ многочлена $f (x)$. Выписать все неприводимые над $P$ многочлены, имеющие корень в $P'$ , и разложить их на линейные множители в поле $P'$ .

$f(x)$ не приводим в $P=\mathbb{Z}_2$ и $deg\ f(x)=4$ Значит $P'$ является полем разложения многочленов $g(x) \in P[x]$ таких, что $g(x)$ неприводимы над $P=\mathbb{Z}_2$ и $deg\ g(x) \in \{1,2,4\}$.
Рассмотрим сначала многочлены 4 степени: $deg\ g(x) = 4$, тогда $g(x)$ имеет вид $g(x)=x^4 + ax^3 + bx^2 + cx + d$; $a,b,c,d \in P=\mathbb{Z}_2$
Его производная $g'(x)=4x^3+3ax^2+2bx+c = ax^2+c$ взаимно проста с $g(x)$ в $P[x]$ (т.к. $g(x)$ не приводим в $P[x]$), а в кольце многочленов $P'[x]$ многочлены $g(x)$ и $g'(x)$ имеют НОД, степень которого не меньше единицы.
Но вот как найти этот НОД в $P'[x]$ я не понимаю, т.к. когда делю столбиком $g(x)$ на $g'(x)$ я понятное дело получаю частное и остаток с коэффициентами из $P=\mathbb{Z}_2$

[nnosipov]

gagauz805 в сообщении #1483437 писал(а):

Выписать все неприводимые над $P$ многочлены

Имеются в виду только нормированные неприводимые многочлены (со старшим коэффициентом единица)?

[gagauz805]

nnosipov в сообщении #1483441 писал(а):

gagauz805 в сообщении #1483437 писал(а):

Выписать все неприводимые над $P$ многочлены

Имеются в виду только нормированные неприводимые многочлены (со старшим коэффициентом единица)?

Да

[nnosipov]

gagauz805 в сообщении #1483437 писал(а):

а в кольце многочленов $P'[x]$ многочлены $g(x)$ и $g'(x)$ имеют НОД, степень которого не меньше единицы

Это ерунда, НОД один и тот же.

Вообще, Вы начали не с того конца. Танцевать нужно от корней искомых многочленов (тем более что многочлены все равно нужно разлагать на линейные множители). Для начала выпишите все корни многочлена $x^4+x+1$. Один из них $\alpha$, а остальные каковы?

[gagauz805]

nnosipov в сообщении #1483447 писал(а):

gagauz805 в сообщении #1483437 писал(а):

а в кольце многочленов $P'[x]$ многочлены $g(x)$ и $g'(x)$ имеют НОД, степень которого не меньше единицы

Это ерунда, НОД один и тот же.

Вообще, Вы начали не с того конца. Танцевать нужно от корней искомых многочленов (тем более что многочлены все равно нужно разлагать на линейные множители). Для начала выпишите все корни многочлена $x^4+x+1$. Один из них $\alpha$, а остальные каковы?

$\alpha$, $\alpha^2$, $\alpha^4$, $\alpha^8$

[nnosipov]

Правильно, но не совсем: последние два следует упростить. Как это сделать?

[gagauz805]

nnosipov в сообщении #1483457 писал(а):

Правильно, но не совсем: последние два следует упростить. Как это сделать?

Получется у нас из того что $f(\alpha)=0$ следует, что $\alpha^4=\alpha +1$ и $\alpha^8= \alpha^2 + 1$.
И $f(x)=(x-\alpha)(x-(\alpha + 1))(x-(\alpha^2 + 1))$. Остальные неприводимые многочлены надо найти из разной комбинации произведений неприводимых многочленов из разложения $f(x)$?

[nnosipov]

gagauz805 в сообщении #1483458 писал(а):

Остальные неприводимые многочлены надо найти из разной комбинации произведений неприводимых многочленов из разложения $f(x)$?

Нет. Многочлен $f(x)$ с его линейными множителями (кстати, там пропущен $x-\alpha^2$) --- это отрезанный ломоть. Остальные неприводимые многочлены делаются из других линейных множителей. Как их сделать?

[gagauz805]

Я кажется понял.
Так как степень остальных неприводимых многочленов должна быть либо 2, либо 4. Значит и количество линейных множителей будет либо 2, либо 4.
Если рассматривать неприводимые многочлены 2 степени, то разложение будет выглядеть так: $(x-\alpha^i)(x-\alpha^j)=x^2+(\alpha^i+\alpha^j)x+\alpha^i\alpha^j$, где $i+j=15$, чтобы произведение $\alpha^i \cdot \alpha^j$ было равным $\alpha^{15}=1$, а сумма $\alpha^i+\alpha^j$ равнялась либо 0, либо 1. Получим что под эти критерии подходят только 2 элемента из $P'$: $\alpha^{10}=\alpha^2+\alpha+1$ и $\alpha^5=\alpha^2+\alpha$.
Если рассматривать неприводимые многочлены 4 степени, то разложение аналогично будет выглядеть так: $(x-\alpha^i)(x-\alpha^j)(x-\alpha^k)(x-\alpha^t)$, где $i+j+k+t=15$, а сумма $\alpha^i+\alpha^j+\alpha^k+\alpha^t$ равнялась либо 0, либо 1. Чтобы меньше перебирать можно воспользоваться тем, что все корни неприводимого многочлена в поле разложения имеют один и тот же порядок. Тогда мы сразу можем понять что
$\alpha^3$;$(Ord\ \alpha^3 = 5)$,
$\alpha^5=\alpha^2+\alpha$ ;$(Ord\ \alpha^5 = 3)$,
$\alpha^6=\alpha^3+\alpha^2$; $(Ord\ \alpha^6 = 5)$,
$\alpha^9 = \alpha^3 + \alpha$; $(Ord\ \alpha^9 = 5)$,
$\alpha^{10} = \alpha^2 + \alpha + 1$;$(Ord\ \alpha^{10} = 3)$ и
$\alpha^{12}=\alpha^3+\alpha^2+\alpha+1$;$(Ord\ \alpha^{12} = 4)$ не будут являться корнями неприводимого многочлена 4 степени.
И под последние условия удовлетворяет только четверка $(\alpha, \alpha^2, \alpha^4, \alpha^8) = (\alpha, \alpha^2, \alpha + 1, \alpha^2 + 1)$
Значит поле $P'$ является полем разложения 2 многочленов:
$f(x)=x^4+x+1=(x+\alpha)(x+\alpha^2)(x+\alpha+1)(x+\alpha^2+1)$
$g(x)=x^2+x+1=(x+\alpha^2+\alpha+1)(x+\alpha^2+\alpha)$

[nnosipov]

gagauz805 в сообщении #1483494 писал(а):

Я кажется понял.

Боюсь, не совсем.

Во-первых, Вы считаете, что степени $\alpha$ вместе с нулем дают все элементы поля $P'$. В данном случае это правда, но только потому, что $\alpha$ --- корень неприводимого многочлена $f(x)=x^4+x+1$ (неприводимые многочлены с таким свойством называют примитивными). Если бы на месте $f(x)$ был другой неприводимый многочлен (а именно, $x^4+x^3+x^2+x+1$), такое утверждение уже было бы неверным (убедитесь в этом).

Во-вторых, Вы не нашли все неприводимые многочлены 4-й степени, имеющие корни в $P'$. Вот это:

gagauz805 в сообщении #1483494 писал(а):

Тогда мы сразу можем понять что
$\alpha^3$;$(Ord\ \alpha^3 = 5)$,
$\alpha^5=\alpha^2+\alpha$ ;$(Ord\ \alpha^5 = 3)$,
$\alpha^6=\alpha^3+\alpha^2$; $(Ord\ \alpha^6 = 5)$,
$\alpha^9 = \alpha^3 + \alpha$; $(Ord\ \alpha^9 = 5)$,
$\alpha^{10} = \alpha^2 + \alpha + 1$;$(Ord\ \alpha^{10} = 3)$ и
$\alpha^{12}=\alpha^3+\alpha^2+\alpha+1$;$(Ord\ \alpha^{12} = 4)$ не будут являться корнями неприводимого многочлена 4 степени.

неверно. На самом деле, помимо самого $f(x)$, есть еще два неприводимых многочлена 4-й степени с корнями в $P'$. Естественно, их наборы корней не пересекаются с набором $\{\alpha,\alpha+1,\alpha^2,\alpha^2+1\}$ корней $f(x)$ и набором $\{\alpha^2+\alpha,\alpha^2+\alpha+1\}$ корней неприводимого многочлена $x^2+x+1$ 2-й степени. Спрашивается, каковы же их корни? И, кстати, почему Вы считаете, что порядок $\alpha^{12}$ равен 4? (Мне думается, что из-за этой мелкой ошибки Вы и просмотрели один неприводимый многочлен 4-й степени, хотя все необходимые вычисления проделали.)

[gagauz805]

nnosipov в сообщении #1483516 писал(а):

Во-первых, Вы считаете, что степени $\alpha$ вместе с нулем дают все элементы поля $P'$. В данном случае это правда, но только потому, что $\alpha$ --- корень неприводимого многочлена $f(x)=x^4+x+1$ (неприводимые многочлены с таким свойством называют примитивными). Если бы на месте $f(x)$ был другой неприводимый многочлен (а именно, $x^4+x^3+x^2+x+1$), такое утверждение уже было бы неверным (убедитесь в этом).

Спасибо, буду знать. Проверил, порядок корней такого многочлена равен 5. И кроме степеней корня этого многочлена и нуля действительно должны быть еще элементы, чтобы поле состояло из $p^k$ ($k \in N$ p - простое) элементов. Я правильно понимаю что неприводимый многочлен является примитивным, если порядок его корня равен $(p^k)^n-1$ ($n = deg\ f(x)$), а если порядок не равен, а только делит это число, то он не примитивен?

nnosipov в сообщении #1483516 писал(а):

И, кстати, почему Вы считаете, что порядок $\alpha^{12}$ равен 4?

Арифметическая ошибка, да действительно $Ord\ \alpha^{12} = 5 \ne 4$, и если мы проверим то корни с порядком равным 5 нам тоже подходят, многочлен $g_2(x)=$$x^4+x^3+x^2+x+1=$ раскладывается на линейные множители $g_2(x)=(x+\alpha^3)(x+\alpha^6)(x+\alpha^9)(x+\alpha^{12})=$$(x+\alpha^3)(x+\alpha^3+\alpha^2)(x+\alpha^3+\alpha)(x+\alpha^3+\alpha^2+\alpha+1)$
И так же я не заметил что подходят оставшиеся 4 корня $\{\alpha^7, \alpha^{11}, \alpha^{13},\alpha^{14}\}=$$\{\alpha^3+\alpha+1,\ \alpha^3 + \alpha^2 + \alpha,\ \alpha^3+\alpha^2+1,\ \alpha^3+1\}$ $g_3(x)=x^4+x^3+1=$$(x +\alpha^3+\alpha+1)(x + \alpha^3 + \alpha^2 + \alpha)(x+ \alpha^3+\alpha^2+1)(x+ \alpha^3+1)$.

И еще у меня это условие:

gagauz805 в сообщении #1483494 писал(а):

где $i+j+k+t=15$, а сумма $\alpha^i+\alpha^j+\alpha^k+\alpha^t$ равнялась либо 0, либо 1

является необходимым, но не является достаточным.

Спасибо вам большое!

[nnosipov]

gagauz805 в сообщении #1483547 писал(а):

Я правильно понимаю что неприводимый многочлен является примитивным, если порядок его корня равен $(p^k)^n-1$ ($n = deg\ f(x)$), а если порядок не равен, а только делит это число, то он не примитивен?

Да, так и есть.

Ну, вот теперь видно, что задача решена.