Деление полиномов. Одинаковый остаток от деления.

[Mikle1990]

(Оффтоп)

Я к вам отсюда: topic75849.html
Циклический код : Computer Science

Делим полином на полином.

Делимое: $x^5$
Делитель: $x^5+x^4+x+1$
Остаток: $x^4+x+1$

Чем можно заменить делимое, чтобы остаток оставался тот же?

При том, что делимое:
1. Может иметь степень не больше $7$.
2. Должно состоять более чем из одного слагаемого, но менее чем из девяти слагаемых.

[provincialka]

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

[gris]

Можно ещё при этом делитель умножать на полиномы.
+++ А, пардон, там не так просто. Разве что неопределённые коэффициенты попробовать?

[provincialka]

Судя по нику, все действия проводятся по модулю 2.

[provincialka]

Посмотрела внимательнее условие, странное требование, что делимое имеет не более 9 слагаемых, если уже сказано, что степень не больше 7. Тогда и слагаемых не больше 8, или вы что-то другое называете слагаемым?

И в чем вопрос? Как получить еще одно делимое? Или все их перечислить?

[Mikle1990]

provincialka в сообщении #763670 писал(а):

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

Википедия: "При делении с остатком частное может иметь любой знак, но остаток, по соглашению, всегда неотрицателен (иначе он определяется не однозначно)"

provincialka в сообщении #763673 писал(а):

Судя по нику, все действия проводятся по модулю 2.

Это здесь вообще не причём. Я про двоичную систему исчисления ни слова не сказал. При чём здесь это???(риторический вопрос)

provincialka в сообщении #763694 писал(а):

Посмотрела внимательнее условие, странное требование, что делимое имеет не более 9 слагаемых, если уже сказано, что степень не больше 7. Тогда и слагаемых не больше 8, или вы что-то другое называете слагаемым?

Молодец, Вы нашли излишние условие! Но что дальше то? И при чём здесь "или вы что-то другое называете слагаемым"? Если бы так было, то я бы об этом сказал

provincialka в сообщении #763694 писал(а):

И в чем вопрос? Как получить еще одно делимое? Или все их перечислить?

Если я узнаю, как получить ещё одно делимое, то, естественно, посмотрев технику поиска этого делимого, я смогу найти и остальные, если таковые имеются. Вы так говорите, как будто кто-то напишите мне ответ без решения.

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

[DVN]

Произведите обратные действия. Умножте делитель например на x , прибавте остаток, приведите подобные. Мне так кажется.

[gris]

Число $7$ при делении на $6$ имеет остатки $1$ и $-5$. То есть остатки могут иметь разные знаки, но они могут отличаться по абсолютной величине.
У Вас любой полином вида $P(x)=Q(x)\cdot (x^5+x^4+x+1)+(x^4+x+1)$ при делении на $x^5+x^4+x+1$ будет иметь остаток $x^4+x+1$

[provincialka]

mikle1990 Насчет остатка глупости пишете. Это при делении чисел остаток положительный. А многочлен - не число, он разные знаки имеет.
и про двоичную систему я не говорила, а только про сложение по модулю 2. Это совсем другое.

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

-- 14.09.2013, 12:37 --

Mikle1990 в сообщении #763665 писал(а):

Делим полином на полином.

Делимое: $x^5$
Делитель: $x^5+x^4+x+1$
Остаток: $x^4+x+1$

это неверно. Если делить обычно, частное будет 1, остаток - $-x^4-x-1$. Ваш остаток может получиться, только если коэффициенты считать по модулю 2.
так что вы уж определитесь.

[Mikle1990]

gris, т.е. получается, что $Q(x)=[x, x^2]$
И тогда ответом на мой изначальный вопрос будут следующие значения:

$x^6+x^5+x^2+x+x^4+x+1=x^6+x^5+x^4+x^2+2x+1$

$x^7+x^6+x^3+x^2+x^4+x+1=x^7+x^6+x^4+x^3+x^2+x+1$

Два полинома. Правильно?

