☞ **((:gruppe_e:galois_e:gf_coders English version))** ---- Раздел создан при поддержке компании ((http://www.raidixstorage.com/ru/ RAIDIX)) ---- Вспомогательная страница к разделу ☞ ((:gruppe:galois ПОЛЯ ГАЛУА)). Здесь приводится краткий алгоритм построения поля Галуа --- для тех программистов, которые не хотят забивать свою оперативную память излишней математической теорией, а желают побыстрее добраться до клавиатуры. Всё же немного математики потребуется: полиномы (делимость, неприводимость, алгоритм Евклида), матрицы (и некоммутативность операции их умножения), определители (не очень конструктивный аппарат при практических вычислениях, но такой наглядный!). ---- ==Поле Галуа GF(16) (версия для программистов)== ~~TOC~~ Итак, поле $ \mathbf{GF}(16) $ cостоит из $ 16 $ элементов, которые мы будем обозначать малыми готическими буквами $ \mathfrak a,\mathfrak b, \mathfrak c,\dots $ Каждый из этих элементов --- четырёхразрядная строка (вектор) $ \mathfrak a=(A_0,A_1,A_2,A_3) $ двоичных разрядов $ \{A_j\}_{j=0}^3 \subset \{0,1\} $. Операция сложения --- поразрядная по модулю $ 2_{} $ (**XOR**): $$ \mathfrak a+\mathfrak b=(A_0,A_1,A_2,A_3)\oplus (B_0,B_1,B_2,B_3)= $$ $$ =(A_0+B_0 \pmod {2},A_1+B_1 \pmod {2},\ A_2+B_2 \pmod {2},\ A_3+B_3 \pmod {2}) \ . $$ Сложнее определить операцию умножения. Прежде всего, мы хотим, чтобы результат умножения $ \mathfrak a $ и $ \mathfrak b $ был __снова вектором__ из двоичных разрядов: $$ (A_0,A_1,A_2,A_3)\times (B_0,B_1,B_2,B_3)=(C_0,C_1,C_2,C_3) \in \mathbf{GF}(16) ; $$ т.е. множество $ \mathbf{GF}(16) $ должно быть ((:gruppe#бинарная_операция замкнуто)) относительно операции умножения. Это требование сразу же блокирует желание прибегнуть к ((:euclid_space скалярному произведению)). Векторное же произведение определено только для трехразрядных строк. ===Умножение== Операцию умножения будем вводить "обходным манёвром", привлекая для этой цели аппарат ((:polynomial полиномов)). Берем __пока произвольный__ полином $ f(x)=x^4+a_1x^3+a_2x^2+a_3x+a_4 $ с коэффициентами $ \{a_j\}_{j=1}^4 \subset \{0,1\} $. Существенно, что степень полинома равна именно $ 4_{} $. Каждому вектору поставим в соответствие также по полиному: $$ \begin{array}{lll} \mathfrak a &=(A_0,A_1,A_2,A_3) \mapsto & a(x)= A_0x^3+A_1x^2+A_2x+A_3, \\ \mathfrak b &= (B_0,B_1,B_2,B_3) \mapsto & b(x)= B_0x^3+B_1x^2+B_2x+B_3 \ . \end{array} $$ Перемножим эти полиномы. В результате получаем полином $ a(x)b(x) $ степени $ \le 6 $. Вычислим ((:polynomial#делимость_полиномов остаток от деления)) этого полинома на $ f_{}(x) $: $$ a(x)b(x)\equiv q(x)f(x) + \underbrace{{\tilde c}_0x^3+{\tilde c}_1x^2+{\tilde c}_2x+{\tilde c}_3}_{=r(x)} \ . $$ Здесь $ q_{}(x) $ обозначает частное от деления (и оно нас абсолютно не интересует), а вот как раз коэффициенты остатка $ r_{}(x) $ нам нужны. Заметим, что $ \deg r(x) \le 3 $, т.е. для задания этого полинома нужно определить $ 4_{} $ коэффициента. За счет того, что старший коэффициент полинома $ f_{}(x) $ равен $ 1_{} $, коэффициенты $ r_{}(x) $ будут целыми числами: $ \{ {\tilde c}_j \}_{j=0}^3 \subset \mathbb Z $ (см. ☞ ((:polynomial:remquo ЗДЕСЬ))). Так вот, теперь мы рассматриваем эти коэффициенты по модулю $ 2_{} $, т.е. заменяем четные --- на $ 0_{} $, а нечетные --- на $ 1_{} $. Результат --- $$ \mathfrak c= (c_0,c_1,c_2,c_3)=({\tilde c}_0,{\tilde c}_1,{\tilde c}_2,{\tilde c}_3) \pmod{2} $$ и будем считать **произведением элемента** $ \mathfrak a $ **на элемент** $ \mathfrak b $, записывая этот факт в виде $ \mathfrak c=\mathfrak a \times \mathfrak b $. !!П!! **Пример.** Пусть $$ \mathfrak a=(1,0,1,1), \mathfrak b=(0,1,1,1) \quad \mbox{ и } \ f(x)=x^4+x^3+x \, .$$ Имеем, $ a(x)=x^3+x+1,\ b(x)=x^2+x+1 $ и $$ a(x)b(x) \equiv x^5+x^4+2\,x^3+2\,x^2+2\,x+1 \ . $$ Делим результат на $ f_{}(x) $: $$ \begin{array}{rrrrrrr|l} x^5&+ x^4 &+2x^3 &+2x^2 &+2x &+1 && x^4+x^3+x\\ x^{5}&+x^4&&+x^2&& && \overline{ x \quad } \\ \hline &&2\,x^3&+x^2&+2\,x&+1 \end{array} \qquad \Rightarrow $$ $$ \Rightarrow \quad c(x)= 2\,x^3+x^2+2\,x+1 \Rightarrow \quad \mathfrak a \times \mathfrak b=(0,1,0,1) \ . $$ Заметим, что окончательный результат не изменится, если сразу после вычисления произведения $ a(x)b(x) $ мы осуществим приведение коэффициентов полинома по модулю $ 2_{} $: $$ x^5+x^4+2\,x^3+2\,x^2+2\,x+1 \equiv x^5+x^4+1 \pmod{2} , $$ и остаток от деления последнего полинома на $ f_{}(x) $ будет равен $ x^{2}+1 $. ♦ Дальнейшие упрощения операции умножения по двойному модулю обсуждаются ☞ ((#возведение_в_степень НИЖЕ)). Будем запись $$ u(x) \quad (\operatorname{modd} \ 2,f(x)) $$ понимать в смысле, что мы вычисляем остаток от деления полинома $ u_{}(x) $ на полином $ f_{}(x) $ и во всех этих вычислениях коэффициенты "удерживаем с точностью до четности", т.е. по модулю $ 2_{} $. Будем также говорить об этом остатке как об **остатке по двойному модулю** $ 2,f(x) $. Если мы возьмем другой полином $ f_{}(x) $ четвертой степени, то результат умножения будет другим. Однако при любом выборе, операция умножения будет коммутативна: $ \mathfrak a \times \mathfrak b= \mathfrak b \times \mathfrak a $ --- поскольку коммутативна операция умножения полиномов. В дальнейшем для обозначения операции умножения я вместо $ \times_{} $ буду использовать • или вообще обозначение опускать --- как для обычных чисел. Очевидно, что умножение любого элемента поля на нулевой элемент $ \mathfrak o=(0,0,0,0) $ даст снова нулевой элемент. Очевидно также, что при любом выборе полинома $ f_{}(x) $, элемент $ \mathfrak e=(0,0,0,1) $ будет играть роль единицы относительно умножения: $ \mathfrak e\cdot \mathfrak a = \mathfrak a \cdot \mathfrak e=\mathfrak a $. Действительно, $ a(x)\cdot 1 \equiv a(x) $. Далее, рассмотрим операцию умножения на элемент $ (0,0,1,0) $. $$ a(x) \cdot x \equiv A_0x^4+A_1x^3+A_2x^2+A_3x \equiv $$ $$\equiv A_0f(x)+ (A_1+A_0a_1)x^3+(A_2+A_0a_2)x^2+(A_3+A_0a_3)x+A_0a_4 \quad \Rightarrow $$ $$ \Rightarrow \quad \mathfrak (A_0,A_1,A_2,A_3) \cdot (0,0,1,0) = \left\{ \begin{array}{lr} (A_1,A_2,A_3,0) & npu \ A_0=0, \\ (A_1+a_1,A_2+a_2,A_3+a_3, a_4) \pmod{2} & npu \ A_0=1. \end{array} \right. $$ Иначе говоря, результатом умножения будет либо сдвиг разрядов вектора $ \mathfrak a $ влево, либо тот же сдвиг с прибавлением строки коэффициентов полинома $ f_{} $. !!?!! Проверьте выполнимость свойства дистрибутивности: $ \mathfrak a (\mathfrak b+\mathfrak c)= \mathfrak a \mathfrak b+ \mathfrak a \mathfrak c $. ===Деление== Итак, с операцией умножения проблем не возникает. Хуже обстоит дело с операцией деления. Операция деления векторов нам неизвестна, но вот для полиномов операция деления ((:polynomial#делимость_полиномов имеется)). Так, полином $ x^3+1 $ делится нацело на полином $ x+1 $: $$ \mathfrak a = x^3+1, \mathfrak b=x+1 \quad \Rightarrow \quad \mathfrak a / \mathfrak b = \frac{x^3+1}{x+1}=\frac{(x+1)(x^2-x+1)}{x+1} \equiv x^2-x+1 \equiv_{2} x^2+x+1 \ . $$ Таким образом, можно считать, что $$(1,0,0,1)/(0,0,1,1)=(0,1,1,1) \ . $$ Заметим, что этот результат не будет зависеть от выбора полинома $ f_{}(x) $, задействованного в предыдущем пункте для введения операции умножения. К сожалению, распространение полиномиального деления на все возможные комбинации векторов сталкивается с проблемой: полином $ x^3+1 $ не делится нацело на $ x^2+1 $: $$ x^3+1\equiv x(x^2+1)+(x+1) \ . $$ Либо надо вводить операцию деления векторов "с остатком", либо... А чего, собственно, мы хотим от операции деления? --- А хотим мы, чтобы она любой упорядоченной паре элементов $ \mathfrak a , \mathfrak b $ ставила в соответствие элемент $ \mathfrak c $ так, чтобы $ \mathfrak a= \mathfrak b \cdot \mathfrak c $. Тут же выводится ограничение на выполнимость поставленного требования: $ \mathfrak b \ne \mathfrak o=(0,0,0,0) $. Итак, мы хотим, чтобы множество $ \mathbf{GF}(16) \setminus \mathfrak o $ было ((:gruppe#бинарная_операция замкнуто)) относительно операции деления. Иными словами: хотим иметь аналог свойства делимости целых чисел (или полиномов) без остатка. В только что разобранном примере для пары $ \mathfrak a = (1,0,0,1), \mathfrak b = (0,0,1,1) $ это требование удалось удовлетворить, но мы хотим выполнения его и для переставленной пары: хотим иметь возможность разделить $ \mathfrak b $ на $ \mathfrak a $ --- и в ответе иметь снова вектор! Для решения этой задачи приходится обращаться к операции умножения, введенной в предыдущем пункте. Мы хотим найти элемент $ \mathfrak c_1 $, удовлетворяющий равенству $ \mathfrak b= \mathfrak a \cdot \mathfrak c_1 $. Операция умножения вводится посредством операции умножения по двойному модулю $ 2, f(x) $, где $ f_{}(x) $, выбирается, например, как в предыдущем пункте $ f(x)=x^4+x^3+x $. Тогда полиномиальное представление $ \mathfrak c_1 $ можно попробовать искать методом неопределенных коэффициентов: $$ x+1 \equiv (x^3+1)(\hat c_0 x^3 +\hat c_1 x^2+\hat c_2 x+\hat c_3) \quad (\operatorname{modd} \ 2, x^4+x^3+x) \ . $$ Ну уж операция вычисления остатка от деления полинома на полином нам известна $$ x+1 \equiv (-\hat c_0+\hat c_1-\hat c_2+ \hat c_3)\,x^3+\hat c_0\,x^2+(\hat c_1-\hat c_0)x+\hat c_3 \pmod {2} \ .$$ Полином, стоящий справа, совпадает с полиномом, стоящим слева при условии выполнения системы линейных сравнений: $$ 0\equiv_{2}-\hat c_0+\hat c_1-\hat c_2+ \hat c_3, \ 0 \equiv_{2} \hat c_0,\ 1 \equiv_{2} \hat c_1-\hat c_0,\ 1 \equiv_{2} \hat c_3 \ . $$ Эта система оказывается совместной и имеет единственное решение: $ \hat c_0 =0, \hat c_1=1, \hat c_2=0, \hat c_3=1 $. Таким образом: $$(0,0,1,1)/(1,0,0,1)=(0,1,0,1) \ . $$ Сработает ли подобная схема рассуждений для произвольных элементов $ \mathfrak a $ и $ \mathfrak b $? --- Не обязательно! Возьмем $ \mathfrak a = (0,0,1,1), \mathfrak b=(0,0,1,0) $. Применение метода неопределенных коэффициентов приведет к несовместной системе сравнений. Почему это произошло? Какое условие на выбор полинома $ f_{}(x) $ гарантирует нам выполнимость операции деления для произвольных элементов поля (исключая деление на нулевой элемент)? Для ответа на эти вопросы сведем задачу к более простой: нам, фактически, необходимо выполнять операцию нахождения обратного к элементу $ \mathfrak a $ относительно операции умножения: $ \mathfrak a^{-1} $ для $ \forall \mathfrak a \ne \mathfrak o $. Переведем эту задачу на язык полиномов: $$ 1 \equiv \tilde c(x) a(x) \quad (\operatorname{modd} \ 2, f(x)) $$ что эквивалентно $$ 1 \equiv_{2} \tilde c(x) a(x)+ q(x) f(x) \ ; $$ при некотором полиноме $ q_{}(x) $. Последнее соотношение требует пояснения. Оно представляет собой не просто сравнение по модулю $ 2_{} $, оно представляет собой полиномиальное тождество: полином слева, тождественно равный $ 1_{} $, должен быть равен полиному справа. Следовательно, коэффициенты при одинаковых степенях $ x_{} $ у этих полиномов должны быть одинаковыми. Для отыскания полинома $ f_{}(x) $, который удовлетворяет условию $ c(x) a(x)+ q(x) f(x) \equiv_{2} 1 $ для любого полинома $ a(x)\not\equiv 0 $, $ \deg a(x)\le 3 $, обратимся к теории полиномов над бесконечными полями --- т.е. полиномов с коэффициентами из $ \mathbb R_{} $ или $ \mathbb C_{} $. Для таких полиномов тождество $ c(x) a(x)+ q(x) f(x) \equiv 1 $ известно как ((:polynomial:relat_prime#тождество_безу тождество Безу)). Оно будет иметь место тогда и только тогда, когда полиномы $ f_{}(x) $ и $ a_{}(x) $ взаимно просты, т.е. когда их наибольший общий делитель тождественно равен $ 1_{} $: $ \operatorname{HOD}(f(x),a(x)) \equiv 1 $. Если же мы требуем выполнения последнего условия __для любого__ полинома $ a(x)\not\equiv 0 $, $ \deg a < \deg f $, то это требование приводит к свойству полинома $ f_{}(x) $, известному под названием ((:polynomial#приводимость неприводимость)) над полем $ \mathbb R_{} $ или $ \mathbb C_{} $. Оно означает, что полином $ f_{}(x) $ не делится нацело ни на какой из полиномов меньшей степени, отличный от константы. Так, полином $ f(x)=x^4+x^3+x $, очевидно, не является неприводимым над $ \mathbb R_{} $ и над $ \mathbb C_{} $ : $$ f(x)\equiv x(x^3+x^2+1) ; $$ чем, собственно, и объясняется неудача при попытке использовать этот полином для генерации операции деления в поле $ \mathbf{GF}(16) $. Элементу поля $ \mathfrak b=(0,0,1,0) $ соответствует полином $ b(x)\equiv x $, но тождеству $ c(x) b(x)+ q(x) f(x) \equiv 1 $ не удастся удовлетворить ни при каком выборе полиномов $ c_{}(x) $ и $ q_{}(x) $, поскольку --- при любом выборе этих полиномов --- полином, стоящий в тождестве слева, делится на $ x_{} $, а справа --- на $ x_{} $ не делится. Идем дальше. Свойство неприводимости полинома определяется в зависимости от того множества, над которым мы рассматриваем полином. Если мы имеем дело с полиномами, коэффициенты которых являются целыми числами, и результат операции деления также хотим иметь целочисленным, то неприводимость следует рассматривать над множеством $ \mathbb Z_{} $. Полиномы, неприводимые над множеством $ \mathbb Z_{} $ можно отыскать, их достаточно много --- даже, если мы дополнительно потребуем требуем, чтобы их коэффициенты были из множества $ \{0,1\} $. Вот примеры таких полиномов степени $ 4_{} $: $$ x^4+1,\ x^4+x+1,\ x^4+x^3+1,\ x^4+x^3+x^2+1; $$ но вот полиномы $$ x^4+x^3+x+1,\ x^4+x^2+1,\ x^4+x $$ оказываются приводимыми над $ \mathbb Z_{} $. Итак, свойство неприводимости полинома $ f_{}(x) $ для порождения поля с замкнутостью относительно операции деления является необходимым. Тем не менее, оно не является достаточным. Причина этого заключается в том, что мы накладываем дополнительное условие на коэффициенты рассматриваемых полиномов --- все они равны $ 0_{} $ или $ 1_{} $. И тождество Безу следует рассматривать по модулю $ 2_{} $. Иными словами, полином $ f_{}(x) $ может быть неприводимым над $ \mathbb Z_{} $, но выполнения тождества $$ c(x) a(x)+ q(x) f(x) \equiv 1 $$ не удастся добиться ни при каких $ c_{}(x) $ и $ q_{}(x) $ если мы все коэффициенты полинома слева усечем по модулю $ 2_{} $. Так, к примеру, для пары полиномов $ f(x)=x^4+1, a(x)=x+1 $ последнее тождество не будет выполнено: при подстановке $ x=1 $ получим $ 2\,c(x)+2\, q(x) \equiv_2 0 $, а не $ 1_{} $, как мы желали бы. Поэтому из множества неприводимых над $ \mathbb Z_{} $ полиномов степени $ 4_{} $ с коэффициентами $ 0_{}^{} $ или $ 1_{} $, мы должны выбрать полиномы, дополнительно неприводимые по модулю $ 2_{} $. Из приведенных выше примеров неприводимых над $ \mathbb Z $ полиномов, приходится отбрасывать следующие: $$ x^4+1 \equiv_{2} (x^2+1)^2 \equiv_{2} (x+1)^4,\ x^4+x^3+x^2+1 \equiv_{2} (x+1)(x^3+x+1) \ . $$ Тотальным перебором можно убедиться, что существует всего только $ 3_{} $ полинома степени $ 4_{} $ неприводимых по модулю $ 2_{} $: $$ x^4+x+1,\ x^4+x^3+1,\ x^4+x^3+x^2+x+1 \ . $$ ---- Доказывается, что существуют неприводимые полиномы любой степени; для каждой степени известно их количество. Отдельная проблема --- построение этих полиномов достаточно больших степеней ( $ 64, 128 $ и т.п.) Пока можно оценить сложность задачи на примере нахождения таких полиномов $ 6_{} $-й степени ☞ ((:gruppe:galois:vspom1 ЗДЕСЬ)), а общие подходы попозже опишу. Причем с точки зрения приложений в теории помехоустойчивого кодирования, интерес представляют **разреженные** неприводимые полиномы, т.е. полиномы с большим количеством нулевых коэффициентов. См. примеры таких полиномов ☞ ((:gruppe:galois:vspom6 ЗДЕСЬ)). Построение поля $ \mathbf{GF}(16) $ завершено. Операция деления в этом поле будет определена, если порождающим полиномом для определения операции умножения выбрать любой из трех приведенных выше. Осталось только привести алгоритм вычисления частного. Поскольку операция деления $ \mathfrak b / \mathfrak a $ сводится к операции умножения $ \mathfrak b \cdot \mathfrak a^{-1} $, то возвращаемся к тождеству Безу, которое и позволило нам ввести операцию нахождения $$ (A_0x^3+A_1x^2+A_2x+A_3)^{-1} \quad (\operatorname{modd} \ 2, f(x)) \ . $$ Имеются различные алгоритмы решения этого тождества. Они абсолютно конструктивны, но, к сожалению, громоздки в изложении. Самый главный из них основан на ((:polynomial:relat_prime#тождество_безу алгоритме Евклида)) вычисления наибольшего общего делителя полиномов $ f_{}(x) $ и $ a_{}(x) $. Собственно сам $ \operatorname{HOD} (f(x),A_0x^3+A_1x^2+A_2x+A_3) $ нас не интересует: при любых значениях коэффициентов $ \{A_j\}_{j=0}^3 $ он будет равен $ 1_{} $. Откуда такая уверенность? --- Она вытекает из неприводимости полинома $ f_{}(x) $. А интересуют нас выражения для частных из алгоритма Евклида вычисления этого (уже предсказанного) $ \operatorname{HOD} $. !!П!! **Пример.** Для $ f(x)=x^4+x+1, a(x)=x^3+x+1 $ имеем: $$ \left. \begin{array}{lcl} f(x) &\equiv & x\cdot a(x) + (x^2+1); \\ a(x) &\equiv & x \cdot (x^2+1)+ 1 \end{array} \right\} \pmod{2} $$ Единица в последней формуле и представляет значение $ \operatorname{HOD} (f(x),a(x)) $. На основании получившихся частных: $$ q_1(x)=x,\ q_2(x)=x, $$ составляем ((:numtheory#линейное_представление_нод континуанту)): $$ b(x)= q_1q_2+1=x\cdot x +1 \equiv_{_2} x^2+1 \ . $$ Проверяем: $$ (x^3+x+1)(x^2+1) \equiv x^5+2\,x^3+x^2+x+1 \equiv 1 \quad (\operatorname{modd} \ 2,f(x)) \ . $$ Итак, обратный к элементу поля $ \mathfrak a=(1,0,1,1) $ относительно умножения по двойному модулю равен $ (0,1,0,1) $. Этот элемент определяется единственным образом. Если хочется получить универсальное его представление --- для произвольного $ \mathfrak a= (A_0,A_1,A_2,A_3) $ и произвольного $ f(x)=x^4+a_1x^3+a_2x^2+a_3x+a_4 $, а континуанта кажется слишком сложным объектом, могу предложить альтернативную форму записи --- посредством ((:dets:resultant:idea#результант_и_наибольший_общий_делитель_полиномов определителя)): $$ b(x)= \left|\begin{array}{ccccccl} 1&a_1&a_2&a_3&a_4& & \\ &1&a_1&a_2&a_3&a_4&\\ &&1&a_1&a_2&a_3&0\\ &&&A_0&A_1&A_2&1\\ &&A_0&A_1&A_2&A_3&x\\ &A_0&A_1&A_2&A_3&0&x^2\\ A_0&A_1&A_2&A_3&0&0&x^3 \end{array}\right|_{7\times 7} \pmod{2} , $$ (все неуказанные элементы считаются равными нулю). ((:algebra2:dets#миноры_и_алгебраические_дополнения Разложите)) определитель по последнему столбцу --- миноры $ 6_{} $-го порядка, соответствующие $ x^3,x^2,x,1 $ и будут формировать $ \mathfrak a^{-1} $. Слишком велик порядок определителя? --- Уменьшим его до порядка равного $ \deg f_{} $. Вычисляем $$ a(x),\ x\cdot a(x),\ x^2 \cdot a(x),\ x^3 \cdot a(x) \quad (\operatorname{modd} \ 2,f(x)) \ , $$ что можно организовать рекурсивно, положив $ a_0(x)\equiv a(x)= A_0x^3+A_1x^2+A_2x+A_3 $: $$ \left. \begin{array}{lll} a_1(x)\equiv x a_0(x) & \equiv & K_0x^3+K_1x^2+K_2x+K_3,\\ a_2(x)\equiv x a_1(x) & \equiv & L_0x^3+L_1x^2+L_2x+L_3 ,\\ a_3(x)\equiv x a_2(x) & \equiv & M_0x^3+M_1x^2+M_2x+M_3 \ , \end{array} \right\} \quad (\operatorname{modd} \ 2,f(x)) \ . $$ Составляем из коэффициентов полиномов $ \{a_j(x) \}_{j=0}^3 $ матрицу $ 4_{} $-го порядка: $$ \mathbf{A}= \left(\begin{array}{llll} M_0 & M_1 & M_2 & M_3 \\ L_0 & L_1 & L_2 & L_3 \\ K_0 & K_1 & K_2 & K_3 \\ A_0 & A_1 & A_2 & A_3 \end{array} \right) $$ заменяем последний столбец на $ [x^3,x^2,x,1]^{\top} $. Вычислим определитель --- он и будет искомым полиномом. Так, для настоящего примера имеем: $$ \mathfrak a=a_0(x)=x^3+x+1,\ a_1(x)=x^2+1,\ a_2(x)=x^3+x,\ a_3(x)=x^2+x+1 $$ и $$ \mathfrak a^{-1}= \left|\begin{array}{cccl} 0 & 1 & 1 & x^3 \\ 1 & 0 & 1 & x^2 \\ 0 & 1 & 0 & x \\ 1 & 0 & 1 & 1 \end{array} \right| \pmod{2} . $$ ♦ Матрица $ \mathbf A_{} $ из последнего примера снова возникнет в одном из последующих ☟ ((#матрицы ПУНКТОВ)). Подведем итог: в конечном поле $ \mathbf{GF}(16) $ операцию умножения можно ввести тремя разными способами --- в зависимости от выбора неприводимого по модулю $ 2_{} $ полинома $ 4_{} $-й степени. Назовем этот полином **порождающим полиномом** поля. В дальнейшем, в настоящем разделе, говоря о неприводимом полиноме, будем иметь в виду именно свойство неприводимости по модулю $ 2_{} $. Имеется ли принципиальное различие между тремя полями, порождаемыми тремя неприводимыми полиномами? --- Оказывается, нет. Можно доказать, что поля Галуа одного порядка все ((:gruppe#кольцо изоморфны)), т.е. между любыми двумя такими полями можно установить взаимно-однозначное соответствие их элементов и при этом соответствие такое, что будут сохраняться результаты операций сложения и умножения. Проверку этого утверждения для $ \mathbf{GF}(16) $ см. ☞ ((:gruppe:galois:vspom3 ЗДЕСЬ)). !!П!! **Пример.** Для поля $ \mathbf{GF}(16) $, порожденного полиномом $ f(x)=x^4+x+1 $, определить частное от деления элемента $ \mathfrak b = (0,0,1,1) $ на элемент $ \mathfrak a= (1,1,1,1) $. **Решение.** Здесь $ a(x)=x^3+x^2+x+1, b(x)=x+1 $. Имеем: тождество Безу $$ u(x)a(x)+v(x) f(x) \equiv 1 $$ (по модулю $ 2_{} $) будет выполнено при $ u(x)=x^3, v(x)=... $ Таким образом, $$ a^{-1}(x) \quad (\operatorname{modd} \ 2,f(x)) = x^3 $$ и $$ b(x) a^{-1}(x) \quad (\operatorname{modd} \ 2,f(x)) = x^3+x+1 \ \Rightarrow \ \mathfrak c= \mathfrak b / \mathfrak a = (1,0,1,1) . $$ ♦ ===Возведение в степень== Итак, с операцией умножения разобрались. Почти разобрались. --- Дело в том, что имеется один неожиданный момент, который не имеет аналогов в теории полиномов над бесконечными полями. Рассмотрим произвольный элемент $ \mathfrak a \ne \mathfrak o $ поля и начнем возводить его в степени: $$ \mathfrak a^{0}=\mathfrak e, \mathfrak a^{1}, \mathfrak a^2,\dots $$ Все элементы этой последовательности будут элементами поля $ \mathbf{GF}(16) $. Но, поскольку последних --- __конечное число__, то последовательность через некоторое количество шагов должна выйти на цикл. !!П!! **Пример.** Для $ f(x)=x^4+x+1 $ имеем: $$ \begin{array}{ll} npu \quad a(x)=x^3+x+1: & 1,\ x^3+x+1,\ x^3+1, x^3+x^2,\ x^3+x^2+1,\ x^2+x,\ x^3+x^2+x+1, \\ & x+1,\ x^3+x^2+x,\ x^3,\ x^2+x+1,\ x^2,\ x^3+x,\ x,\ x^2+1,\ 1,\dots \\ npu \quad a(x)=x^2+x+1: & 1,\ x^2+x+1,\ x^2+x,\ 1,\dots \\ npu \quad a(x)=x^3+x: & 1,\ x^3+x,\ x^3,\ x^3+x^2+x+1,\ x^3+x^2,\ 1,\dots \end{array} $$ Можно проверить, что для любого элемента поля (кроме единичного) его степени будут периодическими последовательностями с длинами циклов равными одному из чисел $ \{3,5,15\} $. Что это за числа? --- Это делители числа $ 2^4-1 $. ♦ Это --- проявление общего правила для конечного поля. Поскольку оно (после выбрасывания нулевого элемента) образует ((:gruppe#подгруппа группу)) относительно умножения, то порядок этой группы должен делиться на порядок любого ее элемента. Гарантированно будет выполнено равенство $$ \mathfrak a^{15}=\mathfrak e \quad npu \quad \forall a \ne \mathfrak o \ , $$ (в общем случае известное под названием ((:gruppe:galois#обобщенная_теорема_ферма обобщенной теоремы Ферма)) ). Нас будет очень интересовать порождающий элемент этой группы --- тот, степени которого пробегают по __всем__ ненулевым элементам поля. Этот элемент называется **примитивным** элементом поля. ((:gruppe:galois:vspom2 Доказывается)), что эти элементы всегда существуют, известно их число --- и это число не зависит от выбора полинома $ f_{}(x) $. Так, для поля $ \mathbf{GF}(16) $ число примитивных элементов равно $ \phi(15)= 8 $; здесь $ \phi_{} $ обозначает ((:numtheory#функция_эйлера функцию Эйлера)). В приведенном выше примере элемент $ (1,0,1,1) $ будет примитивным, а элементы $ (0,1,1,1) $ или $ (1,0,1,0) $ примитивными не будут. Выражения для примитивных элементов __будут зависеть от выбора__ порождающего поле полинома $ f_{}(x) $. Обозначим какой-то из этих примитивных элементов через $ \mathfrak A $. Для заданного элемента $ \mathfrak a \ne \mathfrak o $ поля найдем __минимально возможный__ показатель степени $ k \in \mathbb N $ такой, что $ \mathfrak A^k= \mathfrak a $. Этот показатель $ k_{} $ называют **дискретным логарифмом** элемента $ \mathfrak a $ **по основанию** примитивного элемента $ \mathfrak A $. Плохо только, что, в отличие от своего непрерывного аналога, дискретный логарифм ведет себя совершенно хаотичным образом и выписать его выражение в общем виде --- т.е. в виде явной функции разрядов элемента $ \mathfrak a=(A_0,A_1,A_2,A_3) $ весьма затруднительно. !!П!! **Пример.** $ f(x)=x^4+x+1 $. Через $ \mathfrak A $ обозначен элемент поля $ (0,0,1,0)=x $. ---- "Таблица логарифмов". $$ \begin{array}{l|rrrr|c|c|c} \mathfrak A^0 & & & & \mathfrak e & 0001 & & \\ \mathfrak A^1 & & & \mathfrak A & & 0010 & \Pi & f=0 \\ \mathfrak A^2 & & \mathfrak A^2 & & & 0100 & \Pi & f=0 \\ \mathfrak A^3 & \mathfrak A^3 & & & & 1000 & & f_3=0 \\ \hline \mathfrak A^4 & & & \mathfrak A & +\mathfrak e & 0011 & \Pi & f=0 \\ \mathfrak A^5 & & \mathfrak A^2 & +\mathfrak A & & 0110 & & f_4=0 \\ \mathfrak A^6 & \mathfrak A^3 & +\mathfrak A^2 & & & 1100 & & f_3=0\\ \mathfrak A^7 & \mathfrak A^3 & & + \mathfrak A & +\mathfrak e & 1011 & \Pi & f^{\ast}=0 \\ \hline \mathfrak A^8 & & \mathfrak A^2 & & +\mathfrak e & 0101 & \Pi & f=0 \\ \mathfrak A^9 & \mathfrak A^3 & & +\mathfrak A & & 1010 & & f_3=0 \\ \mathfrak A^{10} & & \mathfrak A^2 &+\mathfrak A & +\mathfrak e & 0111 & & f_4=0 \\ \mathfrak A^{11} & \mathfrak A^3 & +\mathfrak A^2 & +\mathfrak A & & 1110 & \Pi & f^{\ast}=0 \\ \hline \mathfrak A^{12} & \mathfrak A^3 & +\mathfrak A^2 & + \mathfrak A& +\mathfrak e & 1111 & & f_3=0 \\ \mathfrak A^{13} & \mathfrak A^3 & +\mathfrak A^2 & & +\mathfrak e & 1101 & \Pi & f^{\ast}=0 \\ \mathfrak A^{14} & \mathfrak A^3 & & & +\mathfrak e & 1001 & \Pi & f^{\ast}=0 \end{array} $$ Обоснование таблицы ☞ ((:gruppe:galois:vspom3 ЗДЕСЬ)). ---- Получается, что действительно, $ \mathfrak A=x $ является примитивным элементом поля. В четвертом столбце отмечены все примитивные элементы поля. На последний столбец пока не обращаем внимания. Удивительно то, что элементы второго столбца таблицы не изменятся, если взять в качестве $ \mathfrak A $ любой из элементов $ x^2, x^4, x^8 $. Поскольку это поле часто использую для иллюстраций, приведу еще одну таблицу --- для степенных представлений элементов: ---- "Таблица сложения". $$ \begin{array}{l||l|l|l|l|l|l|l|l|l|l|l|l|l|l|l} & \mathfrak A^0 & \mathfrak A^1 & \mathfrak A^2 & \mathfrak A^3 & \mathfrak A^4 & \mathfrak A^5 & \mathfrak A^6 & \mathfrak A^7 & \mathfrak A^8 & \mathfrak A^9 & \mathfrak A^{10} & \mathfrak A^{11} & \mathfrak A^{12} & \mathfrak A^{13} & \mathfrak A^{14} \\ \hline \hline \mathfrak A^0 & \mathfrak o & \mathfrak A^4 & \mathfrak A^8 & \mathfrak A^{14} & \mathfrak A & \mathfrak A^{10} & \mathfrak A^{13} & \mathfrak A^{9} & \mathfrak A^{2} & \mathfrak A^{7} & \mathfrak A^{5} & \mathfrak A^{12} & \mathfrak A^{11} & \mathfrak A^{6} & \mathfrak A^{3} \\ \hline \mathfrak A^1 & & \mathfrak o & \mathfrak A^5 & \mathfrak A^9 & \mathfrak A^0 & \mathfrak A^2 & \mathfrak A^{11} & \mathfrak A^{14} & \mathfrak A^{10} & \mathfrak A^{3} & \mathfrak A^{8} & \mathfrak A^{6} & \mathfrak A^{13} & \mathfrak A^{12} & \mathfrak A^{7} \\ \hline \mathfrak A^2 & & & \mathfrak o & \mathfrak A^{6} & \mathfrak A^{10} & \mathfrak A^{1} & \mathfrak A^{3} & \mathfrak A^{12} & \mathfrak A^0 & \mathfrak A^{11} & \mathfrak A^{4} & \mathfrak A^{9} & \mathfrak A^{7} & \mathfrak A^{14} & \mathfrak A^{13} \\ \hline \mathfrak A^3 & & & & \mathfrak o & \mathfrak A^{7} & \mathfrak A^{11} & \mathfrak A^{2} & \mathfrak A^{4} & \mathfrak A^{13} & \mathfrak A^{1} & \mathfrak A^{12} & \mathfrak A^{5} & \mathfrak A^{10} & \mathfrak A^{8} & \mathfrak A^0 \\ \hline \mathfrak A^4 & & & & & \mathfrak o & \mathfrak A^8 & \mathfrak A^{12} & \mathfrak A^3 & \mathfrak A^5 & \mathfrak A^{14} & \mathfrak A^2 & \mathfrak A^{13} & \mathfrak A^6 & \mathfrak A^{11} & \mathfrak A^9 \\ \hline \mathfrak A^5 & & & & & & \mathfrak o & \mathfrak A^9 & \mathfrak A^{13} & \mathfrak A^4 & \mathfrak A^6 & \mathfrak A^0 & \mathfrak A^3 & \mathfrak A^{14} & \mathfrak A^7 & \mathfrak A^{12} \\ \hline \mathfrak A^6 & & & & & & & \mathfrak o & \mathfrak A^{10} & \mathfrak A^{14} & \mathfrak A^{5} & \mathfrak A^{7} & \mathfrak A & \mathfrak A^{4} & \mathfrak A^{0} & \mathfrak A^{8} \\ \hline \mathfrak A^7 & & & & & & & & \mathfrak o & \mathfrak A^{11} & \mathfrak A^0 & \mathfrak A^{6} & \mathfrak A^{8} & \mathfrak A^2 & \mathfrak A^{5} & \mathfrak A \\ \hline \mathfrak A^8 & & & & & & & & & \mathfrak o & \mathfrak A^{12} & \mathfrak A & \mathfrak A^{7} & \mathfrak A^{9} & \mathfrak A^{3} & \mathfrak A^{6} \\ \hline \mathfrak A^9 & & & & & & & & & & \mathfrak o & \mathfrak A^{13} & \mathfrak A^{2} & \mathfrak A^{8} & \mathfrak A^{10} & \mathfrak A^{4} \\ \hline \mathfrak A^{10} & & & & & & & & & & & \mathfrak o & \mathfrak A^{14} & \mathfrak A^{3} & \mathfrak A^{9} & \mathfrak A^{11} \\ \hline \mathfrak A^{11} & & & & & & & & & & & & \mathfrak o & \mathfrak A^0 & \mathfrak A^{4} & \mathfrak A^{10} \\ \hline \mathfrak A^{12} & & & & & & & & & & & & & \mathfrak o & \mathfrak A^{1} & \mathfrak A^{5} \\ \hline \mathfrak A^{13} & & & & & & & & & & & & & & \mathfrak o & \mathfrak A^{2} \\ \hline \mathfrak A^{14} & & & & & & & & & & & & & & & \mathfrak o \end{array} $$ ♦ Беглый взгляд на обе приведенные таблицы вызывает ощущение хаотичности их формирования. В самом деле, для обычного (классического) логарифма по произвольному основанию, например $ \log_{2} a $, имеет место хотя бы непрерывность по $ a_{} $: если значение $ \log_{2} a $ известно, то $ \log_{2}(a+1) $ находится "где-то рядом". Для дискретного логарифма этой предсказуемости в помине нет. И в этом заключается основная проблема использования аппарата дискретных логарифмов. Подведем итоги: любой ненулевой элемент поля $ \mathbf{GF}(16) $ имеет три представления (ипостаси[[$ \upsilon \pi $''ó''$ \sigma \tau \tilde{\alpha} \sigma \iota \varsigma $ (//др.греч.//) --- сущность.]]): 1. Это --- строка, элемент векторного пространства $ (A_0, A_1, A_2, A_3) $. 2. Это --- полином $ A_0x^3+ A_1x^2+A_2x+ A_3 $. 3. Это --- некоторая степень $ \mathfrak A^k $ примитивного элемента поля. Какое из этих представлений использовать --- зависит от конкретной задачи. Так, складывать проще элементы поля в их представлении в виде 1 или 2 (в сравнении с альтернативным вариантом, представленным последней таблицей). С другой стороны, если известна таблица представлений любого элемента $ (A_0, A_1, A_2, A_3) $ поля по степеням примитивного (типа первой из приведенных в последнем примере), то операцию умножения кажется проще выполнять с элементами поля в виде 3 : $$ \quad \mathfrak a= (A_0, A_1, A_2, A_3) = \mathfrak A^k,\ \mathfrak b= (B_0, B_1, B_2, B_3) = \mathfrak A^{\ell} \quad \Rightarrow \quad \mathfrak a \cdot \mathfrak b = \mathfrak A^{k+\ell} \ . $$ Показатель $ k+\ell $ берется "честно" при $ k+\ell<15 $ и по модулю $ 15_{} $ при $ k+\ell\ge 15 $. Замечание для тех, кто заканчивал школу "во времена далёкие, уже почти забытые": принцип работы тот же, что и при работе с таблицами логарифмов Брадиса. !!П!! **Пример**. Разберем еще раз алгоритм умножения элементов $ \mathfrak a=(A_0,A_1,A_2,A_3) $ и $ \mathfrak b=(1,1,0,1) $ при $ f(x)=x^4+x+1 $. **Решение** 1 . Умножение соответствующих полиномов $ a(x)=A_0x^3+A_1x^2+A_2x+A_3 $ и $ b(x)=x^3+x^2+1 $ ((:polynomial#общая_информация традиционно производится)) "в столбик": {{ gruppe:galois:multipic.jpg |}} Фактически, за счет того, что разрядами элемента $ \mathfrak b $ являются либо $ 0_{} $, либо $ 1_{} $, умножение сводится к действию исключительно только со строкой $ (A_0,A_1,A_2,A_3) $ --- она может быть "сдвинута" на одну или более позиций влево по отношению к предыдущей строке. Стоящие друг под другом разряды суммируются по модулю $ 2_{} $ (без переноса результата в следующий разряд[["С выключенными цепями переносов"]]). Заметим, что полученный результат --- произведение полиномов $ a(x) b(x) $ --- еще не является окончательным, поскольку конечной целью является остаток от деления этого произведения на $ f_{}(x) $ (по модулю $ 2_{} $). Исходя из этой цели, имеет смысл организовать умножение по другой схеме: $$ a(x)(B_0x^3+B_1x^2+B_2x+B_3)= (a(x)B_0)x^3+(a(x)B_1)x^2+(a(x)B_2)x+(a(x)B_3)= $$ $$=\left\{\left[\left(a(x)B_0 \right)\cdot x +a(x)B_1 \right]\cdot x+a(x)B_2 \right\}\cdot x+a(x)B_3 $$ $$=\left\{\left[\left(a(x)\cdot x\right) + a(x) \right]\cdot x+0 \right\}\cdot x+a(x) \ , $$ а результат каждой последовательно вычисленной операции $ \big( \ast \big)\cdot x $, $ \big[ \ast \big]\cdot x $, $ \big\{ \ast \big\}\cdot x $ "усекать" по модулю $ 2,f(x) $: $$ a(x) b(x) \quad (\operatorname{modd} \ 2,f(x)) =$$ $$= \left\{\left[\left(a(x)\cdot x \quad (\operatorname{modd} \ 2,f(x)) \right) + a(x) \right]\cdot x \quad (\operatorname{modd} \ 2,f(x)) \right\}\cdot x \quad (\operatorname{modd} \ 2,f(x)) +a(x) \ . $$ Тем более, что операция умножения на полином $ x_{} $ по двойному модулю $ 2,f(x) $ допускает простую программную реализацию (см. концовку пункта ☞ ((#УМНОЖЕНИЕ)) ). !!?!! Вопрос для тех, кто у меня учился: вам ничего этот алгоритм не напоминает? **Решение** 2 . Тот же самый пример решим с помощью таблицы из предыдущего примера. Итак, $ \mathfrak b=(1,1,0,1)= \mathfrak A^{13} $; аналогичное представление для элемента $ \mathfrak a $ можно получить только при конкретном его выборе. Пусть, к примеру, $ \mathfrak a=(1,0,1,1) $. Тогда $ \mathfrak a = \mathfrak A^{7} $. Имеем, следовательно, $$ \mathfrak a \cdot \mathfrak b=\mathfrak A^{7}\cdot \mathfrak A^{13}=\mathfrak A^{20}=\mathfrak A^{5} \ , $$ и, снова подсмотрев в таблицу, получаем $ (0,1,1,0) $. ♦ А как упрощается для степенного представления элемента его обращение! ^_^ --- В самом деле: $$ \mathfrak a^{15} = \mathfrak e \quad \Rightarrow \quad \mathfrak a^{-1}=\mathfrak a^{14},\ \mathfrak a^{-2}=\mathfrak a^{13},\dots \quad npu \quad \forall \mathfrak a \ne \mathfrak o \ . $$ Словом, наличие заранее вычисленной "таблицы логарифмов" существенно упрощает жизнь вычислителю. Хуже, если такой таблицы нет или вычисление (хранение) ее слишком затратно... !!П!! **Пример.** Здесь для иллюстрации возьму поле побольше[[<> (Кто-то из классиков ;-)).]], именно $ \mathbf{GF}(64) $. Вычислить $$ x^{-11} \quad (\operatorname{modd} \ 2,x^6+x^5+1) \, .$$ **Решение.** Полином $ f_{}(x)=x^6+x^5+1 $ --- неприводимый, а $ x_{} $ --- примитивный элемент поля $ \mathbf{GF}(64) $ (см. ☞ ((:gruppe:galois:vspom1 ЗДЕСЬ)) ), по обобщенной теореме Ферма имеем $ x^{-11} \equiv x^{2^6-1-11}\equiv x^{52} \quad (\operatorname{modd} \ 2,x^6+x^5+1) $. Далее используем идею ((:modular#вычисление_остатков_степенных_выражений алгоритма квадрирования-умножения)): переводим $ 52 $ в двоичную систему счисления $ \underline{52}_{_{10}}=\underline{110100}_{_2} $ и начинаем вычислять остатки $$ \begin{array}{|c|c|c|c|c|c|c|} \hline j & 1 & 2 & 3 & 4 & 5 &6 \\ \hline 52 & 1 & 1 & 0 & 1 & 0 &0 \\ \hline r_j(x) & x & x^2\times x & x^6 & (x^5+1)^2\times x & (x^4+x^3+x^2+1)^2 & (x^4+x^2+x+1)^2 \\ & \equiv_{_{2,f}} x & \equiv_{_{2,f}} x^3 & \equiv_{_{2,f}} x^5+1 & \equiv_{_{2,f}} x^4+x^3+x^2+1 & \equiv_{_{2,f}} x^4+x^2+x+1 & \equiv_{_{2,f}} x^5+x^4+x \\ \hline \end{array} $$ **Ответ.** $ x^5+x^4+x $. ===Уравнения линейные== Пусть заданы элементы поля $ \mathfrak a_1,\dots,\mathfrak a_N, \mathfrak b $. **Линейным уравнением** над полем $ \mathbf{GF}(16) $ относительно неизвестных $ \mathfrak x_1,\dots,\mathfrak x_N $ назовем $$ \mathfrak a_1 \mathfrak x_1+\dots+\mathfrak a_N \mathfrak x_N = \mathfrak b \ . $$ Этот объект вполне определен, поскольку определена операция умножения. Решением уравнения в поле $ \mathbf{GF}(16) $ назовем любой набор элементов из $ \mathbf{GF}(16) $ $$ \mathfrak x_1=\alpha_1,\dots, \mathfrak x_N=\alpha_N \ , $$ обращающий уравнение в верное равенство. **Системой линейных уравнений** над $ \mathbf{GF}(16) $ называется совокупность (набор) из нескольких уравнений от одного и того же набора переменных (неизвестных) $ \mathfrak x_1,\dots,\mathfrak x_N $: $$ \left\{ \begin{array}{lllll} \mathfrak a_{11} \mathfrak x_1 &+\mathfrak a_{12}\mathfrak x_2&+ \ldots&+\mathfrak a_{1N}\mathfrak x_N &=\mathfrak b_1,\\ \mathfrak a_{21}\mathfrak x_1 &+\mathfrak a_{22}\mathfrak x_2&+ \ldots&+\mathfrak a_{2N}\mathfrak x_N &=\mathfrak b_2,\\ \dots & & & & \dots \\ \mathfrak a_{M1}\mathfrak x_1 &+\mathfrak a_{M2}\mathfrak x_2&+ \ldots&+\mathfrak a_{MN}\mathfrak x_N &=\mathfrak b_M. \end{array} \right. $$ Здесь $ \left\{\mathfrak a_{j k} \right\}_{j=1,\dots,M \atop k=1,\dots,N } $ и $ \{ \mathfrak b_{j} \}_{j=1,\dots,M} $ --- фиксированные элементы поля $ \mathbf{GF}(16) $; они называются **коэффициентами системы**. Посмотрим, насколько переносимы в конечное поле результаты, полученные для ((:algebra2:linearsystems систем уравнений над бесконечными полями)) ($ \mathbb Q, \mathbb R_{} $ или $ \mathbb C_{} $). Прежде всего, отметим, что один из сценариев, возможных для бесконечных полей, неактуален для полей конечных: система уравнений над конечным полем не может иметь бесконечного множества решений. Поэтому теоретически допустим способ решения системы линейных уравнений, заключающийся в простом переборе всех возможных комбинаций из $ 16_{} $ элементов поля. Так, для системы из двух уравнений от двух неизвестных $$ \left\{ \begin{array}{lcl} \mathfrak a_{11} \mathfrak x_1 +\mathfrak a_{12}\mathfrak x_2 &= & \mathfrak b_1, \\ \mathfrak a_{21} \mathfrak x_1 +\mathfrak a_{22}\mathfrak x_2 &= & \mathfrak b_2 \end{array} \right. $$ надо проверить $ 16^2 $ комбинаций $ (\mathfrak x_1,\mathfrak x_2) $. Отложив этот способ "про запас" --- ввиду очевидной его неконструктивности, обратимся к другим, которые можно перенести из бесконечных полей. Справедливы ли ((:algebra2:linearsystems#формулы_крамера формулы Крамера))? --- Умножим первое уравнение системы на $ \mathfrak a_{22} $ и вычтем из него ( $ \equiv_{_2} $ прибавим к нему) второе, умноженное на $ \mathfrak a_{12} $: $$ \overbrace{(\mathfrak a_{11}\mathfrak a_{22}- \mathfrak a_{12} \mathfrak a_{21})}^{\Delta}\mathfrak x_1= \overbrace{\mathfrak a_{22} \mathfrak b_1 - \mathfrak a_{12} \mathfrak b_2}^{\Delta_1} \ . $$ Аналогично: $$ (\mathfrak a_{11}\mathfrak a_{22}- \mathfrak a_{12} \mathfrak a_{21})\mathfrak x_2= \overbrace{-\mathfrak a_{21} \mathfrak b_1 + \mathfrak a_{11} \mathfrak b_2}^{\Delta_2} \ . $$ Если элемент поля $ \Delta= \mathfrak a_{11}\mathfrak a_{22}- \mathfrak a_{12} \mathfrak a_{21} $ отличен от нулевого, то у него существует обратный и, следовательно, решение системы уравнений единственно и оно записывается в виде $$ \mathfrak x_1=\Delta_1\cdot \Delta^{-1},\quad \mathfrak x_2=\Delta_2\cdot \Delta^{-1} \ . $$ !!П!! **Пример.** Решить систему уравнений $$ \left\{ \begin{array}{lcl} (0,1,0,0) \mathfrak x_1 +(0,1,0,1)\mathfrak x_2 &= & (1,0,0,0), \\ (1,1,1,1) \mathfrak x_1 +(0,0,1,1)\mathfrak x_2 &= & (1,1,1,0) \end{array} \right. $$ в поле $ \mathbf{GF}(16) $ с умножением, определенным по модулю $ 2,f(x)=x^4+x+1 $. **Решение.** Имеем[[Все дальнейшие сравнения --- по модулю $ 2,f(x)=x^4+x+1 $.]] $$ \Delta\equiv x^2(x+1)-(x^2+1)(x^3+x^2+x+1)\equiv x^3+x,\ $$ $$ \Delta_1 \equiv x^3(x+1)-(x^3+x^2+x)(x^2+1) \equiv x^3,\quad \Delta_2 \equiv x^2(x^3+x^2+x)-(x^3+x^2+x+1)x^3 \equiv x^3+x^2 \ , $$ и $$ \mathfrak x_1\equiv x^3(x^3+x)^{-1}\equiv x^3(x^3+x^2) \equiv x^3+x=(1,0,1,0), \quad \mathfrak x_2\equiv (x^3+x^2)(x^3+x)^{-1} \equiv x^3+x^2+x+1=(1,1,1,1) \ . $$ ♦ !!?!! В поле предыдущего примера решить системы уравнений $$ \mathbf{a)} \left\{ \begin{array}{lcl} (0,1,0,0) \mathfrak x_1 +(1,0,1,0)\mathfrak x_2 &= & (1,0,0,0), \\ (1,1,1,1) \mathfrak x_1 +(0,0,1,1)\mathfrak x_2 &= & (1,1,0,1); \end{array} \right. $$ $$ \mathbf{b)} \left\{ \begin{array}{lcl} (0,1,0,0) \mathfrak x_1 +(1,0,1,0)\mathfrak x_2 &= & (0,1,0,1), \\ (1,1,1,1) \mathfrak x_1 +(0,0,1,1)\mathfrak x_2 &= & (1,1,0,1). \end{array} \right. $$ Теперь можно ввести и аналог определителя --- как полиномиальной функции элементов поля; существенным упрощением ((:algebra2:dets#определение стандартного определения)) является то обстоятельство, что в разложении определителя с элементами из $ \mathbf{GF}(16) $ всем слагаемым можно приписывать одинаковый знак. Так, например, определитель третьего порядка введем формулой $$ \left| \begin{array}{lll} \mathfrak a_{11} & \mathfrak a_{12} & \mathfrak a_{13}\\ \mathfrak a_{21} & \mathfrak a_{22} & \mathfrak a_{23} \\ \mathfrak a_{31} & \mathfrak a_{32} & \mathfrak a_{33} \end{array} \right| =\mathfrak a_{11} \mathfrak a_{22} \mathfrak a_{33}+\mathfrak a_{12}\mathfrak a_{23} \mathfrak a_{31} + \mathfrak a_{21}\mathfrak a_{32} \mathfrak a_{13} + \mathfrak a_{31} \mathfrak a_{22} \mathfrak a_{13} + \mathfrak a_{21}\mathfrak a_{12}\mathfrak a_{33} + \mathfrak a_{11} \mathfrak a_{32} \mathfrak a_{23} \ . $$ А уж если ввели определитель, то самое время ввести понятие матрицы из элементов поля --- хотя бы для того, чтобы иметь возможность выписать решение системы л.у. ((:algebra2:inverse#использование_для_решения_систем_линейных_уравнений с помощью обратной матрицы)). Но пока повременим с развитием этой идеи, а попробуем взглянуть на решение предыдущего примера альтернативным взглядом. Рассмотрим подробнее операцию умножения элемента поля $ \mathfrak a_1= (0,1,0,0) $ на произвольный элемент $ \mathfrak x =(x_0,x_1,x_2,x_3) $ этого же поля[[Все дальнейшие сравнения --- по модулю $ 2,f(x)=x^4+x+1 $.]]: $$ x^2(x_0x^3+x_1x^2+x_2x+x_3) \equiv x_0(x^2+x)+x_1(x+1)+x_2x^3+x_3x^2 \equiv x_2 x^3+(x_0+x_3)x^2+(x_0+x_1)x+x_1 \ . $$ Таким образом, умножение на $ (0,1,0,0) $ определяет отображение строк в поле $ \mathbf{GF}(16) $: $$ \mathfrak x=(x_0,x_1,x_2,x_3) \ \mapsto \ \mathfrak y =(x_2,x_0+x_3,x_0+x_1,x_1) \ . $$ Это отображение, очевидно, является ((:mapping:operator линейным)). Следовательно, его можно задать с помощью ((:mapping:operator#матрица_оператора матрицы)): $$ \mathfrak x \ \mapsto \ \mathfrak y=(x_0,x_1,x_2,x_3) \left(\begin{array}{cccc} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{array} \right) \ . $$ Способ записи этого отображения несколько непривычен в сравнении с традиционным --- когда матрица умножается __слева на столбец__ координат. Однако в теории кодирования больше любят действовать со строками, так что приходится перестраиваться... Не очень принципиально, один способ с другим связан операцией ((:algebra2#транспонирование транспонирования)). Теперь рассмотрим умножение произвольного элемента $ \mathfrak x $ поля на другой элемент, например на $ \mathfrak a_2=(0,1,0,1) $. Соответствующая цепочка рассуждений приводит уже к другой матрице: $$ \mathfrak x \ \mapsto \ \mathfrak y=(x_0,x_1,x_2,x_3) \left(\begin{array}{cccc} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array} \right) \ . $$ Теперь первое уравнение системы из предыдущего примера $$ (0,1,0,0) \mathfrak x_1 +(0,1,0,1)\mathfrak x_2 = (1,0,0,0) $$ также можно переписать в матричном виде если положить $ \mathfrak x_1=(x_{10},x_{11},x_{12},x_{13}) $, $ \mathfrak x_2=(x_{20},x_{21},x_{22},x_{23}) $ и использовать операцию поразрядного сложения по модулю $ 2_{} $ (**XOR**): $$ (x_{10},x_{11},x_{12},x_{13}) \underbrace{\left(\begin{array}{cccc} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{array} \right)}_{=\mathbf{A}_{11}} \oplus (x_{20},x_{21},x_{22},x_{23}) \underbrace{\left(\begin{array}{cccc} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array} \right)}_{=\mathbf{A}_{12}} =(1,0,0,0) \ . $$ Вывод: линейное уравнение относительно $ 2_{} $-х элементов поля $ \mathbf{GF}(16) $ эквивалентно системе из $ 4_{} $-х линейных уравнений относительно $ 8_{} $-ми неизвестных двоичных разрядов. Но если в первом случае уравнение понималось по двойному модулю $ 2,f(x) $, то во втором случае каждое из уравнений --- это сравнение по одному только числовому модулю $ 2_{} $; о подобных уравнениях будем говорить как об **уравнениях над GF(2)**. Второе уравнение системы перепишется в аналогичной форме: $$ (x_{10},x_{11},x_{12},x_{13}) \underbrace{\left(\begin{array}{cccc} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{array} \right)}_{=\mathbf{A}_{21}} \oplus (x_{20},x_{21},x_{22},x_{23}) \underbrace{\left(\begin{array}{cccc} 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{array} \right)}_{=\mathbf{A}_{22}} =(1,1,1,0) \ ; $$ а вся система из $ 2_{} $-х уравнений над $ \mathbf{GF}(16) $ эквивалентна системе из $ 8_{} $-ми уравнений над $ \mathbf{GF}(2) $. Эта система записывается в блочной форме[[В оставшейся части пункта будем считать $ +_{} $ совпадающим с $ \oplus $.]]: $$ \left\{ \begin{array}{lcl} \mathfrak x_1 \mathbf{A}_{11} +\mathfrak x_2 \mathbf{A}_{12}&= & \mathfrak b_1, \\ \mathfrak x_1\mathbf{A}_{21} + \mathfrak x_2 \mathbf{A}_{22} &= & \mathfrak b_2, \end{array} \right. \qquad \iff \qquad (\mathfrak x_1,\mathfrak x_2)_{1\times 8} \left( \begin{array}{ll} \mathbf A_{11} & \mathbf A_{21} \\ \mathbf A_{12} & \mathbf A_{22} \end{array} \right)_{8 \times 8}= (\mathfrak b_1,\mathfrak b_2)_{1\times 8} \ . $$ Мы хотим решить эту систему именно в таком разбиении $ 8_{} $-миразрядной строки неизвестных на две составляющих компоненты $ \mathfrak x_1 $ и $ \mathfrak x_2 $. Попробуем сделать это с помощью матричного формализма, повторив ход решения системы из двух уравнений в поле $ \mathbf{GF}(16) $. Домножим первое уравнение системы справа на матрицу $ \mathbf A_{22} $, второе уравнение системы --- справа же на матрицу $ \mathbf A_{12} $, и вычтем одно получившееся равенство из другого: $$ \mathfrak x_1 (\mathbf A_{11}\mathbf A_{22}- \mathbf A_{21}\mathbf A_{12})+ \mathfrak x_2 (\mathbf A_{12}\mathbf A_{22}- \mathbf A_{22}\mathbf A_{12}) =\mathfrak b_1 \mathbf A_{22}- \mathfrak b_2 \mathbf A_{12} \ . $$ Матрица, стоящая коэффициентом при $ \mathfrak x_2 $, --- нулевая, поскольку $ \mathbf A_{12}\mathbf A_{22}=\mathbf A_{22}\mathbf A_{12} $... Стоп. Стоп! Умножение матриц ((:algebra2/assoc некоммутативно))! Для произвольных квадратных матриц $ \mathbf A_{} $ и $ \mathbf B $, как правило, не будет выполнено $ \mathbf A \mathbf B = \mathbf B \mathbf A $! На всякий случай, всё же проверим[[Напомню: операция $ +_{} $ идет по модулю $ 2_{} $.]]: $$ \mathbf A_{12}\mathbf A_{22}=\left(\begin{array}{cccc} 2 & 2 & 2 & 1 \\ 1 & 2 & 2 & 1 \\ 1 & 1 & 2 & 1 \\ 1 & 1 & 1 & 1 \end{array} \right)\equiv_{_2} \underbrace{\left(\begin{array}{cccc} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{array} \right)}_{=\mathbf{A}_{21}} = \mathbf A_{22}\mathbf A_{12} \ . $$ А наши матрицы-то коммутируют! Более того, совершенно неожиданно результат умножения оказался соответствующим результату умножения элементов поля: $$ (0,1,0,1) \leftrightarrow \mathbf A_{12},\ (0,0,1,1) \leftrightarrow \mathbf A_{22} \quad \Rightarrow (0,1,0,1)\cdot (0,0,1,1)=(1,1,1,1) \leftrightarrow \mathbf A_{21} \ . $$ Проверяем свойство коммутативности умножения для __всех__ построенных нами матриц: оно выполняется :!: Идем дальше. Если $ \mathbf A_{12}\mathbf A_{22}=\mathbf A_{22}\mathbf A_{12} $, то можем корректно завершить наши рассуждения по решению системы уравнений, разбитой на блоки, с помощью матричного формализма: $$ \mathfrak x_1 (\mathbf A_{11}\mathbf A_{22}- \mathbf A_{21}\mathbf A_{12})=\mathfrak b_1 \mathbf A_{22}- \mathfrak b_2 \mathbf A_{12} \quad \Rightarrow \quad \mathfrak x_1=(\mathfrak b_1 \mathbf A_{22}- \mathfrak b_2 \mathbf A_{12})(\mathbf A_{11}\mathbf A_{22}- \mathbf A_{21}\mathbf A_{12})^{-1} \ . $$ Останавливаемся еще раз: где гарантия, что существует обратная матрица? Проверяем: $$ \left(\begin{array}{cccc} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{array} \right) \left(\begin{array}{cccc} 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{array} \right)- \left(\begin{array}{cccc} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{array} \right) \left(\begin{array}{cccc} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array} \right)\equiv_{_2} \overbrace{\left(\begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \end{array} \right)}^{= \mathbf A_{00}} \ . $$ Поскольку $ \det \mathbf A_{00}=-1\equiv_{2} +1 $, обратная матрица существует: $$ \mathbf A_{00}^{-1}= \left(\begin{array}{cccc} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{array} \right) \ . $$ Ну и последний шаг: $$ \mathfrak x_1=(\mathfrak b_1 \mathbf A_{22}- \mathfrak b_2 \mathbf A_{12})\mathbf A_{00}^{-1} =((1,0,1,1)-(0,0,1,1))\mathbf A_{00}^{-1}=(1,0,1,0) \ . $$ И этот результат совпадает с ответом примера. ====Матрицы== Перевод формализма полей Галуа на язык матриц наводит на мысль о существовании более тесной связи между этими двумя объектами. Возникает подозрение, что поле Галуа $ \mathbf{GF}(16) $ ((:gruppe#кольцо изоморофно)) некоторому подмножеству квадратных матриц $ 4_{} $-го порядка. Осталось только указать соответствие: $$ \mathfrak a=(A_0,A_1,A_2,A_3) \ \leftrightarrow \ a(x)=A_0x^3+A_1x^2+A_2x+A_3 \ \leftrightarrow \ \mathbf{A} \ , $$ а потом установить, что оно сохраняет результаты сложения и умножения. Последняя строка матрицы $ \mathbf{A} $ угадывается из примеров --- она совпадает со строкой $ \mathfrak a $: $$ \mathbf{A}= \left(\begin{array}{llll} \ast & \ast & \ast & \ast \\ \ast & \ast & \ast & \ast \\ \ast & \ast & \ast & \ast \\ A_0& A_1 & A_2 & A_3 \end{array} \right) \ . $$ Что представляют собой остальные строки? --- Это коэффициенты полиномов $$ a(x) x,\ a(x)x^2,\ a(x)x^3 \quad (\operatorname{modd} \ 2,x^4+x+1) , $$ т.е. коэффициенты по модулю $ 2_{} $ остатков указанных полиномов от деления на полином $ f(x)=x^4+x+1 $. Эти коэффициенты расположены в матрице по схеме: $$ \begin{array}{ll} \mathbf{A}= \left(\begin{array}{llll} \ast & \ast & \ast & \ast \\ \ast & \ast & \ast & \ast \\ \ast & \ast & \ast & \ast \\ A_0& A_1 & A_2 & A_3 \end{array} \right) & \begin{array}{lc} \leftarrow a(x)x^3 & (\operatorname{modd} \ 2,x^4+x+1) \\ \leftarrow a(x)x^2 & (\operatorname{modd} \ 2,x^4+x+1) \\ \leftarrow a(x)x & (\operatorname{modd} \ 2,x^4+x+1) \\ \leftarrow a(x) & (\operatorname{modd} \ 2,x^4+x+1) \end{array} \\ { } \qquad \quad \ \uparrow \quad \ \ \uparrow \quad \ \uparrow \quad \ \uparrow & \\ { } \qquad \quad \ x^3 \quad \ x^2 \quad \ x \ \quad 1 & \end{array} \ . $$ Откуда возникает эта матрица? Разберем еще раз процедуру вычисления произведения полиномов по двойному модулю, несколько схем для которой были рассмотрены в ☝ ((#возведение_в_степень ВЫШЕ)). Пусть $$ a(x)=A_0x^3+A_1x^2+A_2x+A_3, \ B(x)=B_0x^3+B_1x^2+B_2x+B_3 \ . $$ Организуем вычисления $ a(x)b(x) \ (\operatorname{modd} \ 2,f(x)) $ по иной схеме: $$ \begin{array}{ll} a(x)b(x) \ (\operatorname{modd} \ 2,f(x)) & = \left[ a(x)x^3 \ (\operatorname{modd} \ 2,f(x))\right]B_0+ \\ &+\left[ a(x)x^2 \ (\operatorname{modd} \ 2,f(x))\right]B_1+ \\ &+\left[ a(x)x \ (\operatorname{modd} \ 2,f(x))\right]B_2+\\ &+\left[ a(x) \right]B_3. \end{array} $$ Коэффициенты полиномов в каждой скобке $ [ \mbox{ } \ ] $ образуют строки матрицы $ \mathbf{A} $, а, следовательно, ((:linear_space#линейная_зависимость_базис_координаты линейной комбинации)) этих полиномов, образуемой домножением на скаляры $ B_0,B_1,B_2,B_3 $, соответствует умножение строки этих скаляров на матрицу $ \mathbf{A} $: $$ (B_0,B_1,B_2,B_3) \mathbf{A} \ . $$ Понятно, что матрица $ \mathbf A $ строится снизу вверх, начиная с последней строки: так, $ 3_{} $-я строка матрицы $$ \mathbf{A}= \left(\begin{array}{llll} M_0 & M_1 & M_2 & M_3 \\ L_0 & L_1 & L_2 & L_3 \\ K_0 & K_1 & K_2 & K_3 \\ A_0 & A_1 & A_2 & A_3 \end{array} \right) $$ получается из $ 4_{} $-й по ((#умножение правилу умножения на x))[[Имеется в виду "умножение на <<икс>>", а не то, что может придти в голову ;-)]] и вычисления остатка по модулю $ 2_{} $ при делении на $ f(x)=x^3+a_1x^2+a_2x+a_3 $ $$ \mathfrak (K_0,K_1,K_2,K_3) = \left\{ \begin{array}{lr} (A_1,A_2,A_3,0) & npu \ A_0=0, \\ (A_1+a_1,A_2+a_2,A_3+a_3, a_4) \pmod{2} & npu \ A_0=1. \end{array} \right. $$ После этого, $ 2_{} $-я строка получается из $ 3_{} $-й по аналогичному правилу и т.д. !!П!! **Пример.** $$ \mathfrak a = \mathfrak e=(0,0,0,1) \ \leftrightarrow \ \mathbf{A}=E=\left(\begin{array}{llll} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0& 0 & 1 & 0 \\ 0& 0 & 0 & 1 \end{array} \right) , $$ т.е. единичному элементу поля соответствует единичная матрица $ 4_{} $-го порядка. Далее, $$ (0,0,1,0) \ \leftrightarrow \ \mathbf{F}= \left(\begin{array}{llll} 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0& 1 & 0 & 0 \\ 0& 0 & 1 & 0 \end{array} \right) ,\ (0,0,1,1) \ \leftrightarrow \ \left(\begin{array}{llll} 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 0& 1 & 1 & 0 \\ 0& 0 & 1 & 1 \end{array} \right),\ $$ $$ (0,1,0,0) \ \leftrightarrow \ \left(\begin{array}{llll} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1& 0 & 0 & 0 \\ 0& 1 & 0 & 0 \end{array} \right),\dots $$ Теперь убедимся, что третья матрица является ((:algebra2#полином_от_матрицы_и_матричный_полином степенью)) первой, она равна $ \mathbf{F}^2 \pmod{2} $. Но вторая матрица также является степенью первой: она равна $ \mathbf{F}^4 \pmod{2} $. Откуда это взялось? 8-o --- Пока непонятно, но, по крайней мере, мы не входим в противоречие с "таблицей логарифмов" из пункта ☝ ((#возведение_в_степень ВОЗВЕДЕНИЕ В СТЕПЕНЬ)): $$ {.} \mbox{ если }\ (0,0,1,0) \leftrightarrow \ x, \mbox{ то } \ (0,0,1,1) \leftrightarrow \ x^4 \quad \mbox{ и } \quad (0,1,0,0) \leftrightarrow \ x^2 \ . $$ ♦ Что же за чудесные матрицы нами получены? Начнем идентификацию с более простой матрицы, именно с матрицы $ \mathbf{F} $, фактически задающей умножение элемента поля на полином, тождественно равный $ x_{} $. Какую структуру будет она иметь в случае произвольного поля $ \mathbf{GF}(2^n) $, с операцией умножения, задаваемой по модулю $ 2, f(x)=x^n+a_1x^{n-1}+a_2x^{n-2}+\dots+ a_n $? --- Это легко установить: $$ \mathbf{F}= \left( \begin{array}{lllllll} a_1 & a_{2} & a_{3} & \dots & & a_{n-1} & a_n \\ 1 & 0 & 0 &\dots & 0 & 0 & 0 \\ 0 & 1 & 0 & \dots & 0 & 0 & 0 \\ \vdots& && \ddots && & \vdots \\ 0 & 0 & 0 & \dots & 1 & 0 & 0 \\ 0 & 0 & 0 & \dots & 0 & 1 & 0 \end{array} \right)_{n \times n} \ . $$ Эта матрица[[с точностью до перестановки строк и столбцов]] известна как ((:algebra2#фробениуса матрица Фробениуса)). ---- Сложнее с общим видом матрицы $ \mathbf{A} $, соответствующей полиному $ a(x)=A_0x^3+A_1x^2+A_2x+A_3 $. В случае бесконечных полей ( $ \mathbb Q, \mathbb R_{} $ или $ \mathbb C_{} $) это --- матрица из ((:dets:resultant#результант_в_форме_безу метода Безу представления результанта)) полиномов $ f_{}(x) $ и $ a(x) $. Что известно про подобные матрицы? Если $ \mathbf{B} $ --- матрица, соответствующая полиному $ b(x)=B_0x^3+B_1x^2+B_2x+B_3 $, то $$ \mathbf{A} \mathbf{B}=\mathbf{B} \mathbf{A} \ , $$ т.е. матрицы коммутируют. Более того, общий результат такого произведения представляет аналогичную матрицу, составленную для полинома $ a(x)b(x) \pmod{f(x)} $, т.е. для остатка от деления $ a(x)b(x) $ на $ f_{}(x) $. Доказательство когда-нибудь выложу ☞ ((:dets:resultant:bezout ЗДЕСЬ)). Определитель матрицы $ \mathbf{A} $ равен результанту полиномов $ f_{}(x) $ и $ a(x) $, и он отличен от нуля при условии, что эти полиномы взаимно просты. ---- Переносим эти результаты в конечное поле. Коммутативность умножения матриц сохранится и при переходе к сравнению по модулю $ 2_{} $; этот же переход даст в результате умножения матриц матрицу, соответствующую полиному $ a(x)b(x) \ (\operatorname{modd} \ 2,x^4+x+1) $. Таким образом, установленное соответствие $$ \mathfrak a=(A_0,A_1,A_2,A_3) \ \leftrightarrow \ a(x)=A_0x^3+A_1x^2+A_2x+A_3 \ \leftrightarrow \ \mathbf{A} $$ сохранит результат умножения: произведению элементов поля будет соответствовать произведение соответствующих матриц. Поэтому элементу $ \mathfrak a^{-1} $ будет соответствовать $ \mathbf{A}^{-1} $. Этот факт подтвержает представление для $ \mathfrak a^{-1} $ в полиномиальной форме, данное в конце ☝ ((#деление ПУНКТА)). Действительно, $$ . \mbox{ если } \quad \mathbf{A}^{-1}= \left(\begin{array}{llll} \ast & \ast & \ast & \ast \\ \ast & \ast & \ast & \ast \\ \ast & \ast & \ast & \ast \\ B_0& B_1 & B_2 & B_3 \end{array} \right) \quad \mbox{ то } \quad \mathfrak a^{-1} =B_0x^3+B_1x^2+B_2x+ B_3 $$ С другой стороны, по способу построения обратной матрицы с помощью ((:algebra2:inverse#способы_построения алгебраических дополнений)), элементы последней строки матрицы $ \mathbf{A}^{-1} $ являются алгебраическими дополнениями к элементам последнего столбца матрицы $ \mathbf{A} $, поэтому $$ \mathfrak a^{-1}= \left|\begin{array}{llll} M_0 & M_1 & M_2 & x^3 \\ L_0 & L_1 & L_2 & x^2 \\ K_0 & K_1 & K_2 & x \\ A_0 & A_1 & A_2 & 1 \end{array} \right| \ . $$ Сохранится ли сложение: будет ли сумма $ \mathbf{A}+ \mathbf{B} $ соответствовать элементу поля $ \mathfrak a+\mathfrak b $ или, что то же, $ a(x)+b(x) $? --- Да, будет, поскольку остаток от суммы полиномов совпадает с суммой их остатков: $$ (a(x)+b(x))x^k \quad (\operatorname{modd} \ 2,x^4+x+1) \equiv a(x) x^k (\operatorname{modd} \ 2,x^4+x+1) + b(x) x^k \quad (\operatorname{modd} \ 2,x^4+x+1) $$ для $ \forall k \in \{0,1,2,3\} $. Итак, изоморфизм между полем Галуа и множеством матриц установлен. Из этого утверждения следует, что любая матрица $ \mathbf{A} $, соответствующая полиному $ a(x)=A_0x^3+A_1x^2+A_2x+A_3 $ может быть, с одной стороны, представлена в виде линейной комбинации степеней матрицы Фробениуса, т.е. ((:algebra2#полином_от_матрицы_и_матричный_полином полинома от матрицы)) $ \mathbf{F} $ $$ \mathbf{A} = A_0 \mathbf{F}^3\oplus A_1 \mathbf{F}^2\oplus A_2\mathbf{F}\oplus A_3 E = a (\mathbf{F}) \ , $$ а, с другой стороны, должна быть некоторой степенью все той же матрицы Фробениуса: $$ \mathbf{A} = \mathbf{F}^m \quad \mbox{ при некотором } \quad m\in \{0,1,2,\dots \} . $$ Последовательность $ \mathbf{F}^0=E, \mathbf{F}^1, \mathbf{F}^2,\dots, $ будет цикличной: $ \mathbf{F}^{15}=E $. Подводя итог: в дополнение к упомянутым ☝ ((#возведение_в_степень ВЫШЕ)) интерпретациям поля Галуа, добавим еще одно. Ненулевой элемент поля Галуа --- это 4. некоторая степень матрицы Фробениуса $ \mathbf{F} $ или же полином $ a(\mathbf{F}) $ ( $ \deg a(x) \le 3 $) от этой матрицы. Операция сложения определена как поэлементная по модулю $ 2_{} $, а операция умножения совпадает с операцией умножения матриц[[Поскольку составной частью операции умножения матриц является операция сложения, то последнюю, опять же, выполняем по модулю $ 2_{} $.]]. В такой интерпретации пропадает необходимость в формализме вычисления произведения элементов поля посредством перемножения полиномов и вычисления остатков по модулю полинома $ f_{}(x) $, порождающего поле Галуа. А, кстати, куда этот полином пропал в новом, т.е. матричном, формализме? --- Его коэффициенты составили первую строчку матрицы Фробениуса $ \mathbf{F} $, и это его единственное проявление. ===Восстановление утерянной информации== Собранного в предыдущих пунктах алгебраического формализма достаточно, чтобы попытаться объяснить "на пальцах" его применения для решения задач помехоустойчивого кодирования. Предположим, что у нас имеется строка из $ 20_{} $ информационных двоичных разрядов $ (x_1,\dots,x_{20}) $, которая участвует в процессе //коммуникации// --- либо пересылается по каналу связи, либо записывается на носитель информации. Предположим, что этот процесс подвержен влиянию помех, и часть информационных разрядов могут оказаться потерянными (или испорченными). Задача заключается в такой организации процесса коммуникации, которая позволяла бы восстанавливать потерянное (или исправлять ошибки). Для решения этой задачи нужны ресурсы. И этими ресурсами являются, во-первых, дополнительные --- //служебные// --- разряды, которые подсоединяются к информационным разрядам (и, следовательно, тоже участвуют в процессе коммуникации), и, во-вторых, имеющиеся в нашем распоряжении вычислительные мощности, позволяющие наполнять содержимое служебных разрядов --- в зависимости от содержимого разрядов информационных, а также выполнять собственно задачу восстановления утраченного. ==== Места потерь известны== Поясню на примерах. Составим контрольную сумму $$ s=\sum_{i=1}^{20} x_i \pmod{2} \ . $$ Объектом коммуникации делаем строку $ (x_1,\dots,x_{20},s) $. Если в результате коммуникации //возможно// уничтожается содержимое __ровно одного__ информационного разряда и __номер__ $ j_{} $ этого разряда __становится нам известным__, то однозначное восстановление содержимого //возможно// испорченного разряда производтся по формуле $$ x_j = s+ \sum_{i=1 \atop i\ne j}^{20} x_i \pmod{2} \ . $$ Подчеркнем универсальность этой формулы: она применима для любого значения индекса $ j_{} $. Существенно сложнее организовать восстановление содержания поврежденных разрядов в случае, когда их несколько. Если бы мы заранее знали их номера, то решение проблемы было бы тривиальным. Например, две контрольные суммы $$ \left\{ \begin{array}{lcl} s_1&=& x_1+x_3+\dots+x_{19}, \\ s_2 &=&x_2+x_4+\dots+x_{20} \end{array} \right. \pmod{2} $$ позволят однозначно восстановить содержимое разрядов $ x_{j} $ и $ x_{k} $, если $ j_{} $ и $ k_{} $ --- числа разной четности[[Например, содержимое двух соседних разрядов.]]. Но мы не можем предполагать от нашей техники гарантированного выполнения последнего условия. Так что, если при коммуникации строки $ (x_1,\dots,x_{20},s_1,s_2) $ возникает подозрение об уничтожении информационных разрядов с номерами $ j_{} $ и $ k_{} $ одинаковой четности, то гарантировать их восстановление с помощью указанных контрольных сумм мы не сможем. Что делать? Очевиден подход к решению задачи: нужно выписать набор (систему) линейных соотношений (уравнений) относительно величин $ x_1,\dots,x_{20} $ так, чтобы имелась возможность разрешить полученную систему относительно любых двух величин $ x_{j} $ и $ x_{k} $. Проблема за малым --- как построить такие соотношения? Будем решать задачу путем ее усложнения. Допустим, что в процессе коммуникации возможно уничтожение содержимого $ \le 8_{} $ информационных разрядов строки $ X=(x_1,\dots,x_{20}) $. Для обеспечения возможности восстановления этого содержимого, создаются $ 8_{} $ служебных разрядов $ S= (s_1,\dots,s_8) $ (назовем их **синдромами**) , содержимое которых вычисляется по правилу $$ s_i=a_{i1} x_1+\dots+a_{i,20}x_{20} \pmod{2} \quad npu \quad i\in \{1,\dots,8\} $$ и при некоторых --- пока неопределенных --- значениях коэффициентов $ \{a_{i\ell}\} \subset \{0,1\} $. Сделаем дополнительное предположение: пусть $ 8_{} $ потенциально ошибочных информационных разрядов расположены не совсем хаотично в информационной строке, а локализуются в двух составляющих ее $ 4_{} $-хразрядных блоках $ X_j $ и $ X_k $: $ X=(X_1,X_2,X_3,X_4,X_5) $. Перепишем $ 8_{} $ линейных соотношений для синдромов в матричном виде: $$ X_{1\times 20} \mathbf{A}_{20\times 8}=S_{1\times 8} $$ и перейдем в этом матричном уравнении к составляющим блокам. Если $$ \mathbf{A}= \left( \begin{array}{ll} \mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{A}_{21} & \mathbf{A}_{22} \\ \mathbf{A}_{31} & \mathbf{A}_{32} \\ \mathbf{A}_{41} & \mathbf{A}_{42} \\ \mathbf{A}_{51} & \mathbf{A}_{52} \end{array} \right) \quad u \quad S=(S_1,S_2), $$ то $$ \left\{ \begin{array}{lcl} X_1\mathbf{A}_{11}\oplus X_2\mathbf{A}_{21}\oplus X_3\mathbf{A}_{31} \oplus X_4\mathbf{A}_{41} \oplus X_5\mathbf{A}_{51}&=&S_1, \\ X_1\mathbf{A}_{12}\oplus X_2\mathbf{A}_{22}\oplus X_3\mathbf{A}_{32} \oplus X_4\mathbf{A}_{42} \oplus X_5\mathbf{A}_{52}&=&S_2. \end{array} \right. $$ Задача заключается в подборе таких составляющих матрицу $ \mathbf{A} $ блоков, чтобы последняя система была однозначно разрешима относительно любой пары информационных блоков $ X_{j} $ и $ X_k $. Выберем все эти матрицы $ \{\mathbf{A}_{i,\ell}\} $ из множества $ \{ \mathbf F^{m} \}_{m=0}^{15} $ степеней матрицы Фробениуса, рассмотренной в предыдущем пункте. Поскольку эти матрицы коммутируют, то с ними возможно действовать как с обычными числами. Так, к примеру, если взять систему в виде[[В оставшейся части пункта будем считать $ +_{} $ совпадающим с $ \oplus $.]] $$ \left\{ \begin{array}{lcl} X_1E + X_2E+ X_3 E + X_4E + X_5E&=&S_1, \\ X_1E+ X_2\mathbf F+ X_3\mathbf F^2 + X_4\mathbf F^3 + X_5\mathbf F^4&=&S_2, \end{array} \right. $$ то решение ее относительно любой пары блоков $ X_{j} $ и $ X_{k} $ возможно по схеме, которую мы проиллюстрируем на случае $ j=2, k=4 $: 1. умножим первое уравнение справа на матрицу $ \mathbf F^3 $ и прибавим ко второму: $$ X_{2}( \mathbf F + \mathbf F^3 ) =S_2+S_1\mathbf F^3 +X_1(E+\mathbf F^3)+X_3(\mathbf F^2 + \mathbf F^3 ) + X_5(\mathbf F^4 + \mathbf F^3) \ ; $$ 2. найдем матрицу обратную матрице $ \mathbf F + \mathbf F^3 $ --- любым из ((:algebra2:inverse известных способов)): $$( \mathbf F + \mathbf F^3 )^{-1}= \left( \begin{array}{llll} 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \end{array} \right)^{-1} = \left( \begin{array}{llll} 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{array} \right)=\mathbf F^2 + \mathbf F^3 \ ; $$ 3. домножим последнее уравнение на эту матрицу справа, получим: $$ X_{2}=S_2(\mathbf F^2 + \mathbf F^3)+S_1(\mathbf F^5 + \mathbf F^6) +X_1(\mathbf F^2+\mathbf F^3+\mathbf F^5+\mathbf F^6)+X_3(\mathbf F^4 + \mathbf F^6 )+X_5(\mathbf F^5 + \mathbf F^7); $$ 4. после нахождения $ X_{2} $ выражение для $ X_{4} $ вычисляем из первого линейного соотношения. !!П!! **Пример.** Пусть $$ X_1=(1,0,1,0),\ X_2=(0,1,1,1),\ X_3=(0,1,0,1),\ X_4=(1,0,1,0),\ $$ $$ X_5=(0,0,1,1) \ . $$ Вычисляем $ S_1 $ и $ S_2 $: $$ S_1=(0,0,0,1), S_2=(1,0,0,1) \ . $$ Если предположить, что мы потеряли значения $ X_2 $ и $ X_4 $, то, действуя по предложенному алгоритму, получим: $$ S_2 \left( \begin{array}{llll} 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{array} \right)+S_1 \left( \begin{array}{llll} 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \end{array} \right)+X_1 \left( \begin{array}{llll} 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \end{array} \right)+ $$ $$ +X_3 \left( \begin{array}{llll} 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 1\\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{array} \right)+X_5 \left( \begin{array}{llll} 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 \end{array} \right) =(0,1,1,1)= X_2 \ . $$ В настоящем пункте были сделаны все теоретические "заготовки" необходимые для понимания теории построения ((:codes:raid отказоустойчивых дисковых массивов)); последний разобранный пример соответствует последнему примеру из ☞ ((:codes:raid#идея ПУНКТА)). !!?!! Пусть информационная строка $ X_{} $ состоит из $ 21_{} $ информационного разряда. Разобьем ее на $ 3_{} $-хразрядные блоки $ X=(X_1,\dots,X_7) $. Используя поле $ \mathbf{GF}(2^3) $ придумать схему построения синдромов с возможностью восстановления любых __трех__ блоков. Сработает ли та же схема для строки из $ 24_{} $ разрядов? ====Места потерь неизвестны== Обратимся теперь к решению более сложной задачи: когда в процессе коммуникации портится содержимое одного или нескольких информационных блоков, но номера этих блоков нам __неизвестны__. Начнем с самого простого случая: предположим, что испорчено содержание одного-единственного блока, но его местоположение нам неизвестно. Итак, предположим, что до процесса коммуникации мы вычислили значения синдромов по предложенной выше схеме: $$ \left\{ \begin{array}{lllllcl} X_1& + X_2 &+ X_3& + X_4& + X_5&=&S_1, \\ X_1&+ X_2\mathfrak a&+ X_3 \mathfrak a^2&+ X_4\mathfrak a^3&+ X_5\mathfrak a^4&=&S_2. \end{array} \right. $$ Здесь $ \mathfrak a $ --- произвольный элемент поля $ \mathbf{GF}(16) $ с единственным условием, что все элементы $ \{\mathfrak a^{\ell} \}_{\ell=0}^5 $ различны. Причем нас не интересует пока в какой форме представлен этот элемент --- полиномиальной, матричной или любой иной. Пусть в процессе коммуникации строки $ X_{} $ произошла ошибка в единственном блоке $ X_{j} $, но номер $ j_{} $ этого блока нам неизвестен. В результате пересчитанные синдромы получают новые значения $$ \left\{ \begin{array}{lllllcl} \tilde X_1& + \tilde X_2 &+ \tilde X_3& + \tilde X_4& + \tilde X_5 &=& \tilde S_1, \\ \tilde X_1 &+ \tilde X_2\mathfrak a&+ \tilde X_3 \mathfrak a^2&+ \tilde X_4\mathfrak a^3&+ \tilde X_5\mathfrak a^4&=& \tilde S_2. \end{array} \right. $$ Просуммируем по частям соответствующие равенства. Поскольку все элементы $ \tilde X_i = X_i $ при всех $ i \ne j $, то получаем: $$ X_j + \tilde X_j = S_1+ \tilde S_1,\ (X_j + \tilde X_j) \mathfrak a^{j-1} = S_2+ \tilde S_2 \ . $$ При условии $ S_1 \ne \tilde S_1 $, факт наличия ошибки подтверждается. Тогда $$ (S_1+ \tilde S_1)\mathfrak a^{j-1} = S_2+ \tilde S_2 \ $$ и элемент поля $ \mathfrak a^{j-1} $ может быть выражен из последнего уравнения: $$ \mathfrak a^{j-1} = (S_2+ \tilde S_2)(S_1+ \tilde S_1)^{-1} \ ; $$ надо только понимать, что все наши действия (сложение, умножение, обращение) производились над элементами поля $ \mathbf{GF}(16) $. Таким образом, для определения места ошибки $ j_{} $ мы должны вычислить правую часть последнего равенства и найти в "таблице логарифмов", аналогичной той, что приведена в ☞ ((#возведение_в_степень ПУНКТЕ)), показатель $ j_{}-1 $ которому этот элемент соответствует (т.е. вычислить "дискретный логарифм по основанию" $ \mathfrak a $). После установления значения $ j_{} $ исправляем содержимое блока с этим номером по формуле $$ X_j = \tilde X_j + (S_1+ \tilde S_1) \ . $$ !!П!! **Пример.** Пусть на выходе канала связи получена информационная строка, разбиение которой на блоки имеет вид: $$ \tilde X_1=(1,0,1,0),\ \tilde X_2=(1,1,0,0),\ \tilde X_3=(1,1,1,1),\ \tilde X_4=(0,1,1,0),\ \tilde X_5=(0,0,0,1).\ $$ В предположении единственности испорченного блока, найти его место и исправить его содержимое, если значения синдромов: $$S_1= (0,1,0,0), \tilde S_1= (1,1,1,0),\ S_2= (0,0,0,1), \tilde S_2= (1,1,1,0) $$ подсчитаны в поле $ \mathbf{GF}(16) $ по указанной выше схеме при выборе $ \mathfrak a=(0,0,1,0)=x $ и операции умножения, определенной по двойному модулю $ 2,x^4+x+1 $. **Решение.** $$ x^{j-1}=(1,1,1,1)\cdot(1,0,1,0)^{-1}=(1,1,1,1) \left(\begin{array}{rrrr} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \end{array} \right)^{-1}=(1,0,0,0)=x^3 \ . $$ Таким образом, $ j=4_{} $, а истинное значение блока: $ X_4=(0,1,1,0)+(1,0,1,0)=(1,1,0,0) $. ♦ Распространение предложенного подхода на большее количество испорченных блоков потребует уже существенной изощренности. Предположим, что в процессе коммуникации информационной строки $ X_{} $ испортилось содержимое блоков с номерами $ j_{} $ и $ k_{} $ при $ j \ne k $. Поскольку теперь количество неизвестных в задаче возрастает до четырех ( $ j,k,X_j,X_k $), то можно ожидать, что для восстановления значений этих неизвестных нам потребуются столько же уравнений, т.е. необходимо вычислять значения (как минимум) четырех синдромов. Действуя по аналогии с предыдущим, будем вычислять эти синдромы по правилам: $$ \left\{ \begin{array}{lllllcl} X_1& + X_2 &+ X_3& + X_4& + X_5&=&S_1, \\ X_1&+ X_2\mathfrak a&+ X_3 \mathfrak a^2&+ X_4\mathfrak a^3&+ X_5\mathfrak a^4&=&S_2, \\ X_1&+ X_2\mathfrak a^2&+ X_3 \mathfrak a^4&+ X_4\mathfrak a^6&+ X_5\mathfrak a^8&=&S_3,\\ X_1&+ X_2\mathfrak a^3&+ X_3 \mathfrak a^6&+ X_4\mathfrak a^{9}&+ X_5\mathfrak a^{12}&=&S_4. \end{array} \right. $$ Если величины тех же синдромов на выходе канала связи стали равны $ \{\tilde S_i\}_{i=1}^4 $ и хотя бы для одного из них $ \tilde S_i \ne S_i $, то получаем уравнения для определения испорченных блоков $ X_j,X_k $ в виде: $$ \left\{ \begin{array}{llcl} (X_j+\tilde X_j)& + (X_k+\tilde X_k) &=&S_1 +\tilde S_1, \\ (X_j+\tilde X_j)\mathfrak a^{j-1}& + (X_k+\tilde X_k)\mathfrak a^{k-1} &=&S_2 +\tilde S_2, \\ (X_j+\tilde X_j)\mathfrak a^{2(j-1)}& + (X_k+\tilde X_k)\mathfrak a^{2(k-1)} &=&S_3 +\tilde S_3, \\ (X_j+\tilde X_j)\mathfrak a^{3(j-1)}& + (X_k+\tilde X_k)\mathfrak a^{3(k-1)} &=&S_4 +\tilde S_4. \end{array} \right. $$ Определим сначала из этой системы величины $ j_{} $ и $ k_{} $. Поскольку последние входят в уравнения существенно нелинейным образом, будем искать их через посредство $ \mathfrak a^{j-1} $ и $ \mathfrak a^{k-1} $: найдем уравнение, которому удовлетворяют эти элементы поля $ \mathbf{GF}(16) $. Будем искать его в виде квадратного уравнения $$ \sigma_0\mathfrak e + \sigma_1\mathfrak x + \sigma_2\mathfrak x^2 = \mathfrak o $$ с пока неопределенными коэффициентами $ \{ \sigma_0, \sigma_1, \sigma_2 \}\subset \mathbf{GF}(16) $. Для определения этих коэффициентов домножим равенства, которые получаются из этого уравнения подстановками $ \mathfrak x =\mathfrak a^{j-1} $ и $ \mathfrak x =\mathfrak a^{k-1} $: $$ \left\{ \begin{array}{rl|llc} \sigma_0\mathfrak e+\sigma_1\mathfrak a^{j-1}+\sigma_2\mathfrak a^{2(j-1)}&=0, & \times (X_j+\tilde X_j) & & \\ & & & & + \\ \sigma_0\mathfrak e+\sigma_1\mathfrak a^{k-1}+\sigma_2\mathfrak a^{2(k-1)}&=0 & \times (X_k+\tilde X_k) & & \end{array} \right. $$ и сложим. С учетом приведенных выше соотношений, получим: $$ \sigma_0(S_1 +\tilde S_1)+\sigma_1(S_2 +\tilde S_2)+\sigma_2(S_3 +\tilde S_3)= \mathfrak o \ . $$ Еще раз домножим уравнения: $$ \left\{ \begin{array}{rl|llc} \sigma_0\mathfrak e+\sigma_1\mathfrak a^{j-1}+\sigma_2\mathfrak a^{2(j-1)}&=0, & \times (X_j+\tilde X_j)\mathfrak a^{j-1} & & \\ & & & & + \\ \sigma_0\mathfrak e+\sigma_1\mathfrak a^{k-1}+\sigma_2\mathfrak a^{2(k-1)}&=0 & \times (X_k+\tilde X_k)\mathfrak a^{k-1} & & \end{array} \right. $$ и сложим --- получаем уравнение $$ \sigma_0(S_2 +\tilde S_2)+\sigma_1(S_3 +\tilde S_3)+\sigma_2(S_4 +\tilde S_4)= \mathfrak o \ . $$ Из двух уравнений можно определить набор коэффициентов $ \sigma_0, \sigma_1, \sigma_2 $ с точностью до общего сомножителя; получившееся уравнение можно представить с помощью определителя третьего порядка: $$ \left| \begin{array}{ccc} S_1 +\tilde S_1 & S_2 +\tilde S_2 & S_3 +\tilde S_3 \\ S_2 +\tilde S_2 & S_3 +\tilde S_3 & S_4 +\tilde S_4 \\ 1 & \mathfrak x & \mathfrak x^2 \end{array} \right|= \mathfrak o \ . $$ Если нам удастся найти решения $ \mathfrak x_1, \mathfrak x_2 $ этого уравнения, то позиции ошибок найдутся из уравнений $ \mathfrak a^{j-1}=\mathfrak x_1, \mathfrak a^{k-1}=\mathfrak x_2 $ с помощью "таблицы логарифмов" из ☞ ((#возведение_в_степень ПУНКТА)). После нахождения значений $ j_{} $ и $ k_{} $ истинные значения испорченных блоков восстанавливаются из системы линейных уравнений $$ \left\{ \begin{array}{llcl} (X_j+\tilde X_j)& + (X_k+\tilde X_k) &=&S_1 +\tilde S_1, \\ (X_j+\tilde X_j)\mathfrak x_1& + (X_k+\tilde X_k)\mathfrak x_2 &=&S_2 +\tilde S_2. \end{array} \right. $$ !!П!! **Пример.** Пусть на выходе канала связи получена информационная строка, разбиение которой на блоки имеет вид: $$ \tilde X_1=(1,1,1,1),\ \tilde X_2=(1,1,1,1),\ \tilde X_3=(1,1,1,1),\ \tilde X_4=(1,0,1,1),\ \tilde X_5=(0,1,1,0)\ . $$ В предположении, что количество испорченных блоков равно двум, найти их позиции и исправить их содержимое, если значения синдромов: $$ \begin{array}{|c|c|c|c|c|} \hline j & 1 & 2 & 3 & 4 \\ \hline S_j & (0,1,0,0) & (0,1,1,1) & (1,1,0,1) & (0,1,1,0) \\ \hline & & & & \\ \tilde S_j & (0,0,1,0) & (0,1,1,0) & (0,1,0,0) & (0,0,0,0) \\ \hline \end{array} $$ Вычисления произведены в поле Галуа из предыдущего примера. **Решение.** Составляем уравнение $$ \left| \begin{array}{ccc} S_1 +\tilde S_1 & S_2 +\tilde S_2 & S_3 +\tilde S_3 \\ S_2 +\tilde S_2 & S_3 +\tilde S_3 & S_4 +\tilde S_4 \\ 1 & \mathfrak x & \mathfrak x^2 \end{array} \right|= \mathfrak o \quad \iff \quad \left| \begin{array}{ccc} (0,1,1,0) & (0,0,0,1) & (1,0,0,1) \\ (0,0,0,1) & (1,0,0,1) & (0,1,1,0) \\ 1 & \mathfrak x & \mathfrak x^2 \end{array} \right|= \mathfrak o $$ $$ \iff \quad \mathfrak x^2 (0,0,1,0)+ \mathfrak x (1,1,1,0)+(1,0,1,1) = \mathfrak o \quad \iff \quad \mathfrak x^2 \cdot x + \mathfrak x \cdot x^{11}+ x^7 = \mathfrak o \ . $$ Подстановкой убеждаемся, что корнями этого уравнения являются $ \mathfrak x_1 = x^2 $ и $ \mathfrak x_2 = x^4 $. Следовательно, $ j=3 $ и $ k=5 $ --- номера испорченных блоков. Теперь из системы уравнений $$ \left\{ \begin{array}{llcl} (X_3+\tilde X_3)& + (X_5+\tilde X_5) &=&x^2+x, \\ (X_3+\tilde X_3)x^2& + (X_5+\tilde X_5)x^4 &=&1 \end{array} \right. $$ находим выражения для $ X_3+\tilde X_3 $ и $ X_5+\tilde X_5 $. **Ответ.** $ X_3=(0,0,0,0), X_5=(1,1,1,1) $. В приведенных выше рассуждениях имеется, однако, один изъян. Мы неявно предполагали, что в процессе коммуникации искажению подвергаются исключительно только блоки информационной строки, но никак не значения синдромов $ S_1,S_2,\dots $ Между тем, эти блоки тоже должны участвовать в процессе коммуникации и, следовательно, подвергаются искажениям наряду с $ X_1,X_2,\dots $ Алгоритм же корректировки ошибок, предложенный выше, предполагает достоверное знание значений синдромов --- до коммуникации и после нее[[Если только не предполагать наличие дополнительного канала связи повышенной помехоустойчивости, выделенного для передачи значений синдромов.]]. Как преодолеть это препятствие? Для пояснения идеи подвергнем предложенный алгоритм вспомогательной формализации. Введем в рассмотрение переменную $ \mathfrak x $, которая может принимать значения из поля $ \mathbf{GF}(16) $. Рассмотрим выражение $$ G(\mathfrak x)= X_1 + X_2 \mathfrak x+X_3 \mathfrak x^2+ X_4 \mathfrak x^3+ X_5 \mathfrak x^4 \ . $$ По аналогии с объектом из бесконечных полей, его можно назвать полиномом по переменной $ \mathfrak x $ над полем $ \mathbf{GF}(16) $. Тогда величины синдромов $ S_j $ представляют собой значения полинома $ G(\mathfrak x) $: $$ S_1 = G(\mathfrak e),\ S_2 = G(\mathfrak a),\ S_3 = G(\mathfrak a^2),\dots $$ Ключевая идея помехоустойчивого кодирования заключается в том обстоятельстве, что к процессу коммуникации допускаются только строки с заранее предписанными значениями $ \{ g(\mathfrak a^{\ell}) \} $, например те, для которых $ g(\mathfrak a^{\ell})=\mathfrak o $ при заранее заданном полиноме $ g(\mathfrak x) $. Как этого можно добиться? --- Например, в нашем дежурном примере коммуникации $ 5_{} $ четырехбитных информационных блоков $ (X_1,X_2,X_3,X_4,X_5) $ по каналу связи с возможностью исправления одного блока, строкой для пересылки можно взять строку $ (Y_1,Y_2,Y_3,Y_4,Y_5,Y_6,Y_7) $, формируемую по правилу: $$ Y_1+Y_2\mathfrak x+Y_3\mathfrak x^2+\dots+ Y_7\mathfrak x^6 \equiv G(\mathfrak x)(\mathfrak x + \mathfrak e)(\mathfrak x + \mathfrak a)\equiv $$ $$ \equiv (X_1 + X_2 \mathfrak x+X_3 \mathfrak x^2+ X_4 \mathfrak x^3+ X_5 \mathfrak x^4)(\mathfrak x + \mathfrak e)(\mathfrak x + \mathfrak a) $$ при произвольном примитивном элементе поля $ \mathfrak a $. Содержимое блока $ Y_{i} $ зависит линейно от информационных блоков $ \{X_{\ell}\}_{\ell=1}^5 $; коэффициентами в этих зависимостях являются элементы поля $ \mathbf{GF}(16) $. Таким образом, избыточность сообщения оказывается такой же, как и в разобранном выше случае вычисления двух синдромов по правилу $$ \left\{ \begin{array}{lllllcl} X_1& + X_2 &+ X_3& + X_4& + X_5 &=& S_1, \\ X_1 &+ X_2\mathfrak a&+ X_3 \mathfrak a^2&+ X_4\mathfrak a^3&+X_5\mathfrak a^4&=& S_2. \end{array} \right. $$ Вместо строки $ (X_1,X_2,X_3,X_4,X_5,\, S_1,S_2) $ к процессу коммуникации допускается строка $ (Y_1,Y_2,Y_3,Y_4,Y_5,Y_6,Y_7) $, которая, хотя и формируется более сложным способом, тем не менее является более подходящей с точки зрения восстановимости утерянной информации. Если по прохождении по каналу связи на выходе получаем строку $ (\tilde Y_1, \tilde Y_2, \tilde Y_3, \tilde Y_4, \tilde Y_5, \tilde Y_6, \tilde Y_7) $, для которой не выполняется хотя бы одно из условий $$ \left\{ \begin{array}{lllllllcll} \tilde Y_1& + \tilde Y_2 &+ \tilde Y_3& + \tilde Y_4& + \tilde Y_5& + \tilde Y_6& + \tilde Y_7 &=& \tilde S_1 &= \mathfrak o, \\ \tilde Y_1 &+ \tilde Y_2\mathfrak a&+ \tilde Y_3 \mathfrak a^2&+ \tilde Y_4\mathfrak a^3&+\tilde Y_5\mathfrak a^4 & + \tilde Y_6\mathfrak a^5 & + \tilde Y_7 \mathfrak a^6 &=&\tilde S_2 &= \mathfrak o, \end{array} \right. $$ то делаем заключение о наличии ошибки передачи. Далее, в предположени единственности испорченного блока, ищем его местоположение по разобранному выше алгоритму. В настоящем пункте сделан набросок метода помехоустойчивого кодирования известного под названием ((:codes:cyclic:bch#коды_рида-соломона кода Рида-Соломона)). Для выхода на необходимый уровень строгости изложения нам потребуется узаконить объект, который был //((http://ru.wikipedia.org/wiki/%D1%E0%EF%E0 тихой сапой))// перетащен из теории бесконечных полей --- это полином с коэффициентами из поля Галуа. ===Уравнения нелинейные== Рассмотрим $ 5_{} $ различных элементов поля $ \mathbf{GF}(16) $; воспользуемся их ((#поле_галуа_gf_16_версия_для_программистов изначальным представлением)) в виде 4-хразрядных строк $ \mathfrak a_j=(A_{j0},A_{j1},A_{j2},A_{j3}) $ при $ j\in \{0,1,2,3,4\},\{ A_{jk} \}_{j,k} \subset \{0,1\} $. Рассматриваемые как векторы ((:linear_space#определения линейного пространства)) $ \mathbb R^4 $, они должны быть ((:linear_space#линейная_зависимость_базис_координаты линейно зависимыми)): существуют скаляры $ \{ \tilde{\alpha}_j \}_{j=0}^4 \subset \mathbb R $ такие, что $$ \tilde{\alpha}_0 \mathfrak a_0+\tilde{\alpha}_1 \mathfrak a_1+\tilde{\alpha}_2 \mathfrak a_2+ \tilde{\alpha}_3 \mathfrak a_3+\tilde{\alpha}_4 \mathfrak a_4=(0,0,0,0) \ . $$ Можно быстро доказать что, ввиду целочисленности разрядов строк, скаляры $ \{\tilde{\alpha}_j\} $ также могут быть выбраны целочисленными. Тогда, переходя в векторном равенстве к сравнению по модулю $ 2_{} $, получим равенство для элементов поля $ \mathbf{GF}(16) $ $$ \alpha_0 \mathfrak a_0+\alpha_1 \mathfrak a_1+\alpha_2 \mathfrak a_2+\alpha_3 \mathfrak a_3+\alpha_4 \mathfrak a_4 = \mathfrak o \ , $$ справедливое при некоторых значениях скаляров $ \{ \alpha_{j} \}_{j=0}^4 \subset \{0,1\} $. Если теперь возьмем в качестве элементов поля степени одного-единственного: $ \mathfrak a_j = \mathfrak a^j $ при $ \mathfrak a \ne \mathfrak o $ и $ j\in \{0,1,2,3,4\} $, то придем к заключению, что элемент $ \mathfrak a $ должен удовлетворять некоторому алгебраическому уравнению $ F(\mathfrak x) = \mathfrak o $ степени $ \le 4 $ при $$ F(\mathfrak x)= \alpha_0 \mathfrak e+\alpha_1 \mathfrak x+\alpha_2 \mathfrak x^2+\alpha_3 \mathfrak x^3+\alpha_4 \mathfrak x^4 \quad u \quad \{ \alpha_{j} \}_{j=0}^4 \subset \{0,1\} \ . $$ !!§!! Переменную в полиноме обозначил готической буквой $ \mathfrak x $ чтобы отличать от переменной в ((#умножение полиномиальном представлении элементов поля)). Представление для полинома $ F_{} $ можно получить разными способами, я привожу самое наглядное[[ Хотя и не оптимальное с вычислительной точки зрения]]: $$ F(\mathfrak x)= \left| \begin{array}{lllll} A_{00} & A_{01} & A_{02} & A_{03} & \mathfrak e\\ A_{10} & A_{11} & A_{12} & A_{13} & \mathfrak x\\ A_{20} & A_{21} & A_{22} & A_{23} & \mathfrak x^2\\ A_{30} & A_{31} & A_{32} & A_{33} & \mathfrak x^3\\ A_{40} & A_{41} & A_{42} & A_{43} & \mathfrak x^4 \end{array} \right| \pmod{2} \ . $$ ((:algebra2:dets#миноры_и_алгебраические_дополнения Разложив этот определитель по последнему столбцу)), получим требуемое. Теперь проверим на примерах, насколько эти рассуждения конструктивны --- не получится ли так, что все коэффициенты $ F(\mathfrak x) $ обратятся в нуль? !!П!! **Пример.** Пусть поле $ \mathbf{GF}(16) $ построено на основе умножения по двойному модулю $ 2, f(x) $ при $ f(x)=x^4+x+1 $, и пусть $ \mathfrak a = (0,1,0,1) $. Имеем: $$ \mathfrak a^2=(0,0,1,0),\ \mathfrak a^3=(1,0,1,0),\ \mathfrak a^4=(0,1,0,0) \ , $$ и $$ F(\mathfrak x)\equiv_{_2} \left| \begin{array}{ccccl} 0 & 0 & 0 & 1 & \mathfrak e\\ 0 & 1 & 0 & 1 & \mathfrak x\\ 0 & 0 & 1 & 0 & \mathfrak x^2\\ 1 & 0 & 1 & 0 & \mathfrak x^3\\ 0 & 1 & 0 & 0 & \mathfrak x^4 \end{array} \right| \equiv_{_2} $$ $$ \equiv_{_2} \mathfrak e \left| \begin{array}{cccc} 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{array} \right|+ \mathfrak x \left| \begin{array}{ccccl} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{array} \right|+ \mathfrak x^2 \left| \begin{array}{cccc} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{array} \right|+ \mathfrak x^3 \left| \begin{array}{cccc} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{array} \right|+ \mathfrak x^4 \left| \begin{array}{cccc} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ \end{array} \right| \equiv_{_2} $$ $$ \equiv_{_2} \mathfrak x^4+\mathfrak x+\mathfrak e \ . $$ То есть мы получили тот же полином $ f_{} $, с помощью которого было построено поле! --- Неожиданный результат, который хочется подвергнуть дополнительной проверке. Проверка для элементов $ \mathfrak a^2=(0,0,1,0) $ и $ \mathfrak a^4=(0,1,0,0) $ приводит к тому же полиному $ f_{} $, но вот для $ \mathfrak a^3=(1,0,1,0) $ получаем другой результат: $$ F(\mathfrak x) =\mathfrak x^4+\mathfrak x^3+\mathfrak x^2+\mathfrak x+ \mathfrak e \ . $$ Еще пара проверок: $$ \mathfrak a=(1,0,1,1) \quad \Rightarrow \quad F(\mathfrak x) =\mathfrak x^4+\mathfrak x^3+ \mathfrak e \ ; $$ $$ \mathfrak a=(0,1,1,0) \quad \Rightarrow \quad F(\mathfrak x) =\mathfrak x^2+\mathfrak x+ \mathfrak e \ . $$ В последнем случае приходится немного повозиться, потому как построение полинома $ F(\mathfrak x) $ в виде определителя $ 5_{} $-го порядка приводит к тождественно нулевому полиному... ♦ Теперь подтвердим полученные результаты, основываясь на ((#матрицы матричном формализме)) поля Галуа. Фундаментальным результатом теории матриц является ((:algebra2:charpoly#теорема_гамильтона-кэли теорема Гамильтона-Кэли)): матрица $ A_{n\times n} $ является корнем своего характеристического полинома, т.е. если $$ \det (A-xE) \equiv (-1)^n(x^n+a_1x^{n-1}+\dots+a_n) $$ при $ E_{} $ --- ((:algebra2#единичная единичной матрице)) порядка $ n_{} $, то $$ A^n+a_1A^{n-1}+\dots+a_nE \equiv \mathbb O_{n\times n} \ . $$ !!П!! **Пример.** Поле $ \mathbf{GF}(16) $ --- то же, что и в предыдущем примере. Элементу поля $ \mathfrak a = (0,1,0,1) $ сопоставляется матрица $$ \mathbf A= \left( \begin{array}{rrrr} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array} \right) \ . $$ Вычислим ее характеристический полином: $$ \det (\mathbf A-\mathfrak x E) = \left| \begin{array}{cccc} 1- \mathfrak x & 1 & 1 & 0 \\ 0 & 1-\mathfrak x & 1 & 1 \\ 1 & 0 & 1-\mathfrak x & 0 \\ 0 & 1 & 0 & 1-\mathfrak x \end{array} \right| \equiv \mathfrak x^4 -4\, \mathfrak x^3+ 4\, \mathfrak x^2 - \mathfrak x +1 \equiv_{_2} \mathfrak x^4 + \mathfrak x +1 \ . $$ Получили тот же самый полином, что и в предыдущем примере. Но вот с другим элементом получается результат, отличный от полученного ранее: $$ \mathfrak a=(0,1,1,0) \quad \Rightarrow \quad \det (\mathbf A-\mathfrak x E)\equiv_{_2} \mathfrak x^4 + \mathfrak x^2 +1 \ . $$ Тем не менее, и для этого результата найдется объяснение из теории матриц: $$\mathfrak x^4 + \mathfrak x^2 +1 \equiv_{_2} (\mathfrak x^2+\mathfrak x+1)^2 , $$ и полином $ \mathfrak x^2+\mathfrak x+1 $ является ((:mapping:operator:jordan#аннулирующий_полином минимальным аннулирующим)) для матрицы $ \mathbf A_{} $. Вполне предсказуем и результат для элемента поля $ \mathfrak a=(0,0,1,0)=x $ --- матрица Фробениуса $ \mathbf F $ имеет ((:algebra2:charpoly#характеристический_полином просто вычисляемый характеристический полином)): $$ \left| \begin{array}{cccc} - \mathfrak x & 0 & 1 & 1 \\ 1 & 1-\mathfrak x & 0 & 0 \\ 0 & 1 & 1-\mathfrak x & 0 \\ 0 & 0 & 1 & 1-\mathfrak x \end{array} \right| \equiv \mathfrak x^4+\mathfrak x+1 $$ ♦ Основываясь на этих (весьма неполных) экспериментальных данных, сделаем общие выводы: 1. Любой ненулевой элемент поля является корнем некоторого полинома $ F(\mathfrak x) $, степень которого равна одному из чисел: $ \{1,2,4\} $. 2. Если $ \mathfrak a $ --- корень полинома $ F(\mathfrak x) $, то и $ \mathfrak a^2, \mathfrak a^4,\mathfrak a^8,\dots $ будут корнями этого полинома[[Понятно, что эта последовательность является циклической?]]. 3. Все возможные полиномы, корнями которых могут быть элементы поля, являются делителями по модулю $ 2_{} $ полинома $ x^{15}-1 $: $$ x^{15}-1 \equiv_{_{2}} (x-1)\underbrace{(x^2+x+1)}_{f_{_4}(x)}\underbrace{(x^4+x+1)}_{\equiv f(x)}\underbrace{(x^4+x^3+1)}_{\equiv f^{\ast}(x)} \underbrace{(x^4+x^3+x^2+x+1)}_{\equiv f_{_3}(x)}\ . $$ Нечто подобного можно было бы ожидать, если вспомнить упомянутую выше ((#возведение_в_степень обобщенную теорему Ферма)): для любого элемента поля $ \mathfrak a \ne \mathfrak o $ выполняется $ \mathfrak a^{15} = \mathfrak e $. Не столь очевиден следующий вывод: 4. Полиномы, стоящие в правой части разложения полинома $ x^{15}-1 $, являются неприводимыми полиномами. Степени неприводимых полиномов являются делителями числа $ 4_{} $. Именно эти полиномы указаны в последнем столбце таблицы, приведенной в примере из ☞ ((#возведение_в_степень ПУНКТА)). Попробуем теперь обсудить полученные в настоящем пункте выводы, переведя их на язык альтернативного представления элементов поля $ \mathbf{GF}(16) $, а именно --- как полиномов $ A_0x^3+A_1x^2+A_3x+1 $. Получилось, что эти полиномы сами являются корнями некоторых полиномов от другой переменной $ \mathfrak x $! В самом деле, подставим $ \mathfrak x=x^3+1 $ в полином $ \mathfrak x^4+\mathfrak x^3+\mathfrak e $ и проведем все вычисления по двойному модулю $ 2,f(x)=x^4+x+1 $ с использованием таблицы из ☝ ((#возведение_в_степень ПУНКТА)): $$(x^3+1)^4+(x^3+1)^3+1 \equiv_{_2} x^{12}+1+x^{9}+x^{6}+x^3+1+1\equiv_{_2,f} $$ $$ \equiv_{_2,f}\underbrace{(x^3+x^2+x+1)}_{\equiv x^{12}}+\underbrace{(x^3+x)}_{\equiv x^{9}}+\underbrace{(x^3+x^2)}_{\equiv x^{6}}+x^3+1 \equiv_{_2} 0 \ . $$ Теперь попробуем провести проверку с другой стороны --- попробуем разложить какой-нибудь из неприводимых полиномов на ((:polynomial#корни линейные множители)). Возьмем, к примеру полином $ f_3(\mathfrak x)=\mathfrak x^4+\mathfrak x^3+\mathfrak x^2+\mathfrak x+\mathfrak e $. Согласно последнему столбцу таблицы из ☝ ((#возведение_в_степень ПУНКТА)), его корнями являются полиномы $ x^3,\ x^6,\ x^9,\ x^{12} $. Вычислим произведение $$(\mathfrak x+x^3)(\mathfrak x+x^6)(\mathfrak x+x^9)(\mathfrak x+x^{12}) = $$ $$= \mathfrak x^4+(x^3+x^6+x^9+x^{12})\mathfrak x^3+(x^9+x^{12}+x^{15}+x^{15}+x^{18}+x^{21})\mathfrak x^2+ (x^{18}+x^{21}+x^{24}+x^{27})\mathfrak x + x^{30} \ . $$ Имеем, $$ x^{30} \equiv_{_{2,f}} 1,\ x^3+x^6+x^9+x^{12} \equiv_{_{2,f}} x^3+(x^3+x^2)+(x^3+x)+(x^3+x^2+x+1)\equiv_{_2} 1,\dots , $$ т.е. противоречий не получаем. Идем далее. До сих пор примеры полиномов $ F(\mathfrak x) $, которые нам попадались в настоящем пункте, имели коэффициенты $ 0_{} $ или $ 1_{} $, или, как говорят, были полиномами над полем $ \mathbf{GF}(2) $. А нам в предыдущем ((#места_потерь_неизвестны ПУНКТЕ)) пришлось столкнуться с необходимость решения уравнений $ F(\mathfrak x)= \mathfrak o $, коэффициентами которых были элементы поля $ \mathbf{GF}(16) $. Что можно сказать о таких уравнениях? --- Можно ли утверждать, что они имеют решения в том же поле? Если да, то как эти решения найти? !!П!! **Пример.** В поле $ \mathbf{GF}(16) $ с умножением, определенным по модулю __любого__ неприводимого (по модулю $ 2_{} $) полинома $ f_{}(x) $ степени $ 4_{} $, существует решение уравнения $ \mathfrak x^2 + \mathfrak a = \mathfrak o $ относительно $ \mathfrak x $ при любом значении $ \mathfrak a \in \mathbf{GF}(16) $. Иными словами, существует "корень квадратный" из любого элемента поля. Для доказательства, вспомним, что элемент $ \mathfrak a $ можно представить в виде степени примитивного элемента поля: $ \mathfrak a = \mathfrak A^k $. Очевидно, что $$ \sqrt{\mathfrak a}= \left\{ \begin{array}{rl} \mathfrak A^{k/2} & npu \ k\ \mbox{четном} , \\ \mathfrak A^{(15+k)/2} & npu \ k\ \mbox{нечетном} , \end{array} \right. $$ и это --- единственное значение квадратного корня. С другой стороны, не существует корней у уравнения $ \mathfrak x^2+x\cdot \mathfrak x+ \mathfrak e= \mathfrak o $ при выборе в качестве "генерирующего умножение" неприводимого полинома $ f(x)=x^4+x+1 $. Проверить это утверждение удается только перебором всех элементов поля: ((:complex_num#квадратный_корень формула дискриминанта)) для квадратного уравнения в $ \mathbf{GF}(16) $ не работает[[Почему? --- А попробуйте ее вывести! (Если забыли как выводится --- см. ☞ ((:complex_num#квадратный_корень ЗДЕСЬ)) ).]]. У того же уравнения существуют два корня, именно $ \mathfrak x=x^2 $ и $ \mathfrak x=x^{13} $, при выборе в качестве неприводимого полинома $ f(x)=x^4+x^3+1 $. ♦ !!?!! Доказать, что полином $ \mathfrak x^2+\mathfrak a_1 \mathfrak x+ \mathfrak a_2 $ над $ \mathbf{GF}(16) $ при $ \mathfrak a_1 \ne \mathfrak o $ либо не имеет корней в этом же поле, либо имеет два различных. Какие результаты можно перенести из теории полиномов над бесконечными полями? --- Прежде всего, проверим один полезный результат, связанный с делимостью полиномов. Допустим, что для полинома $ F(\mathfrak x) $ степени $ \ge 2 $ найден корень $ \mathfrak x=\mathfrak x_1 $, т.е. $ F(\mathfrak a_1)= \mathfrak o $. Будет ли справедлива ((:polynomial#корни теорема Безу)): $$ F(\mathfrak x) \equiv (\mathfrak x + \mathfrak a_1) F_1(\mathfrak x) \ ? $$ Здесь $ \equiv_{} $ означает тождественное равенство (т.е. равенство справедливое при $ \forall \mathfrak x \in \mathbf{GF}(16) $), а $ F_1(\mathfrak x) $ --- полином над $ \mathbf{GF}(16) $ степени, равной $ \deg F-1 $. Ответ оказывается положительным и доказательство основывается на ((:polynomial#схема_хорнера схеме Хорнера)). !!П!! **Пример.** В $ \mathbf{GF}(16) $ с умножением, определенным по модулю $ x^4+x+1 $ полином $$ F(\mathfrak x) =\mathfrak x^3+(x^2+x)\,\mathfrak x^2+(x^2+x+1)\, \mathfrak x+ (x^3+x+1) $$ имеет корень $ x_{}+1 $. Проверить это утверждение и найти полином $ F_1(\mathfrak x) $ из предыдущего тождества. **Решение.** Строим схему Хорнера: $$ \begin{array}{c|cccc} & 1& x^2+x & x^2+x+1 & x^3+x+1 \\ \hline x_{}+1 & 1 & x^2+1 & x^3 & 0 \end{array} $$ Таким образом, действительно $$ F(x+1)=\mathfrak o \quad u \quad F_1(\mathfrak x)=\mathfrak x^2+(x^2+1)\mathfrak x+x^3 \ . $$ ♦ !!Т!! **Теорема.** //Полином// $ F(\mathfrak x) $ //над полем// $ \mathbf{GF}(16) $ //степени// $ \deg F \ge 1 $ //имеет не более// $ \deg F $ //корней в этом поле//. ==Задачи== ☞ ((:gruppe:galois:vspom4:problems ЗДЕСЬ))