2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Разложение многочлена на множители над конечным полем
Сообщение20.05.2016, 14:38 


20/05/16
14
Здравствуйте.
Не могли бы помочь мне разобраться в данной теме. Я сам программист, а не математик, потому немного запутался.

Задача - разложить многочлен над конечным полем $GF(2^n)$ , используя алгоритм Берлекэмпа
В интернете можно найти только примеры с $n=1$ , либо для $GF(p)$ ( $p$ - простое). И как работает сам алгоритм я вроде бы и понял.

Я вообще правильно понимаю, что коэффициенты у многочлена - это элементы поля $GF(2^n)$ ? Ведь эти элементы тоже имеют полиномиальную форму.
С арифметикой в поле тоже понял практически как работать используя степени двойки, но не могу разобраться в одном моменте. Как определить какой многочлен брать в качестве неприводимого? Вначале думал что он имеет общий вид $x^n+x+1$ , но на степени $5$ пошли нестыковки. Для его нахождения разложить на множители многочлен $x^{2^n-1} + 1$ над $GF(2)$ нужно?

Может есть пример, где рассматривается разложение над каким то полем $GF(p^n)$ (где $n$ - не $1$ ) ?

 Профиль  
                  
 
 Posted automatically
Сообщение20.05.2016, 14:47 


20/03/14
12041
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

 Профиль  
                  
 
 Posted automatically
Сообщение20.05.2016, 15:51 


20/03/14
12041
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

 Профиль  
                  
 
 Re: Разложение многочлена на множители над конечным полем
Сообщение20.05.2016, 17:25 
Заслуженный участник


08/04/08
8562
dypsi в сообщении #1124708 писал(а):
Как определить какой многочлен брать в качестве неприводимого?
Никак: можно брать любой неприводимый. Если степень многочлена одна и та же, то все поля, порожденные разными неприводимыми многочленами, будут изоморфны.

dypsi в сообщении #1124708 писал(а):
Для его нахождения разложить на множители многочлен $x^{2^n-1} + 1$ над $GF(2)$ нужно?
Можно, не необязательно. Искать можно хоть методом тыка. Да и раскладывать, пожалуй, запаритесь: $2^n-1$ - это много, раскладывать многочлен на множители не очень просто.
Думаю (но я не спец, бойтесь советов неспецов) можно просто поперебирать многочлены степени $n$. Среди них неприводимых довольно много, угадать довольно легко.
Указать формулой семейство неприводимых многочленов я не смогу. И вряд ли. Это примерно как указать параметрически семейство простых чисел - я такого ни одного не знаю.

dypsi в сообщении #1124708 писал(а):
Может есть пример, где рассматривается разложение над каким то полем $GF(p^n)$ (где $n$ - не $1$ ) ?
Попробуйте скачать книжку Лидл Нидеррайтер Конечные поля, там точно есть.

 Профиль  
                  
 
 Re: Разложение многочлена на множители над конечным полем
Сообщение20.05.2016, 17:36 


20/05/16
14
А если перебирать, есть тест многочлена на неприводимость?

В книге $GF(2)$ и $GF(23)$ есть. Почему то только для простых чисел все время встречается. Но алгоритм должен работать для $GF(p^n)$ . Еще есть шанс что я не верно совсем все понимаю.

 Профиль  
                  
 
 Re: Разложение многочлена на множители над конечным полем
Сообщение20.05.2016, 17:55 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
dypsi в сообщении #1124708 писал(а):
Может есть пример, где рассматривается разложение над каким то полем $GF(p^n)$ (где $n$ - не $1$ ) ?

Общий алгоритм Берлекэмпа подробно расписан у О.Н. Василенко . стр 170 и далее, соответствующий материал есть и во втором томе Д. Кнута.

 Профиль  
                  
 
 Re: Разложение многочлена на множители над конечным полем
Сообщение20.05.2016, 18:02 


20/05/16
14
Алгоритм Берлекэмпа у меня работает для $GF(2)$ . Мне нужно понять, как он работает в $GF(2^n)$ , так как такой вариант отличается принципиально.

За ссылку спасибо, нашел там проверку на неприводимость многочлена

 Профиль  
                  
 
 Re: Разложение многочлена на множители над конечным полем
Сообщение20.05.2016, 18:30 
Заслуженный участник
Аватара пользователя


11/01/06
3824
dypsi в сообщении #1124742 писал(а):
Мне нужно понять, как он работает в $GF(2^n)$ , так как такой вариант отличается принципиально.
Да ничем он не отличается. Алгоритм Берлекэмпа одинаково работает над любым конечным полем. Просто с элементами $GF(p)$ легко работать (фактически это работа с остатками при делении на $p$), поэтому в примерах только этот случай и рассматривается.

 Профиль  
                  
 
 Re: Разложение многочлена на множители над конечным полем
