Генерация обратного элемента в поле Галуа

#python #алгоритм #криптография

Имеем поле Галуа GF(2409), и неприводимый полином над полем :

f(x) = x409 + x15 + x6 + x + 1
//Коэффициенты при степенях только 0 или 1

Пускай у меня есть какой-то полином a(x) в этом поле.
Вопрос: Как мне найти обратный к "а(x)",относительно f(x) элемент , используя именно
алгоритм Евклида, а не возведение элемента "а(x)" в степень 2409-2.

//Алгоритм поиска обратного элемента пишу на Python используя полиномиальный базис,
а на нём возведение в степень работает слишком долго
//Проблемы возникают при введении операции деления на полиномах
    

Ответы

Ответ 1

2409-2 - это число, содержащее 409 установленных битов и один сброшенный (предпоследний).
Это значит, что для быстрого возведения в эту степень элемента a(x) требуется 408 операций
возведения в квадрат и 408 операций умножения над полиномами 409-го порядка по модулю f(x).

Для умножения полиномов нужно 409 * 410 / 2 умножений, порядок произведения будет
818. Для приведения его к модулю f(x) по методу деления "уголком" требуется 409*4 вычитаний,
что практически не влияет на производительность.

Итого: 2 * 408 * 409 * 410 / 2 = 68 417 520 умножений.

Реальная проблема - в разрядности данных, поскольку при каждом возведении полинома
в квадрат сумма его коэффициентов (равная значению полинома при x = 1) также возводится
в квадрат, что увеличивает исходную разрядность на 409 log2 a(1) бит и в итоге "утяжеляет"
алгоритм, как минимум, на 2 порядка.

Остальное - детали реализации.