Разложение многочлена на множители над конечным полем

[dypsi]

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

Задача - разложить многочлен над конечным полем $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$ ) ?

[Lia]

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

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

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

[Lia]

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

[Sonic86]

dypsi в сообщении #1124708 писал(а):

Как определить какой многочлен брать в качестве неприводимого?

Никак: можно брать любой неприводимый. Если степень многочлена одна и та же, то все поля, порожденные разными неприводимыми многочленами, будут изоморфны.

dypsi в сообщении #1124708 писал(а):

Для его нахождения разложить на множители многочлен $x^{2^n-1} + 1$ над $GF(2)$ нужно?

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

dypsi в сообщении #1124708 писал(а):

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

Попробуйте скачать книжку Лидл Нидеррайтер Конечные поля, там точно есть.

[dypsi]

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

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

[Brukvalub]

dypsi в сообщении #1124708 писал(а):

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

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

[dypsi]

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

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

[RIP]

dypsi в сообщении #1124742 писал(а):

Мне нужно понять, как он работает в $GF(2^n)$ , так как такой вариант отличается принципиально.

Да ничем он не отличается. Алгоритм Берлекэмпа одинаково работает над любым конечным полем. Просто с элементами $GF(p)$ легко работать (фактически это работа с остатками при делении на $p$), поэтому в примерах только этот случай и рассматривается.

[Brukvalub]

RIP в сообщении #1124750 писал(а):

Просто с элементами $GF(p)$ легко работать (фактически это работа с остатками при делении на $p$), поэтому в примерах только этот случай и рассматривается.

Как я понял из фразы

dypsi в сообщении #1124708 писал(а):

Я вообще правильно понимаю, что коэффициенты у многочлена - это элементы поля $GF(2^n)$ ? Ведь эти элементы тоже имеют полиномиальную форму.

, ТС затрудняется в работе с полями конечной характеристики, когда элементов поля больше, чем величина характеристики, именно из-за способа представления элементов поля. Иными словами, ему нужно разбираться с конечными полями прямо "от печки".

[dypsi]

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

[dypsi]

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

[Sonic86]

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)$ нужно?

Вот тоже неплохой критерий, но тоже переборный. (и наверное)

[dypsi]

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

[Sonic86]

Зависит от того представления элементов, которое Вы выбрали. Например, как известно, мультипликативная группа поля циклична, откуда следует, что любой элемент представляется в виде $\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)$ работают.
Наверняка у программистов уже есть какая-то практика при работе с конечными полями - надо искать инфу о ней. А я не знаю