Здравствуйте!

Мне пока известно лишь то, что умножение в GF(2^8) реализуется сложением индексов и с использованием таблицы.
Буду благодарен за любую информацию о других существующих алгоритмах.

Чего так сложно? Умножение над GF(2^8) эквивалентно взятию самого младшего байта произведения 

Что-то у меня так не получается. Например, в матлабе gf(10, 8)*gf(10, 8) = 68. Как это получить предлагаемым Вами способом?

gf(x,m) 

Я же говорил о перемножении двух чисел в поле 2^8

Значит, наверно, я непонятно выразился.
Имеем поле GF(2^8), основанное на полиноме x^8 + x^4 + x^3 + x^2 + 1.
Нужен алгоритм быстрого перемножения чисел из этого поля. Собственно, в приведенном примере ( gf(10, 8)*gf(10, 8) = 68 ) показано, что требуется сделать.

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

Сообщение отредактировал andrex - Feb 25 2009, 14:10

А что тут придумаешь? Таблично.
- анализ на a==0 или b==0
- берем логарифм a (для GF(2^10) - таблица 1024xshort)
- по той же таблице - логарифм b
- сумма по модулю 2^10-1
- антилогарифм (другая таблица, тоже 1024xshort)
Способы ускорения:
- часто требуется умножать массив на константу, ее логарифм взять заранее, далее - иметь спецфункцию GF_mul_exp(GF_val a, GF_log B )
- чтобы не тратить время на проверки равенства 0 и взятие по модулю - иметь расширенную вчетверо таблицу антилогарифмов:
log(0)=2*2^N, таблица расширена просто: exp(2^N...2*2^N-2) = exp(1...2^N-1), при x>2*2^N-2 exp(x)=0

Спасибо, в общем-то так и делаю.

А в чем проблема? Что может быть быстрее таблицы, особенно если избавиться от добавочных проверок? Как вариант - храните элементы в логарифмическом представлении. Но тогда складывать по таблицам придется - шило на мыло...

Есть книга Морелос-Сарагоса "Искусство помехоустойчивого кодирования", есть сайт
http://the-art-of-ecc.com
Там куча примеров программ работы с полями Галуа (БЧХ, Рид-Соломон)
По полиному генерируются две таблицы - основная и логарифмическая и имеются две простые функции сложения и умножения, которые обращаются к этим таблицам.