Остаток от деления многочленов конечного поля

[Without Name]

Я пишу библиотеку для вычислений в конечных полях. Сейчас я делаю функции для операций над многочленами над полем $GF(2)$. Вот пример функции взятия остатка, которую я нашел в одной книге на псевдокоде.

int degree(uint8_t a) {
    if (a == 0)
        return -1;
    else
        return bit_length(a) - 1;
}


uint8_t rem(uint8_t a, uint8_t b) {
    uint8_t result = a;

    while (degree(result) >= degree(b)) {
        int position = degree(result) - degree(b);
        result ^= b << position;    // minus x^pos
    }

    return result;
}

Мне непонятна в функции $rem$ операция

result ^= b << position

Что здесь происходит? Строкой выше разность степеней многочленов $result$ и $b$ это степень икса в частном при делении в столбик. А что происходит потом, где операция $xor$ и битовый сдвиг? Здесь мой комментарий 'minus x power pos', я предположил, что это вычитание результата умножения делителя на степень икса как при делении в столбик, но я не уверен.

[mihaild]

Видимо считается, что в битах числа хранятся коэффициенты при соответствующих степенях многочлена. Тогда r ^ (b << p) это просто $r - b \cdot x^p$. Если у $r$ была степень $m$, а у $b$ степень $m < n$, то $b \cdot x^{n - m}$ - это многочлен степени $m$, а $r - b \cdot x^{n-m}$ - степени не выше $m - 1$.

(и это не псевдокод, это С)

[Without Name]

mihaild в сообщении #1576195 писал(а):

Видимо считается, что в битах числа хранятся коэффициенты при соответствующих степенях многочлена.

Да, все верно. А почему умножение на степень икс реализуется именно как сдвиг, какая тут логика? То есть почему

b << p

это $bx^p$?
Это не псевдокод, это то, что я пишу на си по этому псевдокоду :)

[mihaild]

Потому что как при умножении на $x^p$ коэффициент при $x^i$ становится коэффициентом при $x^{i + p}$, так и при битовом сдвиге $i$-й бит становится $i+p$-м.

(и я сильно подозреваю, что 8 бит вам не хватит, советую взять сразу 64 или завести псевдоним для типа, чтобы потом было легко поменять)

[Without Name]

А как в этом коде получить кроме остатка от деления еще неполное частное $quo$? Смотрю и не могу придумать, только решением уравнения додумался находить неполное частное. Или можно накапливать вот эти степени $b << power$ в переменной $quo$?

// FIXME
void quo_rem(gf_element a, gf_element b, gf_element& quo, gf_element& rem) {
    gf_element result = a;
    quo = 0;

    while (degree(result) >= degree(b)) {
        int power = degree(result) - degree(b);
        result ^= b << power; // result - bx^power
    }

    rem = result;
}

[svv]

Что-то я перестал понимать. Вы используете многочлены, чтобы построить расширение поля $GF(2)$, как в этой теме? То есть каждый многочлен представляет некий элемент поля $GF(2^m)$, так? Тогда какой остаток, в поле любые два элемента делятся без остатка (лишь на нуль делить нельзя).

Где я ошибаюсь?

[Without Name]

Я хочу в итоге реализовать расширенный алгоритм Евклида в конечном поле. Для этого нужны все эти операции. Но некоторые операции я пишу просто для работы с многочленами, они не обязательно должны быть в поле. Алгоритм Евклида будет для любых многочленов над $F_2$. Так что одни операции у меня работают в расширении поля, а другие - с многочленами над $F_2$

Вас смутил псевдоним типа $gf_element$, его лучше переименовать на $polynom$ для функций, которые работают с обычными многочленами.

[svv]

Я понимаю, что Вам это нужно. Давайте возьмём какое-нибудь игрушечное поле, например, $GF(2^2)$. Вот здесь таблица умножения. Покажите мне какие-нибудь два полинома, которые при делении друг на друга дают остаток.

-- Вт янв 24, 2023 14:39:58 --

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

Так что одни операции у меня работают в расширении поля, а другие - с многочленами над $F_2$

Понял.

[Without Name]

Вроде я додумался. Правильно?

// FIXME
void quo_rem(polynomial a, polynomial b, polynomial& quo, polynomial& rem) {
    rem = a;
    quo = 0;

    while (degree(rem) >= degree(b)) {
        int power = degree(rem) - degree(b);
        rem ^= b << power; // rem - b*x^power
        quo ^= 1 << power; // quo + x^power
    }
}

[svv]

Да, правильно.
Функцию можно проверить так. Возьмите несколько раз случайные a и b, найдите quo и rem. Они вычислены правильно, если
1) b*quo+rem равно a (сложение и умножение ясно в каком смысле)
2) степень rem ниже степени b

[Markiyan Hirnyk]

Without Name

Цитата:

Я пишу библиотеку для вычислений в конечных полях

Это механизировано в Мэйпле. См. (28)-(31) здесь.

[svv]

Markiyan Hirnyk, спасибо за ссылку и информацию.
К сожалению, не всегда можно использовать Maple. Представьте себе, например, декодер кода Рида-Соломона по методу Евклида, работающий на микроконтроллере во встроенной системе (где нет ни клавиатуры, ни монитора, а объём памяти минимальный).

[Markiyan Hirnyk]

svv
Вопрос задан не о железе, а о программе. См. также это.