2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Неприводимые над $\mathbb{F}_2$
Сообщение17.04.2013, 12:45 
Аватара пользователя
Привет! Можно ли явно указать неприводимый многолчен над $\mathbb{F}_2$ произвольной степени $n$?

 
 
 
 Re: Неприводимые над $\mathbb{F}_2$
Сообщение17.04.2013, 14:18 
Могу сказать, что можно для заданного многочлена за время $O(n^2)$ проверить неприводимость (Критерий Батлера). Ну или построить за среднее время $O(n^2)$ пребирая многочлены подряд. Однако на практике, помнится, я всегда находил неприводимый трехчлен (начинал перебор с трехчленов степени $n$)

 
 
 
 Re: Неприводимые над $\mathbb{F}_2$
Сообщение17.04.2013, 14:24 
Аватара пользователя
VladimirKr
Спасибо за ответ. Но я что-то не совсем понял, т.е. приется каждый многочлен степени $n$ проверять? Вообще мне нужно (желательно быстро) найти многочлен степени $n$ над $F_2$. Я пока не особо представляю как это провернуть без перебора....

 
 
 
 Re: Неприводимые над $\mathbb{F}_2$
Сообщение17.04.2013, 14:32 
xmaister
Знаете, а вы постройте список всех неприводимых над $\mathbb F_2$ многочленов для $n$, скажем, $\leqslant 200$. Потом попробуйте поискать какие-нибудь закономерности (типа, "всегда есть неприводимый трехчлен") и даже, может быть, доказать их.

 
 
 
 Re: Неприводимые над $\mathbb{F}_2$
Сообщение17.04.2013, 14:36 
Вероятность того, что случайный многочлен степени $n$ неприводим известна и, мне кажется, достаточно велика. Ну и распределение времени поиска неприводимого можно достаточно точно оценить. А уж устроит вас это время или нет - вам решать.

 
 
 
 Re: Неприводимые над $\mathbb{F}_2$
Сообщение17.04.2013, 14:42 
Вообще, могу посоветовать в NTL глянуть внутри GF2XFactoring.cpp, на функции BuildIrred(), BuildSparseIrred() — для степеней не выше $2048$ есть неприводимые пятичлены, но не всегда трехчлены: например, все трехчлены восьмой степени приводимы.

 
 
 
 Re: Неприводимые над $\mathbb{F}_2$
Сообщение17.04.2013, 15:29 
Аватара пользователя
VladimirKr в сообщении #711548 писал(а):
Вероятность того, что случайный многочлен степени $n$ неприводим известна и, мне кажется, достаточно велика. Ну и распределение времени поиска неприводимого можно достаточно точно оценить. А уж устроит вас это время или нет - вам решать.

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

 
 
 
 Re: Неприводимые над $\mathbb{F}_2$
Сообщение17.04.2013, 16:34 
Аватара пользователя
Вообще для не шибко больших $n$ наверное и обычное решето сгодится...

 
 
 
 Re: Неприводимые над $\mathbb{F}_2$
Сообщение17.04.2013, 16:39 
Цитата:
Мне это все не известно, к сожалению. Дадите ссылку где посмотреть?

Как пользоваться критерием Батлера я давал ссылку выше.
Количество унитарных неприводимых многочленов над $\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$?

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group