GF2p8 Аффинные преобразования (ч. 4)

Вычисление CRC на операции умножения в изоморфном представлении поля GF(2^8)

Мы приблизились к тому, ради чего все затевали.. Нет, вычисление CRC-8 не самоцель. Это самый простой пример применения арифметики Галуа, на котором можно проверить методику. Наша цель - изоморфные преобразования поля, чтобы свести все варианты расчета к одному полиному 0x11B.

Хотелось бы донести хотя бы до одного человека, как выводить алгоритмы. На первом шаге берем операцию, на которой работает CRC:
a(x)×x⁸ mod P(x) -- операция '×'-умножение без переноса или сдвиг.
Это можно представить иначе:
a(x)⊗(x⁸ mod P(x)) -- операция '⊗'-умножение в поле P(x).
Для полинома 0x11D выражение принимает вид: a(x)⊗0x1D -- операция '⊗'-умножение в поле P(x)=0x11D.

// CRC-8 в поле 0x11D
uint8_t crc = 0xFD;// начальное значение
uint8_t x8  = 0x1D;
for (i=0; i<length; i++) {
    crc = gf2p8_mul(crc ^ data[i], x8, 0x11D);
}
return crc;

M^-1·M(a(x)×0x1D mod 0x11D) = M^-1((M·a(x)) × (M·0x1D) mod 0x11B) -- операция '×'-сначала выполняется в поле P(x)=0x11D, а после преобразования в поле P(x)=0x11B.

// CRC-8 в изоморфном представлении 0x11D=>0x11B
// матрицы изоморфного преобразования {11D, 02} =>{11B, FB}
uint64_t M =0x57EED8E22A228202;
uint64_t Mr=0x4F803A301CA0E8C0;

uint8_t crc = affine_byte(M, 0xFD);// начальное значение
uint8_t x8  = affine_byte(M, 0x1D);// преобразование 0x11D=>0x11B
for (i=0; i<length; i++) {
    crc^= affine_byte(M, data[i]);
    crc = gf2p8_mul(crc, x8, 0x11B);
}
return affine_byte(Mr, crc);// обратное преобразование 0x11B=>0x11D

FD => 6A        57EED8E22A228202
1D => 11        57EED8E22A228202
DE => 7E        4F803A301CA0E8C0
CRC8I=7E ..ok

Операция вычисляется на двух инструкциях в цикле: gf2p8_mul и affine. Работает!!