Формальная производная полинома над полем GF(p^m)

Paul Kellerman · 30.11.2011, 11:24

В свое время я в теме, посвященной алгебраической теории кодирования,
обсуждал вопрос теоретического обоснования формулы формальной произ-
водной полинома L(x), приводимой в литературе по теории кодирования без
какого-либо выведения или хотя бы пояснений, и я изложил свою "версию"
вывода формулы, но тогда я ограничивался полиномами, конкретно над по-
лями Галуа GF(2^m), а теперь доразобрался и для общего случая GF(p^m).

Кстати говоря, полученная формула конечно похожа на ту, кот. приводится
в книге Ван дер Вардена, но в конечных полях GF(p^m) есть особый нюанс.

Если коротко, пусть задан полином L(x) = L[0] + L[1]*x + ... + L[k-1]*x^(k-1)
над конечным полем GF(p^m). Тогда формальная производная полинома L(x):

d(L(x))/dx = (L[1]*(1 mod p)) + (L[2]*(2 mod p))*x + ... + (L[k-1]*((k-1) mod p))*x^(k-2)

Особо обращаю внимание, что выражение (i mod p) для каждого i = 1...k-1
вычисляется в привычной арифметике, то есть берется остаток от деления
индекса i на простое число p. Но вот результирующий вычисленный остаток
интерпретируется как элемент поля GF(p^m), и далее вычисляется произве-
дение этого элемента на соответствующий коэффициент L[i], также являю-
щийся элементом поля GF(p^m) с использованием операции умножения поля.

Нюансом в конечным полях Галуа GF(p^m) является арифметическое свойство:
Сумма из n слагаемых элементов a: (a + a + ... + a) в поле равна ((n mod p)*a),
где (n mod p) вычисляется в привычной арифметике, а затем полученный оста-
ток интерпретируется как элемент поля GF(p^m) и умножается на элемент a с
использованием уже операции умножения этого поля. Именно этот нюанс лежит
в основе вывода формулы формальной производной L(x). Подробности в файле.

phys2010 · 01.12.2011, 17:05

Цитата:

Сообщение от PavelAR

...полученная формула (производной полинома над конечным полем) конечно похожа на ту, кот. приводится в книге Ван дер Вардена,...

В книге Ван дер Вардена рассмотрен также и существенно более общий случай дифференцирования произвольной алгебраической функции (в том числе и от нескольких переменных). Этот материал изложен в параграфе 76 на стр. 259-264. Формулы, полученные там, позволяют, в частности, найти полную производную многочлена от нескольких переменных. Интересно, работает ли ваш метод в этом, более общем, случае?

Paul Kellerman · 02.12.2011, 10:34

Ну, наверное, я некорректно выразился... Я имел ввиду не суперобобщение,
как в книге Вардена, а локальное обобщение со случая GF(2^m) до GF(p^m).
К сожалению из общих рассуждений Вардена вовсе неочевидна производная
для полинома от одной переменной над полем GF(p^m), это нужно еще долго
и нудно выводить, готовых "выводов" я не нашел, пришлось самому заняться.

Попытка в лоб использовать тождество d(a*x^n) / dx = n*a*x^(n-1) приводит
к заведомо неверному результату в конечных полях, особенно когда элементы
поля представлены не в виде многочленов, а в виде числовых эквивалентов в
десятичной, например, системе счисления, а Варден, к сожалению, никак не
комментирует (я не увидел), как именно интерпретировать выражение (n*a).

phys2010 · 02.12.2011, 15:41

PavelAR, вы с Ван дер Варденом просто не поняли друг друга

. На самом деле оба определения вполне согласуются друг с другом. Рассмотрим определение производной по Ван дер Вардену. Исходный полином и его производная имеют вид:

L(x)=L[0]+L[1]x+L[2]x^2+L[3]x^3+...+L[k]x^k
L'(x)=L[1]+2*L[2]x+3*L[3]x+...+k*L[k]x^(k-1).

Здесь L[k] - элемент поля F, x - переменная (принимающая значения в поле F), k - натуральное число. Кроме того предполагается, что

