Комментарии 10
Крутой вариант шаблонной магии С++! :)
Функцию galuaMul можно упростить:
Не важно сколько нулей и единиц в basePolynome, при делении многочленов неполное частное зависит только от старшего одночлена. В формате программы, неполное частное от деления mul на basePolynome — это mul>>32.
uint64_t galuaMul(uint64_t a, uint64_t b){
uint64_t mul = polynomeMul(a, b);
const uint64_t basePolynome = 0x100011011;
return mul ^ polynomeMul(basePolynome, mul>>32);
}Не важно сколько нулей и единиц в basePolynome, при делении многочленов неполное частное зависит только от старшего одночлена. В формате программы, неполное частное от деления mul на basePolynome — это mul>>32.
Оптимизировать — так до конца. Число операций galuaMul при нахождении обратного элемента можно уменьшить с 13 до 11 если вместо общего алгоритма воспользоваться разложением
254 = 2 * (1 + 2 * 3 * 3 * (1 + 2 * 3)):uint64_t galuaInverse(uint64_t a){
uint64_t a2 = galuaMul(a, a);
uint64_t a6 = galuaMul(a2, galuaMul(a2, a2));
uint64_t a7 = galuaMul(a6, a);
uint64_t a21 = galuaMul(a7, galuaMul(a7, a7));
uint64_t a63 = galuaMul(a21, galuaMul(a21, a21));
uint64_t a126 = galuaMul(a63, a63);
uint64_t a127 = galuaMul(a126, a);
return galuaMul(a126, a126);
}
Скажите, чем вас не устроила таблица логарифмов?
"Galua" — это от души. Бедный Galois.
А еще, чтобы не писать сишные GaloisMul, можно слепить класс с переопределенными арифметическими операциями. Хороший компилятор умеет экземпляр такого класса размещать в регистрах, если нужно. Делал так в рабочем проекте. Всё это крутилось на платформе CUDA с умопомрачительной скоростью :)
>Итак, требуется реализовать следующие операции в поле GF(256) над многочленом x^8 + x^4 + x^3 + x + 1:
Обозначение поля странное. Если числовое поле вычетов, тоGF(256), то в скобках должно быть простое число (не 256), если поле расширения, то в скобках степень простого GF(2^8). Не все вещи можно игнорировать, если не хотите демонстрировать свою неграмотность
Поле задается не только неприводимым многочленом, но и примитивным элементом.
У Вас он какой? Не встретил о нем в тексте ни одного слова.
Обозначение поля странное. Если числовое поле вычетов, то
Поле задается не только неприводимым многочленом, но и примитивным элементом.
У Вас он какой? Не встретил о нем в тексте ни одного слова.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Конечное поле GF(256) и немного магии