Быстрое экспонирование для полей галуа

Question

Я хочу быть в состоянии вычислить

g^x = g * g * g * ... * g     (x times)

где g находится в конечном поле GF(2^m). Здесь m довольно большое, m = 256, 384, 512 и т. Д., Поэтому таблицы поиска не являются решением. Я знаю, что есть действительно быстрые алгоритмы для аналогичной идеи, modpow для Z/nZ (см. Страницу 619-620 HAC).

1. Что такое быстрый, не основанный на таблицах способ вычисления циклов (т. Е. G ^x)?
2. Это, безусловно, желательный вопрос, но здесь он возникает: может ли идея " умножения / возведения в степень Монтгомери" быть "переработана" на месторождения Галуа? Я хотел бы думать так из-за изоморфных свойств, но я действительно не знаю.

Замечание: это из моего поста на math.stackru.com. Полагаю, это лучшее сообщество, чтобы задать этот вопрос.

Answer 1

Из сообщества по обмену математическими стеками у меня было два человека, которые предложили Binary Exponentiaion. Википедия утверждает, что это рекурсивный алгоритм. Его можно изменить на итеративный алгоритм, как показано в псевдокоде вики.

Сначала я нахмурился над этой идеей, но я больше изучил ее и нашел две статьи ( 1, 2), которые могут помочь реализовать двоичное возведение в степень в полях Галуа, использующих умножение Монтгомери.

Кроме того, Per Hornshøj-Schierbeck предложил использовать нормальные основания (или когда m =/= 256,384, 512 и т. Д. Оптимальные нормальные основания) для ускорения умножения. Алгоритмы для этого метода умножения можно найти в этой статье.

Спасибо Сарнольду за его вклад.