Быстрые алгоритмы арифметики в полях Галуа? Опции

[andrex]

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

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

[kons]

А что тут придумаешь? Таблично.
- анализ на 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

[andrex]

А что тут придумаешь? Таблично.

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

[kons]

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

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