Значение многочленов в полях Галуа

[migellito]

Здравствуйте, разбираюсь с полями Галуа. Мне нужно найти корни полинома $Lambda_0 + Lambda_1 x^1 + Lambda_2 x^2 + Lambda_3 x^3$
Где $Lambda_i$ - коэффициенты представленные в полиномиальной форме.

Соответственно корни я нахожу подставлением вместо $x$ последовательно всех элементов от $Alpha_0 $ до $Alpha_{2^m-1}$ также в полиномиальной форме. В частности вычисления идут в поле $GF(2^6)$.

Правильно ли я понимаю, что если после подстановки $i-го$ элемента и выполнения операций сложения и умножения, в соответствии с правилами поля, значение полинома равно 0, то элемент $2^m - 1 - i$ будет являться корнем многочлена?

[Joker_vD]

Лямбда пишется как \lambda: $\lambda$. Альфа пишется как \alpha: $\alpha$.

Теперь по сути вопроса: как вы нумеруете элементы поля? Что такое "$i$-ый элемент"?

[migellito]

Хмм, действительно.

Насколько я понимаю элементы поля можно формировать следующим образом
полагаем $\alpha_0 = 1$, а далее сдвигаем эту единицу вправо (имея ввиду более старшие степени ) по разрядам полиномиального представления элемента поля, и, в случае, если степень становится большей $m-1$ - делим на минимальный полином (вроде в данном контексте его можно назвать образующим, не уверен в терминах, но например для $GF(2^6)$ я использую $p(x) = x^6 + x + 1$ )
каждый раз при сдвиге индекс i при $\alpha_i$ увеличивается на единицу.

Вообще говоря, не работает конкретная реализация данного алгоритма поиска, которая устроена следующим образом:
сначала на 0-ой итерации я подставляю вместо $x$ - $\alpha_0 = 1$ и проверяю равенство нулю,
затем на 1-ой итерации я сдвигаю каждый коэффициент $\lambda$ при $x^j$ в сторону старших степеней, на j разрядов, реализуя таким образом умножение коэффициентов исходного полинома на $\alpha_1$ в соответствующей степени, помня про то, что умножение должно быть по модулю образующего многочлена. И, суммируя их, опять проверяю равенство нулю.
Соответственно на i-ой итерации я сдвигаю коэффициенты полинома, полученные на $i-1 $-ой итерации, таким образом подставляя следующий элемент поля.
После $2^m - 1$ итераций все элементы пространства были подставлены в исходный многочлен.
Я буду очень признателен, если вы напишите свои мысли по поводу математической стороны данной реализации и, возможно, некоторых неверных выводов в описанных действиях.

PS К сожалению я уже не могу исправить греческие буквы в предыдущем сообщении

[Joker_vD]

В принципе все правильно, только не забывайте еще ноль подставлять. И помните, что кратности корней вы таки образом не определите.

По математической стороне: вы тупо перебираете все элементы поля и подставляете их в многочлен. Поскольку многочлен у вас кубический, а поле — $2^6$, т.е. маленькое, то это, пожалуй, самое разумное дело.

Однако в случае больших степеней и больших полей эффективнее использовать специальные алгоритмы. Они подробно описаны в Лидл, Нидеррайтер, "Конечные поля". Момент, когда такие хитрые алгоритмы начинают работать быстрее тупого перебора, определяется экспериментально.

[migellito]

Спасибо за замечания про ноль и кратность.

Вроде бы то, что я применяю называется алгоритм Чена (Chien).

Вообще говоря, мои $2^6$ это один наиболее простой из частных случаев, которые мне необходимы. Наиболее сложным же будет решение многочлена $24$-ой степени в поле $GF(2^{14})$. Считаете в этом случае имеет смысл обратить внимание на более продвинутые алгоритмы?
Признаюсь не смотрел еще книгу, которую вы посоветовали, возможно вы бы могли в нескольких словах описать принцип этих специальных алгоритмов. Это может помочь мне оценить трудоемкость их реализации.

[VAL]

Не совсем понял Ваши обозначения.
Верно ли я понимаю задачу: Найти корни полинома 24-й (допустим) степени с коэффициентами из поля $GF(14)$?
А что такое Ваша $\alpha$? Это порождающий элемент мультипликативной группы поля $GF(2^m)$?
А чему равно $m$? 336?

Если я верно понял постановку задачи, то решал бы ее так:
Вначале разложил бы исходный полином на неприводимые множители (используя технику отделения кратных корней и алгоритм Берлекэмпа).
А затем искал бы корни этих сомножителей (что может существенно уменьшить перебор). Тем более, что для каждого неприводимого сомножителя достаточно найти всего один корень. Остальные получаются его циклическим возведением в $q$-ю степень, где $q$ - число элементов основного поля (например, $2^{14}$).

PS: Впрочем, я совсем не уверен, что я верно понял постановку задачи.
Но в любом случае согласен с рекомендацией обратиться к двухтомнику Лидла и Нидеррайтера.

[migellito]

Я, очевидно, не настолько глубоко изучил тему, чтобы ответить на ваши вопросы.
В целом - да задача - в поиске корней полинома 24-ой (или менее) степени с коэффициентами в виде многочленов 13-ой степени.

под $\alpha_i$ я имею ввиду множество элементов поля, которые получаю последовательно в сдвиговом регистре, заранее выбрав минимальный полином для этого поля.
В целях ускорения процесса поиска предполагаю увеличивать параллелизм (да - тупой метод), и разбивать на группы в зависимости от количества корней, поскольку вероятность необходимости решения полинома 24 степени сильно меньше, чем 1-5 степеней.

Извиняюсь за нематематичное описание проблемы, меня больше интересует непосредственное приложение теории.