Умножение полиномов по модулю

[ChrisLamier]

Доброго времени суток, уважаемые участники форума.

Я начну с места в карьер, а затем попытаюсь обощить свой вопрос.
Итак, предположим, у нас есть три полинома:
$a(x) = x^6 + x^4 + x^2 + x + 1;$
$b(x) = x^7 + x + 1;$
$m(x) = x^8 + x^4 + x^3 + x + 1.$

Необходимо найти произведение $a(x)\cdotb(x)$ $\mod$ $m(x)$. Впрочем, известно, что оно равно $x^7 + x^6 + 1$, но у меня не получается прийти к такому результату. Вот на чём я остановился:

$c(x) = (x^6 + x^4 +x^2 + x + 1)(x^7 + x + 1) \mod (x^8 + x^4 + x^3 + x + 1) = \\ = (x^{13} + x^7 + x^6 + x^{11} + x^5 + x^4 + x^9 + x^3 +x^2 +x^8 + x^2 + x + x^7 + x + 1) \mod (x^8 + x^4 + x^3 + x^3 + x + 1) = (x^{13} + x^{11} + x^9 + x^8 + (x^7 \oplus x^7) + x^6 + x^5 + \\ + x^4 + x^3 + (x^2 \oplus x^2) + (x \oplus x) + 1)) \mod (x^8 + x^4 + x^3 + x^3 + x + 1) = (x^{13} + x^{11} + \\ + x^9 + x^8 + x^6 + x^5 +x^4 + x^3 + 1) \mod (x^8 + x^4 + x^3 + x + 1) = ...= x^7 + x^6 + 1.$

Если бы $m(x) =x^8 + 1$, то, вероятно, было бы справедливо равенство $x^i \mod x^8 + 1 = x^{i \mod 8}$. Если воспользоваться им при вычислении произведения двух исходных многочленов, то результат будет далёк от того, что я обозначил в самом начале.
Помогите пожалуйста восстановить цепь преобразований, а также подскажите правило, которым необходимо руководствоваться при вычислении.

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Тема перемещена в Карантин по следующим причинам:

1. Запишите формулы в соответствии с требованиями Правил форума, т.е. в $\TeX$.
Краткие инструкции можно найти здесь: topic8355.html и topic183.html.
Кроме этого, в теме Видео-пособия для начинающих форумчан можно посмотреть видео-ролик "Как записывать формулы".

2. Приведите свои попытки решения и/или укажите затруднения.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[Brukvalub]

А если просто взять остаток от деления произведения первых двух многочленов на третий многочлен?

[nnosipov]

ChrisLamier в сообщении #898309 писал(а):

Если бы $m(x) =x^8 + 1$, то, вероятно, было бы справедливо равенство $x^i \mod x^8 + 1 = x^{i \mod 8}$.

Да, было бы. Но это к делу не относится, поскольку $m(x)$ у Вас не $x^8+1$.

ChrisLamier в сообщении #898309 писал(а):

а также подскажите правило, которым необходимо руководствоваться при вычислении.

Школьникам это правило известно как "деление углом". Вспомнили?