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

Question

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

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

Answer 1

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