Решение системы уравнений в поле F16

[vinchkovsky]

Здраствуйте. Есть задание найти общее решение системы уравнений:

$\overline{s}^2$x+$\overline{s}$y=$\overline{1}$
$\overline{s}^3$x+y=$\overline{s}^3$

Как я понимаю, $\overline{s}$ - это корень некоторого неприводимого многочлена четвертого степеня. Т.е., чтобы решить систему, надо знать этот многочлен, так как в процессе возникают четвертые степеня (поэтому и просят найти общее решение?). Но как быть в этом случае? Как узнать, чему равняется, например, $\overline{s}^2$+$\overline{s}^4$ в поле?

Буду благодарен за подсказку алгоритма или поправку. Так же очень хотелось бы посмотреть на пример решения подобных задач где-нибудь в интернете.

[Leox]

vinchkovsky в сообщении #272054 писал(а):

Здраствуйте. Есть задание найти общее решение системы уравнений:

$\overline{s}^2$x+$\overline{s}$y=$\overline{1}$
$\overline{s}^3$x+y=$\overline{s}^3$

Как я понимаю, $\overline{s}$ - это корень некоторого неприводимого многочлена четвертого степеня. Т.е., чтобы решить систему, надо знать этот многочлен, так как в процессе возникают четвертые степеня (поэтому и просят найти общее решение?). Но как быть в этом случае? Как узнать, чему равняется, например, $\overline{s}^2$+$\overline{s}^4$ в поле?

Буду благодарен за подсказку алгоритма или поправку. Так же очень хотелось бы посмотреть на пример решения подобных задач где-нибудь в интернете.

Возьмите любую книгу по алгебраической теории кодирования, там много таких примеров. Насколько я понимаю ситуацию, вам нужно вьіразить все елементьі поля через степени корня неприводимого многочлена. Поетому многочлен нужно знать.

[vinchkovsky]

Спасибо за отклик.

Нет, в условии сказано исследовать систему уравнений и найти ее общее решение.

А если бы был многочлен, то можно было бы выразить $x$ как ($\overline{s}^4$+1)/($\overline{s}^4$+$\overline{s}^2$), выразить числитель и знаменатель через элементы поля, найти обратный элемент к знаменателю и умножить числитель и знаменатель дроби на него, да?

А как быть с таким условием и найти общее решение? Или как понимать задание? Тема, на которой мы остановились - расширение полей.

[Профессор Снэйп]

Вопрос немного не по теме: зачем эти чёрточки сверху? Особенно чёрточка над единицей смущает: это что, не настоящая единица поля, а какой-то другой элемент? Ну и чёрточки над $s$ непонятно какую роль играют.

-- Ср дек 16, 2009 23:59:07 --

Ну и потом. Если $s = 0$, то из первого уравнения $0 = 1$ и система не имеет решений. Пусть $s \neq 0$. Домножая первое уравнение на $s$ и вычитая из него второе, получаем $s^2y - y = s - s^3$. Теперь если $s^2 \neq 1$, то $y = (s - s^3)/(s^2 - 1) = -s$, $s^2x = 1 + s^2$ и $x = s^{-2} + 1$. Если же $s^2 = 1$, то система превращается в

$$ \begin{cases} x + sy = 1 \\ sx + y = s \end{cases} $$

и каждое из уравнений получается домножением другого уравнения на $s$, то есть эти уравнения эквивалентны. $\mathbb{F}_{16}$ --- поле характеристики $2$, так что условию $s^2 = 1$ удовлетворяет только элемент $s = 1$. И получается, что множеством решений будет $\{ \langle x, 1-x \rangle : x \in \mathbb{F}_{16} \}$.

Вроде всё. Что ещё надо?

[vinchkovsky]

Спасибо.

Черточки обозначают элементы фактор-множества.

Цитата:

Если $s = 0$

А разве $\overline{s}$ может быть равным нулю? Если это отдельный от $\overline{0}$ класс эквивалентности из фактор-множества. Тоже самое про $\overline{s}^2$.

Чтобы вычислить это - $x = s^{-2} + 1$ - нужно знать многочлен, корнем которого расширяется поле $\mathbb{F}_{2}$? Или я заблуждаюсь?

Очень прошу, если я ошибаюсь - поправьте меня.

[Профессор Снэйп]

vinchkovsky в сообщении #272127 писал(а):

Черточки обозначают элементы фактор-множества.

Какого ещё фактор-множества? Мы разве где-то что-то факторизовали?

vinchkovsky в сообщении #272127 писал(а):

А разве $\overline{s}$ может быть равным нулю?

А разве в условии где-то сказано, что не может?

vinchkovsky в сообщении #272127 писал(а):

Чтобы вычислить это - $x = s^{-2} + 1$ - нужно знать многочлен, корнем которого расширяется поле $\mathbb{F}_{2}$? Или я заблуждаюсь?

Короче, как у Вас задано $s$?

[vinchkovsky]

Напишу, как примерно у меня в учебнике пишет:

