2014 dxdy logo

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

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




 
 Умножение полиномов по модулю
Сообщение22.08.2014, 11:37 
Доброго времени суток, уважаемые участники форума.

Я начну с места в карьер, а затем попытаюсь обощить свой вопрос.
Итак, предположим, у нас есть три полинома:
$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}$. Если воспользоваться им при вычислении произведения двух исходных многочленов, то результат будет далёк от того, что я обозначил в самом начале.
Помогите пожалуйста восстановить цепь преобразований, а также подскажите правило, которым необходимо руководствоваться при вычислении.

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

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

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

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

 
 
 
 Posted automatically
Сообщение22.08.2014, 13:36 
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

 
 
 
 Re: Умножение полиномов по модулю
Сообщение22.08.2014, 13:45 
Аватара пользователя
А если просто взять остаток от деления произведения первых двух многочленов на третий многочлен?

 
 
 
 Re: Умножение полиномов по модулю
Сообщение22.08.2014, 14:56 
ChrisLamier в сообщении #898309 писал(а):
Если бы $m(x) =x^8 + 1$, то, вероятно, было бы справедливо равенство $x^i \mod x^8 + 1 = x^{i \mod 8}$.
Да, было бы. Но это к делу не относится, поскольку $m(x)$ у Вас не $x^8+1$.
ChrisLamier в сообщении #898309 писал(а):
а также подскажите правило, которым необходимо руководствоваться при вычислении.
Школьникам это правило известно как "деление углом". Вспомнили?

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group