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 ] 

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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