Народ, помогите решить задачку!!!

Borman

Пожалста, кто чем может:) :
Конечное Поле Галуа 64 порядка

исходный многочлен в GF(64):
4x^19 + 13x^18 + 63x^17 + x^16 + 24x^15 + 9x^14 + 59x^13 + 3x^12 +
15x^11 + 4x^10

генератор многочлен) g(x) = (x-2^1x-2^2)...(x-2^10) =
x^10 + 31x^9 + 28x^8 + 39x^7 + 42x^6 + 57x^5 + 2x^4 + 3x^3 + 49x^2 + 44x + 46
Исходный многочлен поделён на генератор многочлен, получая в остатке:
50x^9 + 2x^8 + 42x^7 + 51x^6 + 53x^5 + 34x^4 + 22x^3 + 20x^2 + 5x + 16
Задача состоит в том, что бы получить алгоритм деления многочленов
конечных полей. Что бы можно было ввести коэффициенты первого
многочлена, второго многочлена и получить коэффициенты результата. Ну
или хотя бы понять, как это деление в столбик действует. Что удалось
найти пока, это то что в конечных полях деление а / b является
умножением a на b ^ -1.

Sanych

Поле Галуа порядка 64 - это поле, состоящее из 64 элементов. При этом, естественно, 1+1=0
Элементы поля представляются в виде a_5q^5+a_4q^4+a_3q^3+a_2q_2+a_1q+a_0, где a_i -- коэффициэнты (равные 0 или 1).
Судя по всему, 2 это обозначение для q и вообще выше приведённое выражение обозначается целым числом
N=a_5 2^5 + a_4 2^4 +a_3 2^3 +a_2 2^2 +a_1 2^1 +a_0 2^0. Тогда приведённое вычисление может иметь некоторый смысл.
Перемножать такие элементы (по сути, многочлены над полем из 2 элементов) надо по модулю некоторого неприводимого многочлена степени 6.
Таких неприводимых штук 9, какой из них использовать - я не знаю:
1+q+q^6
1+q^3+q^6
1+q+q^2+q^4+q^6
1+q+q^3+q^4+q^6
q^6+q^5+1
1+q+q^2+q^5+q^6
1+q^2+q^3+q^5+q^6
1+q+q^4+q^5+q^6
1+q^2+q^4+q^5+q^6
Откуда взялось приведённое вычисление и какой характер оно носит (рекомендация по формату ввода-вывода, результат работы некоторой программы, часть постановки задачи)?

PS. Для деления на элемент поля GF(64) проще всего зараннее составить таблицу обратных и потом ей пользоваться.

Borman

результат программы...
спасибо огромное, сейчас попробую разобраться

Mike3

результат программы...
спасибо огромное, сейчас попробую разобраться
охренеть. это чо за программа такая вежливая?

Borman

программа ищет ошибки при считывании шрих-кодов
друг ее усовершенствует, вот возникли проблемы с полями Галуа...
еще раз спасибо за помощь, я сам в этом ни хрена не понимаю....

Sanych

Вопрос: а если программа уже есть, то разве она делает не то самое, что нужно? Или проблема в том, что выводится остаток, а надо получить частное? Вообще, деление многочленов, даже если у них коэффициенты из GF(64) - это обычное деление в столбик, отличается только то, как при этом их коэффициенты будут складываться, делиться и перемножаться друг с другом.
Оставить комментарий
Имя или ник:
Комментарий: