2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Умножение многочленов в конечном поле
Сообщение06.01.2023, 20:26 
Аватара пользователя


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

Код:
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;

 Профиль  
                  
 
 Re: Умножение многочленов в конечном поле
Сообщение07.01.2023, 04:32 
Заслуженный участник


23/07/08
10626
Crna Gora
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.
Сравните с моим циклом.

 Профиль  
                  
 
 Re: Умножение многочленов в конечном поле
Сообщение07.01.2023, 05:42 
Заслуженный участник


23/07/08
10626
Crna Gora
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 после сдвигов, на одной из итераций может случиться переполнение. Старшая единица при очередном сдвиге просто исчезнет, а дальнейшие вычисления будут неверными.

 Профиль  
                  
 
 Re: Умножение многочленов в конечном поле
Сообщение07.01.2023, 12:02 
Аватара пользователя


03/01/23
57
Код:
for (int k=0; k<d; ++k)
{
   if ((a>>k) & 1) // k-й бит числа a
      result ^= b<<k;
}


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

 Профиль  
                  
 
 Re: Умножение многочленов в конечном поле
Сообщение07.01.2023, 17:38 
Заслуженный участник


23/07/08
10626
Crna Gora
Умножение полинома $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 здесь.

 Профиль  
                  
 
 Re: Умножение многочленов в конечном поле
Сообщение07.01.2023, 19:38 
Аватара пользователя


03/01/23
57
Спасибо, разобрался.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group