tefion Mar 14 2016 at 11:52

Конечное поле GF(256) и немного магии

6 min

28K

C++*Abnormal programming*

From sandbox

+20

Comments 13

pavelodintsov Mar 14 2016 at 11:53

Крутой вариант шаблонной магии С++! :)

mayorovp Mar 14 2016 at 13:31

Функцию 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.

mayorovp Mar 14 2016 at 13:48

Оптимизировать — так до конца. Число операций 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);
}

koldyr Mar 14 2016 at 15:10

Скажите, чем вас не устроила таблица логарифмов?

rprokop Mar 15 2016 at 14:29

Присоединяюсь к вопросу. Обычно вычисляют таблицу логарифмов. Либо в compile-time, либо можно написать генератор.
Умножение — это потенцированная сумма логарифмов, по модулю N-1. Недостаток — само умножение в compile-time загнать сложнее (но в принципе возможно).

iUser Mar 14 2016 at 16:02

"Galua" — это от души. Бедный Galois.

domix32 Mar 14 2016 at 17:59

Не все знакомы с французским

rprokop Mar 15 2016 at 14:37

А еще, чтобы не писать сишные GaloisMul, можно слепить класс с переопределенными арифметическими операциями. Хороший компилятор умеет экземпляр такого класса размещать в регистрах, если нужно. Делал так в рабочем проекте. Всё это крутилось на платформе CUDA с умопомрачительной скоростью :)

VAE Jul 11 2020 at 22:04

>Итак, требуется реализовать следующие операции в поле GF(256) над многочленом x^8 + x^4 + x^3 + x + 1:
Обозначение поля странное. Если числовое поле вычетов, то ~~GF(256)~~, то в скобках должно быть простое число (не 256), если поле расширения, то в скобках степень простого GF(2^8). Не все вещи можно игнорировать, если не хотите демонстрировать свою неграмотность
Поле задается не только неприводимым многочленом, но и примитивным элементом.
У Вас он какой? Не встретил о нем в тексте ни одного слова.

-1

mayorovp Jul 12 2020 at 11:43

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

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

VAE Jun 14 at 09:46

Не могу согласиться. Поля из 256 чисел не бывает, так как 256 не простое число. Обозначение для поля из 256 многочленов должно содержать указание на неприводимый многочлен. Иначе поле не построить. Разные примитивные элементы приводят к получению разных полей. Тот кто поставил мне минус не понимает этих деталей.

-1

mayorovp Jun 14 at 10:11

В комментарии выше вы сами писали GF(2^8) без указания неприводимого многочлена.

VAE Jun 17 at 09:51

Здравствуйте !

В алгебре (высшей), в теории поля 256 и 2^8 не одно и тоже. Когда указывается числом порядок поля, оно (число) может быть только простым, а когда указывается как степень характеристики поля, имеется в виду поле многочленов (поле расширения). При этом (для построения поля) подразумевается, что для задания поля необходимо указывать примитивный элемент и неприводимый многочлен. Я поле строить не собирался и в этой ситуации достаточно указать, что речь идет о поле расширения. Математика изобилует такими деталями как и программирование. Не знание таких деталей говорит о подготовке пишущего.

Поле, если его построить, как предлагает автор, не имеет отношения к шифру. Пример зашифрования\расшифрования автор не приводит. В моих публикациях (они учебные) все сделано строго, хотя и не с первого раза. Кстати, в публикации Зензина О.С., Иванова М.А. примитивный элемент также не указан, а на обложке грам. ошибка, но поле построено верно. Мне пришлось находить самостоятельно находить примитивный элемент.

С уважением, Арис

-1