Портал аспирантов
 

Вернуться   Портал аспирантов > Общие > Дискуссионный зал > Физико-математические науки

Ответ
 
Опции темы
Старый 30.11.2011, 11:24   #1
Paul Kellerman
Gold Member
 
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,804
По умолчанию Формальная производная полинома над полем GF(p^m)

В свое время я в теме, посвященной алгебраической теории кодирования,
обсуждал вопрос теоретического обоснования формулы формальной произ-
водной полинома 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). Подробности в файле.
Вложения
Тип файла: pdf formal_derivative.pdf (302.0 Кб, 7 просмотров)
Paul Kellerman вне форума   Ответить с цитированием
Реклама
Старый 01.12.2011, 17:05   #2
phys2010
Silver Member
 
Аватар для phys2010
 
Регистрация: 30.12.2010
Адрес: ЦФО, Россия
Сообщений: 852
По умолчанию

Цитата:
Сообщение от PavelAR Посмотреть сообщение
...полученная формула (производной полинома над конечным полем) конечно похожа на ту, кот. приводится в книге Ван дер Вардена,...
В книге Ван дер Вардена рассмотрен также и существенно более общий случай дифференцирования произвольной алгебраической функции (в том числе и от нескольких переменных). Этот материал изложен в параграфе 76 на стр. 259-264. Формулы, полученные там, позволяют, в частности, найти полную производную многочлена от нескольких переменных. Интересно, работает ли ваш метод в этом, более общем, случае?
phys2010 вне форума   Ответить с цитированием
Старый 02.12.2011, 10:34   #3
Paul Kellerman
Gold Member
 
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,804
По умолчанию

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

Попытка в лоб использовать тождество d(a*x^n) / dx = n*a*x^(n-1) приводит
к заведомо неверному результату в конечных полях, особенно когда элементы
поля представлены не в виде многочленов, а в виде числовых эквивалентов в
десятичной, например, системе счисления, а Варден, к сожалению, никак не
комментирует (я не увидел), как именно интерпретировать выражение (n*a).
Paul Kellerman вне форума   Ответить с цитированием
Старый 02.12.2011, 15:41   #4
phys2010
Silver Member
 
Аватар для phys2010
 
Регистрация: 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]+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).

Очевидно, что это выражение полностью совпадает с тем, что получли вы.
phys2010 вне форума   Ответить с цитированием
Старый 09.12.2011, 08:47   #5
Paul Kellerman
Gold Member
 
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,804
По умолчанию

Цитата:
Сообщение от 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].

Последний раз редактировалось Paul Kellerman; 09.12.2011 в 09:35.
Paul Kellerman вне форума   Ответить с цитированием
Старый 09.12.2011, 11:43   #6
phys2010
Silver Member
 
Аватар для phys2010
 
Регистрация: 30.12.2010
Адрес: ЦФО, Россия
Сообщений: 852
По умолчанию

"Загвозка" в разных обозначениях. У Ван дер Вардена для операции умножения не используется дополнительная символика. Так, умножение в поле 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). Таким образом, ваши с Ван дер Варденом подходы приводят в точности к одному выражению для производной.
phys2010 вне форума   Ответить с цитированием
Ответ

Опции темы

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.



Текущее время: 00:10. Часовой пояс GMT +3.


Powered by vBulletin® Version 3.8.8
Copyright ©2000 - 2024, vBulletin Solutions, Inc. Перевод: zCarot
© 2001—2024, «Аспирантура. Портал аспирантов»
Рейтинг@Mail.ru