Вопрос по алгебраической теории кодирования

[gav]

PavelAR

Вот уж не думал, что школьная и институтская алгебра (матан)
могут подложить такие "грабли".

Школьная и институтская математика здесь совершенно непричем! Эти "грабли" - исключительно продукт нашего мозга, склонного отождествлять неотождествимое и строить аналогию в неаналогичном. Ни в институте, ни, тем более, в школе, Вам никто не обещал, что производная в поле Галуа будет дакой же, как и в действительных числах. Наоборот, надо ставить вопрос об удивительном, что они так похожи!

[phys2010]

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

что касается деления логарифмов, она, вроде как, не определена?

Рассмотрим вновь выражение kL*X^k. Предположим, что мы пока не определили конкретный вид поля над которым работаем. В этом случае сомножитель kL=L+...+L, где символом k обозначено число слагаемых (некоторое натуральное число). С другой стороны, сомножитель X^k=X*...*X, где симколом k обозначено уже число сомножителей. Очевидно, что обоих случаях k - одно и тоже натуральное число. Теперь фиксируем поле. Если оно характеристики 0 (например, поле вещественных чисел), то оно содержит множество натуральных чисел и поэтому смысл символа k не меняется - его можно считать элементом поля. Если же мы имеем поле Галуа GF(2^n), то ситуация меняется. В этом случае для сомножителя kL мы должны использовать таблицу сложения (из которой следует тождество X+X=0), а для сомножителя X^k - таблицу умножения (из которой следует тождество X^q=X, где q=2^n). Причем L и X являются элементами поля, а вот символ k им не является. Этим символом обозначено лишь количество (натуральное число) слагаемых и сомножителей соответственно. И это количество в обоих сомножителях совпадает (кстати, при таком подходе школьная и институтская алгебра работают ). Поэтому определять деление на этом множестве (множестве натуральных чисел) некорректно.
PS
Можно, конечно, символы k в сомножителях kL и X^k вложить в поле Галуа (и тогда деление выполняться будет, поскольку k^{q-1}=1). Но тогда элементы, соответствующие символу k, будут различаться и это приведет к ненужному усложнению текста.

[Paul Kellerman]

Продолжаем тему... Следующий вопрос чуток другого плана...

Итак пусть задано простое конечное поле Галуа GF(p), где p - разумеется простое,
в котором сложение и умножение выполняется с помощью операций, соответсвую-
щих операциям сложения и умножения по модулю (p) с точки зрения привычной ал-
гебры поля действительных чисел. В поле GF(p) существует (и необязательно один)
примитивный элемент с помощью которого можно получить все ненулевые элементы
поля GF(p), путем возведения его в соответствующие степени 0, 1,..., p - 2. Сами
степени мы можем называть "логарифмами по основанию примитивного элемента" .

Так вот, пусть есть простое поле GF(p), пусть имеется множество {0, 1, ... , p - 2}
логарифмов по основанию примитивного элемента поля для всех ненулевых элемен-
тов поля GF(p). Зададим для множества логарифмов операции сложения и умноже-
ния, соответствующие операциям сложения и умножения по модулю (p - 1) с точки
зрения алгебры поля действительных чисел. А тогда, можно ли считать множество
логарифмов с двумя заданными операциями "коммутативным кольцом с единицей"?

[phys2010]

Да. В кольце целых чисел классы вычетов по произвольному положительному числу x состоят из тех чисел, которые при делении на x дают остаток y. Чтобы сложить или перемножить два класса вычетов нужно сложить или соответственно перемножить их представители и привести результат к его наименьшему неотрицательному остатку от деления на x. В вашем случае x=p-1 и поэтому x - четное число отличное от 2. Следовательно указанное множество логарифмов является коммутативным кольцом с единицей, в котором есть делители нуля (если p-1 не есть степень двойки).

[Paul Kellerman]

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

множество логарифмов является коммутативным кольцом с единиц

Спасибо большое! То есть для любого простого поля Галуа GF(p), p >= 3, можно пос-
троить соответствующее ему кольцо логарифмов LR(p - 1), LR - сокр. Logarithm Ring.
Причем, в случае: p = 3, мы получаем LR(2), которое также является и полем GF(2).

Теперь я могу спать спокойно

Вопрос второй, чтобы уж совсем успокоиться

А могу ли я утверждать, что циклическая мультипликативная группа, состоящая
из множества всех ненулевых элементов поля GF(p) и определенной в ней опера-
ции умножения (по модулю p), изоморфна циклической аддитивной группе, сос-
тоящей из множества соответствующих логарифмов и определенной в ней опера-
ции сложения (по модулю p - 1). То есть, для любых ненулевых a, b и с из GF(p),
таких что: с = a * b (по правилам умножения поля GF(p)), имеются соответству-
ющие u, v и w из LR(p - 1): w = u + v (по правилам сложения в кольце LR(p - 1)),
ну и соответственно, соответствие в обратном направлении также справедливо?

[phys2010]

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

Вопрос второй, чтобы уж совсем успокоиться

Любые две циклические группы одного порядка изоморфны (вне зависимости от явного вида операций, заданных на них). Изоморфизм определяется отображением (любого) порождающего элемента одной группы в (любой) порождающий элемент другой группы.

[Paul Kellerman]

Спасибо большое, теперь все ясно.

[Paul Kellerman]

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