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

[andrex]

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

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

[_Pasha]

 умножение в GF(2^8)

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

[andrex]

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

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

[_Pasha]

 Например, в матлабе

gf(x,m) 

Создает массив элементов конечного поля из матрицы x. Конечное поле имеет 2^m элементов

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

[andrex]

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