И ещё вопрос.
$S(x)=x^5\mod x^5+x^4+x+1=-x^4-x-1$ . Правильно?

Если то, что выше, правильно, то остаток от деления искать через формулу
$P(x)=Q(x)\cdot (x^5+x^4+x+1)+(-x^4-x-1)$ ?

Тогда получаем
$P(x)=x^6+x^5+x^2+x-x^4-x-1=x^6+x^5-x^4+x^2-1$
$P(x^2)=x^7+x^6+x^3+x^2-x^4-x-1=x^7+x^6-x^4+x^3+x^2-x-1$

gris, я уверен, что всё правильно. Поэтому очень Вас прошу, напишите, пожалуйста, как всё это дело правильно записать, т.к. у меня есть сомнения относительно моих записей типа $Q(x)=[x, x^2]$ ... $P(x^2) или P_{2}(x)$

[gris]

Вообще-то, я в первом своём сообщении вначале подумал, что речь идёт об обычных многочленах и делении в столбик, но потом увидел, что у Вас речь о CRC кодах. Тогда откуда там возьмутся отрицательные коэффициенты. В той теме у Вас верно было.
То есть

$S(x)=x^5\mod x^5+x^4+x+1=x^4+x+1$ .

$P(x)=x^2\cdot (x^5+x^4+x+1)+(x^4+x+1)=x^7+x^6+x^3+x^2+x+1 (1101111)$ ?

[Mikle1990]

gris, пожалуйста, не покидайте меня

$S(x)$ - синдром вектора ошибки $e=00100000$
$S(x)=x^4+x+1$ ?
$P(x)=Q(x)\cdot (x^5+x^4+x+1)+(?)$

$P_1(x) = ?$
$P_2(x) = ?$

[gris]

Ну Вы даёте. Я имею некоторое представление о сабже, но не настолько, чтобы уверенно консультировать.
Ну просто мы полином второй степени умножаем на образующий и добавляем синдром.
Но Вам же надо найти вектор единичной ошибки с таким же синдромом?

[Mikle1990]

Давайте просто порассуждаем.

В той задаче сказано:
● Найдите вектор ошибки $e^{,}$ с весом больше $1$ , имеющий такой же синдром, как вектор $e$.

Решение
Ошибка $e$ в виде полинома: $e=x^5$
Синдром ошибки $e$: $S(x)= e(x)\mod g(x) = x^5\mod x^5+x^4+x+1=x^4+x+1$
Т.к. мы у всех синдромов ставим положительные коэффициенты, то заметим, что, допустим, синдромы $S(x)=x^4+x+1$ и $S(x)=-x^4-x-1$ - равны. Так?

Найти такой же синдром, значит найти такие значения $e$, при которых остаток от деления будет равен $±x^4±x±1$ - т.е. у нас целых 8 вариантов полинома синдрома, которые в двоичном представлении дают один и тот же синдром. Получается мы имеем $8$ вариантов $P(x)$, каждый из которых даёт по 2 значения $e^{,}$.

Получается, что мы имеем 16 вариантов векторов ошибки $e^{,}$ с весом больше $1$ , имеющий такой же синдром, как вектор $e$.
Вам не кажется это странным?

[gris]

А чего тут странного? Количество полиномов 7 степени в 8 раз больше количества полиномов четвёртой., которые представляют остатки от деления на образующий. Не могут же все они иметь разные остатки. Насчёт отрицательных коэффициентов повторю, что по существу это правильно, но чисто формально вроде бы не принято так писать. Ведь полиномs $x$ и $-x$ соответствуют одному вектору $10$, хотя насчёт некорректности написания я не уверен.
Но дело не в отрицательных коэффициентах. Умножая образующий на $1, x, x^2, x+1, x^2+x+1, x^2+1$ и добавляя $x^4+x+1$, мы получим 6 полиномов 5-7 степени, имеющие этот синдром.
Вес ошибки это что? Я засомневался. Как и в том, откуда отсчитывается номер символа.
То есть $e$ это не (100)?