x^k=xx...x
k*M[x]=M[x]+M[x]+...+M[x]

- формальные выражения для произведения и суммы k сомножителей и слагаемых, соответственно. В том случае, когда значение x=a (т.е. является фиксированным), соответствующие произведения и суммы вычисляются в поле F. Предположим, что F=GF(p^m) - поле Галуа. Тогда, ввиду дистрибутивности законов сложения и умножения, и ввиду того, что сомножитель k*L[k] определен в поле GF(p^m), слагаемое

k*L[k]x^(k-1)=(k*L[k])x^(k-1)=((k*L[k]) mod p)x^(k-1)=(L[k]*(k mod p))x^(k-1).

Поэтому выражение для производной по Ван дер Вардену над полем GF(p^m) можно переписать в следующем виде:

L'(x)=(L[1]*(1 mod p))+(L[2]*(2 mod p))x+...+(L[k]*(k mod p))x^(k-1).

Очевидно, что это выражение полностью совпадает с тем, что получли вы.

Paul Kellerman · 09.12.2011, 08:47

Цитата:

Сообщение от phys2010

Кроме того предполагается, что
k*L[k] = L[k] + L[k] + ... + L[k]

Наверное именно в этом загвоздка, что k просто некоторое натуральное число, а не
элемент поля, которому принадлежат коэффициенты полинома, и левая часть тожде-
ства не совсем корректна, так как под знаком * понимается бинарная операция умно-
жения поля (или не понимается?), при этом множитель k не является элементом поля.

А если это не тождество, а определение некоторого формального спецпроизведения,
которое должно вычисляться через суммирование с применением операции сложения
поля, то какой-то другой знак должен быть, чтобы не путать с операцией умножения.

В своих выкладках я избегаю введения операции "спецпроизведения", вместо этого
показываю, как натуральное число k корректно превратить в элемент поля GF(p^m).
Кстати с вычислительной точки зрения такой подход тоже выгоднее, ибо если напри-
мер p = 7, а k = 500, то вычислить 500 mod 7 = 3 и умножить его на коэффициент L[k]
c применением операции умножения поля будет быстрее, чем 499 раз прибавить L[k].

phys2010 · 09.12.2011, 11:43

"Загвозка" в разных обозначениях. У Ван дер Вардена для операции умножения не используется дополнительная символика. Так, умножение в поле F записывается просто как ab=c. А символ * включил я, для того, чтобы кратко обозначить сумму k элементов. Именно, a*k=a+a+...a (всего k раз). Дело в том, что в книге Ван дер Вардена встречаются выражения вида ab и ak без объяснения их содержания. Поэтому здесь я просто тождественно положил ak=a*k, если k - натуральное (чтобы не было путаницы). А у вас же, как я понял, символ * используется для записи умножения в поле GF(p^m). Вот и вся разница.

Кстати, избежать введения дополнительной операции "спецпроизведения" (т.е. исключить символ *) можно и в формализме Ван дер Вардена. Действительно, из-за наличия модуля, производную (по Ван дер Вардену) можно записать в двух эквивалентных видах:

L'(x)=(L[1]*(1 mod p))+(L[2]*(2 mod p))x+...+(L[k]*(k mod p))x^(k-1),
L'(x)=(L[1](1 mod p))+(L[2](2 mod p))x+...+(L[k](k mod p))x^(k-1).

