Умножение многочленов в конечном поле

[Without Name]

Пишу функцию для умножения многочленов в конечном поле по учебнику. Вот код умножения в столбик на си, на вход подаются два многочлена из расширения двоичного поля и многочлен, по которому построено расширение.

gf_element multiply(gf_element a, gf_element b, gf_element mod) {
    gf_element result = 0;

    a = rem(a, mod);
    b = rem(b, mod);
    
    int d = degree(mod);

    while (a != 0) {
        if (a & 1)
            result ^= b;
        a >>= 1;
        b <<= 1;

        if (degree(b) == d)
            b ^= mod;
    }

    return result;
}

Здесь

Цитата:

using gf_element = unsigned int;

Как работает этот алгоритм? Я понимаю только половину:

Приводим многочлены по модулю, если их степень больше, чем степень модуля

    a = rem(a, mod);
    b = rem(b, mod);

Умножаем $b$ на $a$ в столбик. Не $a$ на $b$, это принципиально для понимания кода дальше. Если первый бит $a$ единица, то как при умножении в стобик, прибавляем $b$ к результату

while (a != 0) {
        if (a & 1)
            result ^= b;

Сдвигаем $a$, чтобы посмотреть значение следующего бита.

a >>= 1;

С этого момента непонятно. Для чего сдвигаем $b$, какая математическая логика здесь закодирована?

b <<= 1;

Если степень $b$ больше степени модуля, устраняем переполнение. Но почему вычитаем модуль именно из $b$? Логичнее было бы вычитать его из $result$, потому что переполнение может произойти в результате всех сложений и получиться многочлен слишком большой степени, который надо привести по модулю. Или я неправильно понимаю?

if (degree(b) == d)
            b ^= mod;

[svv]

Without Name в сообщении #1576393 писал(а):

Приводим многочлены по модулю, если их степень больше, чем степень модуля

Назовём это действие нормализацией. После нормализации степень полинома $a(x)$ не превышает $d-1$. Будем пока для простоты игнорировать необходимость нормализации b и/или result, тогда цикл while можно переписать так:

Используется синтаксис C++

for (int k=0; k<d; ++k)
{
   if ((a>>k) & 1) // k-й бит числа a
      result ^= b<<k;
}

Отталкиваясь от такой формы цикла, легче ответить на вопрос.

Without Name в сообщении #1576393 писал(а):

Для чего сдвигаем $b$, какая математическая логика здесь закодирована?

Обозначения: число $a$ в программе кодирует полином $a(x)=\sum\limits_{k=0}^{d-1}a_k \,x^k$, где коэффициент $a_k$ равен $k$-му биту $a$.
Если
$c(x)=a(x)b(x)=\sum\limits_{k=0}^{d-1}a_k\;b(x)x^k,$
то
$c=\bigoplus\limits_{k=0}^{d-1}a_k(b\ll k)=\bigoplus\limits_{k=0}^{d-1}\begin{cases}b\ll k,&\text{если}\; a_k=1\\0,&\text{если}\; a_k=0\end{cases}$
Здесь $\bigoplus$ означает побитовый XOR.
Сравните с моим циклом.

[svv]

Without Name в сообщении #1576393 писал(а):

Если степень $b$ больше степени модуля, устраняем переполнение. Но почему вычитаем модуль именно из $b$? Логичнее было бы вычитать его из $result$, потому что переполнение может произойти в результате всех сложений и получиться многочлен слишком большой степени, который надо привести по модулю. Или я неправильно понимаю?

Я обозначу неприводимый многочлен, с помощью которого строилось расширение, через $m(x)$.
Во-первых, нормализация производится, даже если степень $b(x)$ равна степени $m(x)$. Правила игры таковы, что только полином $m(x)$ имеет степень $d$, остальные — меньшую, и достигается это нормализацией. Например, в случае $GF(2^3)$ можно взять $m(x)=x^3+x+1$. Тогда полином $x^3$ следует заменить на $-x-1=x+1$.
Во-вторых, давайте называть переполнением integer overflow, а не ситуацию, когда нужна нормализация.

Пусть тип gf_element 32-разрядный. Функция будет нормально работать, даже если $d=31$. Рассмотрим этот крайний случай. В цикле while в начале каждой итерации переменная b имеет нуль в старшем 31-м бите. Поскольку побитовый XOR не создаёт перенос, переполнения в операторе result ^= b не возникает.
После оператора b <<= 1 в старшем разряде b может появиться единица. В этом случае степень $b(x)$ достигла $31$ и нужна нормализация, в результате которой степень опять понижается. Всё хорошо.

Если же не нормализовать b после сдвигов, на одной из итераций может случиться переполнение. Старшая единица при очередном сдвиге просто исчезнет, а дальнейшие вычисления будут неверными.

[Without Name]

for (int k=0; k<d; ++k)
{
   if ((a>>k) & 1) // k-й бит числа a
      result ^= b<<k;
}

А здесь

result ^= b<<k;

выражение $b << k$ равносильно $bx^k$? Почему именно так? Почему к результату мы прибавляем это выражение?

[svv]

Умножение полинома $b(x)$ на $x$ соответствует логическому сдвигу $b$ влево на 1 бит.

(Наглядно)

На примере из Вики:

Сверху полином $b(x)=x^4+x^2+x+1$.
Умножая на $x$, получаем полином снизу:
$c(x)=x^5+x^3+x^2+x$

(Формально)

Пусть $b(x)=\sum\limits_{k=0}^{\operatorname{deg}(b)}b_k x^k$, тогда
$c(x)=xb(x)=\sum\limits_{k=0}^{\operatorname{deg}(b)}b_k x^{k+1}$
Сделаем замену $j=k+1, k=j-1$.
$c(x)=\sum\limits_{j=1}^{\operatorname{deg}(b)+1}b_{j-1} x^j$
Сравнивая с $c(x)=\sum\limits_{j=0}^{\operatorname{deg}(c)}c_j x^j$, получаем $c_0=0$ и $c_j=b_{j-1}$ при $j>0$.

Я думал, это самый очевидный момент.

-- Сб янв 07, 2023 15:51:35 --

Кстати, на этот вопрос Вам уже отвечал mihaild здесь.

[Without Name]

Спасибо, разобрался.