Сообщение20.05.2016, 18:37 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
RIP в сообщении #1124750 писал(а):
Просто с элементами $GF(p)$ легко работать (фактически это работа с остатками при делении на $p$), поэтому в примерах только этот случай и рассматривается.

Как я понял из фразы
dypsi в сообщении #1124708 писал(а):
Я вообще правильно понимаю, что коэффициенты у многочлена - это элементы поля $GF(2^n)$ ? Ведь эти элементы тоже имеют полиномиальную форму.
, ТС затрудняется в работе с полями конечной характеристики, когда элементов поля больше, чем величина характеристики, именно из-за способа представления элементов поля. Иными словами, ему нужно разбираться с конечными полями прямо "от печки".

 Профиль  
                  
 
 Re: Разложение многочлена на множители над конечным полем
Сообщение20.05.2016, 21:02 


20/05/16
14
Нет. Я понял как работать с таким полем (за исключением поиска неприводимого многочлена подходящего). Меня смущает то, что везде рассматривают только случаи с $GF(p) $ . Думал, что это может означать что они приводятся из вида $GF(p^n)$ к виду $GF(p)$ . И тот факт что коэффициенты многочленов тоже имеют полиномиальную форму. В общем думал, что понял все не так как надо. А наличие любого примера помогло бы разобраться.

 Профиль  
                  
 
 Re: Разложение многочлена на множители над конечным полем
Сообщение21.05.2016, 12:18 


20/05/16
14
А есть способ найти неприводимый многочлен степени $n$ над $GF(2) $ кроме перебора и проверки на неприводимость? Или, если это программа, их из таблицы стоит брать?

 Профиль  
                  
 
 Re: Разложение многочлена на множители над конечным полем
Сообщение21.05.2016, 13:19 
Заслуженный участник


08/04/08
8562
dypsi в сообщении #1124854 писал(а):
Или, если это программа, их из таблицы стоит брать?
Для программы, конечно, проще из таблицы. Вряд ли у Вас $n>10^3$. Для такого диапазона проще 1 раз вычислить и сохранить.

dypsi в сообщении #1124854 писал(а):
А есть способ найти неприводимый многочлен степени $n$ над $GF(2) $ кроме перебора и проверки на неприводимость?
Интересный вопрос :-)
Это обсуждалось в topic71047.html
(Еще где-то была тема topic15488.html?hilit=Rowland вот про такую последовательность: http://oeis.org/A132199. Интересно, этот генератор можно адаптировать для поиска неприводимых многочленов над конечными полями?)

dypsi в сообщении #1124708 писал(а):
ля его нахождения разложить на множители многочлен $x^{2^n-1} + 1$ над $GF(2)$ нужно?
Вот тоже неплохой критерий, но тоже переборный. (и наверное)

 Профиль  
                  
 
 Re: Разложение многочлена на множители над конечным полем
Сообщение21.05.2016, 17:25 


20/05/16
14
Еще вопрос возник.
В поле $GF(2^n)$ $2^n$ элементов. Для умножения и нахождения обратного элемента используются степени двойки в этом поле. Вычислять их по каждый раз - слишком затратно, а один раз вычислить и сохранить в массив - при больших $n$ очень много памяти займет. С умножением еще можно разобраться. А есть какие - то способы быстро находить обратные элементы?

 Профиль  
                  
 
 Re: Разложение многочлена на множители над конечным полем
Сообщение21.05.2016, 17:50 
Заслуженный участник


08/04/08
8562
Зависит от того представления элементов, которое Вы выбрали. Например, как известно, мультипликативная группа поля циклична, откуда следует, что любой элемент представляется в виде $\alpha^k, k=1,2^n-1$ или $0$. В таком виде элементы можно перемножать ну очень быстро и искать обратный элемент - тоже очень быстро. Но для сложения придется использовать функцию Якоби - тоже либо затабулировать, либо вычислять каждый раз.
Если представляете элементы в виде многочленов, то $\beta^{-1}=\beta^{2^n-2}$ - последнее можно вычислять двоичным возведением в степень. Можно, наверное, использовать и алгоритм Евклида для многочленов для поиска обратного элемента (для $GF(p)$ для поиска обратных элементов используется именно он).
dypsi в сообщении #1124914 писал(а):
Вычислять их по каждый раз - слишком затратно
В $GF(p)$ использование алгоритма Евклида как раз вообще не затратно.
Оба алгоритма быстрые - за $O(\ln q)$ в поле $GF(q)$ работают.
Наверняка у программистов уже есть какая-то практика при работе с конечными полями - надо искать инфу о ней. А я не знаю :-(

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: StudentV


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group