Проблема следующая — я написал функцию нахождения обратной матрицы в поле Галуа GF(256) с использованием метода Гаусса. Функция нормально работает при замене чисел из поля Галуа на действительные числа и операций в поле Галуа на обычные операции, т.е. в самом алгоритме ошибок нет. Но вот в поле Галуа вычислять обратную матрицу она не хочет. Мне кажется, это связано с тем, что в поле Галуа такого размера не выполняется закон дистрибутивности умножения и сложения.
Подскажите, пожалуйста, какой алгоритм следует использовать? Или я что-то неправильно понимаю?
Здравствуйте, Manticore, Вы писали:
M>Мне кажется, это связано с тем, что в поле Галуа такого размера не выполняется закон дистрибутивности умножения и сложения.
Звучит забавно
Если в нем не выполняется закон дистрибутивности, то это уже не поле, а безобразие какое-то
Да и как Вы себе представляете отсутствие дистрибутивности: Ваше поле -- это всего лишь фактор кольца многочленов над Z_2 по неприводимому многочлену 8-й степени. Потеряться дистрибутивности тут негде.
M>Подскажите, пожалуйста, какой алгоритм следует использовать? Или я что-то неправильно понимаю?
Искать ошибку в реализации операций в конечном поле.
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, Manticore, Вы писали:
M>>Мне кажется, это связано с тем, что в поле Галуа такого размера не выполняется закон дистрибутивности умножения и сложения.
Mab>Звучит забавно Если в нем не выполняется закон дистрибутивности, то это уже не поле, а безобразие какое-то Да и как Вы себе представляете отсутствие дистрибутивности: Ваше поле -- это всего лишь фактор кольца многочленов над Z_2 по неприводимому многочлену 8-й степени. Потеряться дистрибутивности тут негде.
M>>Подскажите, пожалуйста, какой алгоритм следует использовать? Или я что-то неправильно понимаю?
Mab>Искать ошибку в реализации операций в конечном поле.
Если не трудно, укажи, пожалуйста, на ошибку.
Вот: GFMul(2^3, 5) = 15
GFMul(2,5)^GFMul(3,5)=127
Функции:
Умножение:
UCHAR GFMul(UCHAR x, UCHAR y)
{
if(!x || !y) return 0;
int t = alpha_of[x] + alpha_of[y];
if(t>255) t -= 255;
return index_of[t];
}
Генерация таблиц:
void GFFillTables()
{
int InitialPolynom = 29; // (x^8) + x^4 + x^3 + x^2 + 1
UCHAR i;
// Нулевой элемент
alpha_of[0] = 255;
index_of[alpha_of[0]] = 0;
// Единичный элемент
alpha_of[255] = 0;
index_of[alpha_of[255]] = 255;
// Порождающий полином
alpha_of[1] = InitialPolynom;
index_of[alpha_of[1]] = 1;
// Заполняем оставшуюся часть таблицы
for (i = 2; i < 255; i++)
{
if (alpha_of[i-1] >= 128)
alpha_of[i] = alpha_of[1] ^ (alpha_of[i-1] << 1);
else
alpha_of[i] = alpha_of[i-1] << 1;
index_of[alpha_of[i]] = i;
}
}
