Неприводимые над $\mathbb{F}_2$

[xmaister]

Привет! Можно ли явно указать неприводимый многолчен над $\mathbb{F}_2$ произвольной степени $n$?

[VladimirKr]

Могу сказать, что можно для заданного многочлена за время $O(n^2)$ проверить неприводимость (Критерий Батлера). Ну или построить за среднее время $O(n^2)$ пребирая многочлены подряд. Однако на практике, помнится, я всегда находил неприводимый трехчлен (начинал перебор с трехчленов степени $n$)

[xmaister]

VladimirKr
Спасибо за ответ. Но я что-то не совсем понял, т.е. приется каждый многочлен степени $n$ проверять? Вообще мне нужно (желательно быстро) найти многочлен степени $n$ над $F_2$. Я пока не особо представляю как это провернуть без перебора....

[Joker_vD]

xmaister
Знаете, а вы постройте список всех неприводимых над $\mathbb F_2$ многочленов для $n$, скажем, $\leqslant 200$. Потом попробуйте поискать какие-нибудь закономерности (типа, "всегда есть неприводимый трехчлен") и даже, может быть, доказать их.

[VladimirKr]

Вероятность того, что случайный многочлен степени $n$ неприводим известна и, мне кажется, достаточно велика. Ну и распределение времени поиска неприводимого можно достаточно точно оценить. А уж устроит вас это время или нет - вам решать.

[Joker_vD]

Вообще, могу посоветовать в NTL глянуть внутри GF2XFactoring.cpp, на функции BuildIrred(), BuildSparseIrred() — для степеней не выше $2048$ есть неприводимые пятичлены, но не всегда трехчлены: например, все трехчлены восьмой степени приводимы.

[xmaister]

VladimirKr в сообщении #711548 писал(а):

Вероятность того, что случайный многочлен степени $n$ неприводим известна и, мне кажется, достаточно велика. Ну и распределение времени поиска неприводимого можно достаточно точно оценить. А уж устроит вас это время или нет - вам решать.

Мне это все не известно, к сожалению. Дадите ссылку где посмотреть?Joker_vD
Спасибо, ща глянем.

[xmaister]

Вообще для не шибко больших $n$ наверное и обычное решето сгодится...

[VladimirKr]

Цитата:

Мне это все не известно, к сожалению. Дадите ссылку где посмотреть?

Как пользоваться критерием Батлера я давал ссылку выше.
Количество унитарных неприводимых многочленов над $\mathbb{F}_q$ степени $n$ равно $\frac 1 n\sum\limits_{d|n}q^{d}\mu(\frac n d)$
Очень грубо говоря, каждый $n-$ый. Ну и значит, среднее время нахождения при случайном выборе где-то $O(n^3)$
Посмотреть можно, например, в Лидл,Нидеррайтер "Конечные поля"
Кроме этого, например, Степанов С. А. "О числе неприводимых над конечным полем многочленов заданного вида"

-- 17.04.2013, 17:41 --

xmaister в сообщении #711613 писал(а):

Вообще для не шибко больших $n$ наверное и обычное решето сгодится...

Ну, сложность такого поиска экспоненциальна от $n$?