Двоичный XGCD для полиномов

Question

Существует двоичный алгоритм GCD для нахождения наибольшего общего делителя числа. В общем, GCD может быть расширен до XGCD, что может помочь найти мультипликативный обратный в поле.

Я работаю с двоичными числами, которые представляют полином. Например, цепочка битов 1101 представляет х ^3 + х ^ 2 + 1. Мне нужно вычислить модульную инверсию случайного полинома по модулю x^p - 1 для некоторого большого известного простого числа p. Тем не менее, мне нужно сделать это в постоянное время (это означает, что время выполнения не должно зависеть от числа, которое я инвертирую). Я знаю, как сделать двоичный GCD постоянным по времени, и я знаю, как реализовать XGCD для полиномов для вычисления мультипликативных инверсий. Чего я не знаю, так это если существует двоичный эквивалент GCD (с соответствующим XGCD) для (двоичных) полиномов?

Answer 1

Да, есть. "Бинарный" GCD работает в любом кольце, где существует наименьшее простое число. Для целых чисел это 2отсюда и название бинарное. Для полиномов это x, Алгоритм следует той же идее: вычесть многочлены, чтобы исключить свободный член в одной из более высоких степеней, вычленить максимально возможную степень xи продолжайте, пока результат вычитания не станет равным нулю.