Действительно, она не элемент поля, зато она логарифм элемента поля :)

Именно так! Слагаемое
kL[k]*X^k=L[k]*X^k+....+L[k]*X^k.
С другой стороны, в поле Галуа GF(2^n) справедливо тождество
A+A=0.
Поэтому
2L[k]*X^k=L[k]*X^k+L[k]*X^k=0,
3L[k]*X^k=2L[k]*X^k+L[k]*X^k=L[k]*X^k,
и т.д.

Вся фишка в том, что в выражении kL*X^k символом k (если мы считаем, что он обозначает элемент поля Галуа) обозначены два (вообще говоря различных) элемента. В сомножителе kL этот символ принимает значения 0 и 1, а в сомножителе X^k - значение любого элемента поля. Чтобы не заморачиваться с этим, проще понимать под выражением n*X сумму n одинаковых элементов X+...+X, где n - натуральное число, а X - элемент поля Галуа. Эквивалентность двух подходов следует из тождества X+X=0.

Кстати, по этой теме есть неплохая книга:
Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971.
В ней терия конечных полей изложена ясно и достаточно полно.

Читал взахлеб :) Вообще, Берлекэмп - однозначно гений, придумать алгоритм со
сложностью всего ~ t^2 для решения системы уравнений и при этом, чтобы сте-
пень полинома-решения была минимальной... это просто невообразимая крутизна.

К сожалению мне трудно это оценить...
Слишком далеко все это находится от области моих интересов :)

Млин... Вот уж не думал, что школьная и институтская алгебра (матан)
могут подложить такие "грабли". Просто еще со школьной скамьи усва-
иваешь, что производная от X^k это k*X^k-1, причем k в множителе и
k в степени элементы одного и того же поля вещественных чисел. Когда
начинаешь ковыряться с полями Галуа, то с удивлением обнаруживаешь,
что школьные и институтские знания дают "осечку". Вы были совершенно
правы, при взятии производной от функции X^k в случае поля Галуа, "k",
"слезающая" со степени в множитель также при этом трансформируется
из элемента поля (или кольца???) логарифмов в элемент поля Галуа (GF).
И для корректной трансформации от "k" нужно взять остаток по модулю 2.
То есть, как я уже писал раньше: d(X^k)/dX = (k mod 2)*X^(k-1), k >= 1.

Короче говоря, "множители", "слагаемые" и значения самой переменной X
- элементы поля Галуа, а степени - это уже элементы поля (или кольца?)
логарифмов, где правила сложения, вычитания и умножения такие же как
в школьной алгебре, только все операции делаются по модулю (2^8 - 1),
ну, а что касается деления логарифмов, она, вроде как, не определена?

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, будут различаться и это приведет к ненужному усложнению текста.

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

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

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

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

Спасибо большое! То есть для любого простого поля Галуа 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)),
ну и соответственно, соответствие в обратном направлении также справедливо?

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

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

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