В первом выражении (которое появилось в #4) символ * используется для обозначения суммы k слагаемых, во втором (которое полностью эквивалентно вашему из #1) используется операция умножения над полем GF(p^m). То, что эти две формулы совпадают, следует из того, что L[k]*(k mod p)=L[k](k mod p) над полем GF(p^m). Таким образом, ваши с Ван дер Варденом подходы приводят в точности к одному выражению для производной.

02.12.2011, 10:34	#3
Paul Kellerman Gold Member Регистрация: 25.06.2005 Адрес: F000:FFF0 Сообщений: 1,814	Ну, наверное, я некорректно выразился... Я имел ввиду не суперобобщение, как в книге Вардена, а локальное обобщение со случая GF(2^m) до GF(p^m). К сожалению из общих рассуждений Вардена вовсе неочевидна производная для полинома от одной переменной над полем GF(p^m), это нужно еще долго и нудно выводить, готовых "выводов" я не нашел, пришлось самому заняться. Попытка в лоб использовать тождество d(ax^n) / dx = nax^(n-1) приводит к заведомо неверному результату в конечных полях, особенно когда элементы поля представлены не в виде многочленов, а в виде числовых эквивалентов в десятичной, например, системе счисления, а Варден, к сожалению, никак не комментирует (я не увидел), как именно интерпретировать выражение (na).

02.12.2011, 15:41	#4
phys2010 Silver Member Регистрация: 30.12.2010 Адрес: ЦФО, Россия Сообщений: 852	PavelAR, вы с Ван дер Варденом просто не поняли друг друга . На самом деле оба определения вполне согласуются друг с другом. Рассмотрим определение производной по Ван дер Вардену. Исходный полином и его производная имеют вид: L(x)=L[0]+L[1]x+L[2]x^2+L[3]x^3+...+L[k]x^k L'(x)=L[1]+2L[2]x+3L[3]x+...+kL[k]x^(k-1). Здесь L[k] - элемент поля F, x - переменная (принимающая значения в поле F), k - натуральное число. Кроме того предполагается, что x^k=xx...x kM[x]=M[x]+M[x]+...+M[x] - формальные выражения для произведения и суммы k сомножителей и слагаемых, соответственно. В том случае, когда значение x=a (т.е. является фиксированным), соответствующие произведения и суммы вычисляются в поле F. Предположим, что F=GF(p^m) - поле Галуа. Тогда, ввиду дистрибутивности законов сложения и умножения, и ввиду того, что сомножитель kL[k] определен в поле GF(p^m), слагаемое kL[k]x^(k-1)=(kL[k])x^(k-1)=((kL[k]) mod p)x^(k-1)=(L[k](k mod p))x^(k-1). Поэтому выражение для производной по Ван дер Вардену над полем GF(p^m) можно переписать в следующем виде: L'(x)=(L[1](1 mod p))+(L[2](2 mod p))x+...+(L[k](k mod p))x^(k-1). Очевидно, что это выражение полностью совпадает с тем, что получли вы.

09.12.2011, 11:43	#6
phys2010 Silver Member Регистрация: 30.12.2010 Адрес: ЦФО, Россия Сообщений: 852	"Загвозка" в разных обозначениях. У Ван дер Вардена для операции умножения не используется дополнительная символика. Так, умножение в поле F записывается просто как ab=c. А символ * включил я, для того, чтобы кратко обозначить сумму k элементов. Именно, ak=a+a+...a (всего k раз). Дело в том, что в книге Ван дер Вардена встречаются выражения вида ab и ak без объяснения их содержания. Поэтому здесь я просто тождественно положил ak=ak, если k - натуральное (чтобы не было путаницы). А у вас же, как я понял, символ * используется для записи умножения в поле GF(p^m). Вот и вся разница. Кстати, избежать введения дополнительной операции "спецпроизведения" (т.е. исключить символ ) можно и в формализме Ван дер Вардена. Действительно, из-за наличия модуля, производную (по Ван дер Вардену) можно записать в двух эквивалентных видах: L'(x)=(L[1](1 mod p))+(L[2](2 mod p))x+...+(L[k](k mod p))x^(k-1), L'(x)=(L[1](1 mod p))+(L[2](2 mod p))x+...+(L[k](k mod p))x^(k-1). В первом выражении (которое появилось в #4) символ * используется для обозначения суммы k слагаемых, во втором (которое полностью эквивалентно вашему из #1) используется операция умножения над полем GF(p^m). То, что эти две формулы совпадают, следует из того, что L[k]*(k mod p)=L[k](k mod p) над полем GF(p^m). Таким образом, ваши с Ван дер Варденом подходы приводят в точности к одному выражению для производной.

Реклама