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

Портал аспирантов (http://www.aspirantura.spb.ru/forum/index.php)
-   Физико-математические науки (http://www.aspirantura.spb.ru/forum/forumdisplay.php?f=128)
-   -   Вопрос по алгебраической теории кодирования (http://www.aspirantura.spb.ru/forum/showthread.php?t=6380)

gav 17.01.2011 11:42

PavelAR
Цитата:

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

phys2010 17.01.2011 17:45

Цитата:

Сообщение от PavelAR (Сообщение 113202)
что касается деления логарифмов, она, вроде как, не определена?

Рассмотрим вновь выражение 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 01.02.2011 13:12

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

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

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

phys2010 01.02.2011 17:13

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

Paul Kellerman 03.02.2011 09:18

Цитата:

Сообщение от phys2010 (Сообщение 119094)
множество логарифмов является коммутативным кольцом с единиц

Спасибо большое! То есть для любого простого поля Галуа 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 03.02.2011 11:36

Цитата:

Сообщение от PavelAR (Сообщение 119413)
Вопрос второй, чтобы уж совсем успокоиться

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

Paul Kellerman 04.02.2011 11:10

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

Paul Kellerman 30.05.2011 09:55

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


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

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