Обратить хэш спереди

Для моего славного хобби обычно достаточно просто иметь рабочий код, поэтому математически корректная формулировка задачи может быть непростым делом...

1) Требуется умножать двоичные полиномы с приведением результата по модулю неприводимого многочлена 32-степени, т.е. в GF(2^32), с использованием небольшого числа небольших таблиц.

2) Для поля GF(2^16) возможно построение таблиц логарифмов и антилогарифмов, которые будут занимать 2*65536*2 байт, что вполне допустимо. Тогда умножение элементов a_ и b_ отличных от нуля может быть осуществлено как a_*b_=Exp[Log[a_] + Log[b_] mod 65535]

3) Для поля GF(2^32) такие таблицы будут занимать уже 2*4G*4 байт, что недопустимо.

4) Однако в GF(2^32) существуют циклические подгруппы по умножению с периодом 65535, поскольку 2^32-1=65535*65537

5) Требуется предложить способ умножения в GF(2^32) с использованием логарифмов(или индексов) циклических подгрупп по аналогии с 2)

 

RElf

Вот Вам пару цитат по сабжу

Я пока только работал в конечных полях с полным генератором. Они мало чем отличаются от обычных чисел. С менее совершенными конструкциями как то кольца или эти субполя не работал (т.к. боюсь делителей нуля и непредсказуемого поведения).

 

Блин, просто чума какая-то, то 5 умножений, то 6 умножений! Почему не четыре умножения столбиком?