Comments 10
Функцию galuaMul можно упростить:

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);
}
Присоединяюсь к вопросу. Обычно вычисляют таблицу логарифмов. Либо в compile-time, либо можно написать генератор.
Умножение — это потенцированная сумма логарифмов, по модулю N-1. Недостаток — само умножение в compile-time загнать сложнее (но в принципе возможно).
А еще, чтобы не писать сишные GaloisMul, можно слепить класс с переопределенными арифметическими операциями. Хороший компилятор умеет экземпляр такого класса размещать в регистрах, если нужно. Делал так в рабочем проекте. Всё это крутилось на платформе CUDA с умопомрачительной скоростью :)
>Итак, требуется реализовать следующие операции в поле GF(256) над многочленом x^8 + x^4 + x^3 + x + 1:
Обозначение поля странное. Если числовое поле вычетов, то GF(256), то в скобках должно быть простое число (не 256), если поле расширения, то в скобках степень простого GF(2^8). Не все вещи можно игнорировать, если не хотите демонстрировать свою неграмотность
Поле задается не только неприводимым многочленом, но и примитивным элементом.
У Вас он какой? Не встретил о нем в тексте ни одного слова.

GF(n) — это обозначение для поля Галуа из n элементов. Поскольку для каждого n оно такое единственное (с точностью до изоморфизма и если вообще существует), нет никакой разницы в каком виде записано число n.


Можно даже GF(255+1) написать, это будет так же корректно.

Only those users with full accounts are able to leave comments. Log in, please.