Есть поле $\mathbb{F}_{2}$. Зафиксируем полином $f(x)=x^2+x+1$ и построим отношение эквивалентности: полиномы $u(x)$ и $v(x)$ эквивалентны, если остаток от деления на $f(x)$ одинаковые. ... Элементами фактор-множества будут $\overline{0}$, $\overline{1}$, $\overline{x}$, $\overline{x+1}$. Обозначим s=$\overline{x}$. .... Тогда $\mathbb{F}_{4}$={as+b|a,b є $\mathbb{F}_{2}$.

Это для $\mathbb{F}_{4}$. Для $\mathbb{F}_{16}$, соответственно, нужно взять полином четвертого степеня. $\overline{s}$, насколько я понимаю, обозначает то же самое, что и $\overline{x}$ в описании.

Собственно, мои проблемы - как решить систему уравнений в общем виде, не зная полином (его в условии нету). Если это невозможно - буду благодарен, если кто-то мне скажет об этом.

[Профессор Снэйп]

vinchkovsky в сообщении #272156 писал(а):

Собственно, мои проблемы - как решить систему уравнений в общем виде, не зная полином (его в условии нету). Если это невозможно - буду благодарен, если кто-то мне скажет об этом.

Это невозможно

По-моему, так всё предельно просто. Вам дана система уравнений с параметром $s$, нужно найти зависимость решений этой системы от параметра. Мы её нашли. То есть сделали то, о чём нас просили. Что ещё надо?

Что, в условии сказано, что $s$ --- это полином? Если Вас не устраивает то, что мы сделали, приведите условие полностью, с точностью до буквы, так, как написано у Вас в задачнике. Если есть разобранная задача с похожим условием, приведите и её тоже.

-- Чт дек 17, 2009 01:13:57 --

В конце-концов, если Вам так нужны эти полиномы... Выпишите все классы эквивалентности полиномов, образующие поле $\mathbb{F}_{16}$ и составьте для них таблицу умножения. Потом посмотрите, чему равна минус вторая степень каждого полинома (с точностью до заданной эквивалентности).

Но, ещё раз повторяю, не уверен, что в задаче это требуется.

[Leox]

vinchkovsky в сообщении #272070 писал(а):

Спасибо за отклик.

Нет, в условии сказано исследовать систему уравнений и найти ее общее решение.

А если бы был многочлен, то можно было бы выразить $x$ как ($\overline{s}^4$+1)/($\overline{s}^4$+$\overline{s}^2$), выразить числитель и знаменатель через элементы поля, найти обратный элемент к знаменателю и умножить числитель и знаменатель дроби на него, да?

А как быть с таким условием и найти общее решение? Или как понимать задание? Тема, на которой мы остановились - расширение полей.

Я думаю что вам уже решили уравнение. Для етого вьірожденного случая оказалось что не нужно знать представления поля через корень неприводимого многочлена. Но в общем случае для вьічислений в поле желательно знать тот многочлен которьій использовался для построения расширения $\matbb{Z}_2.$

[Профессор Снэйп]

Leox в сообщении #272190 писал(а):

Я думаю что вам уже решили уравнение. Для етого вьірожденного случая оказалось что не нужно знать представления поля через корень неприводимого многочлена. Но в общем случае для вьічислений в поле желательно знать тот многочлен которьій использовался для построения расширения $\matbb{Z}_2.$

Зачем? Система двух линейных уравнений с двумя неизвестными... Линейная алгебра - она ведь над произвольными полями работает.

[vinchkovsky]

Не сказано. Возможно, действительно условие не совсем понятно (за что я извиняюсь), но у нас $\overline{s}$ всегда обозначал отдельный класс эквивалентности (как $\overline{0}$, $\overline{1}$) поэтому, думаю, тут так же.

В любом случае, ничего больше не надо
Спасибо.

Цитата:

Я думаю что вам уже решили уравнение. Для етого вьірожденного случая оказалось что не нужно знать представления поля через корень неприводимого многочлена.

Согласен. А $s$ - это и есть корень того многочлена (если я все понимаю правильно).

[Leox]

Профессор Снэйп в сообщении #272195 писал(а):

Leox в сообщении #272190 писал(а):

Я думаю что вам уже решили уравнение. Для етого вьірожденного случая оказалось что не нужно знать представления поля через корень неприводимого многочлена. Но в общем случае для вьічислений в поле желательно знать тот многочлен которьій использовался для построения расширения $\matbb{Z}_2.$

Зачем? Система двух линейных уравнений с двумя неизвестными... Линейная алгебра - она ведь над произвольными полями работает.

Да, линейная алгебра, конечно, даст формальньій ответ, но его желательно представить конкретньім єлементом поля, а для єтого нужно знать представление поля через степени корня.
Но, строго говоря, вьі конечно правьі. Как представить ответ єто дело вкуса. Но в теории кодирования, именно возможность представить решение как степень корня играет существенную роль в алгоритмах декодирования.

-- Ср дек 16, 2009 21:35:00 --

vinchkovsky в сообщении #272200 писал(а):

Согласен. А $s$ - это и есть корень того многочлена (если я все понимаю правильно).

Нет, по условию задачи -- єто произвольньій елемент поля.

[AD]

vinchkovsky, в доллары надо заключать всю формулу целиком, а не отдельные буквосочетания. Выглядит красивее, да и тег math при этом писать не нужно. Сравните: $\overline{s}^2$x+$\overline{s}$y=$\overline{1}$ vs. $\overline{s}^2x+\overline{s}y=\overline{1}$