Мы предполагаем, что читатель владеет понятиями группа, кольцо, поле. Поэтому очень кратко изложим элементы теории с нужными нам для дальнейшего акцентами.
В основе всех понятий, изучаемых в различных разделах алгебры, лежит понятие алгебраической операции.
Пусть $$G$$ - множество (элементами $$G$$ могут быть числа или функции или объекты геометрической природы и т.д.).
Определение 3.1 Говорят, что на $$G$$ задана бинарная алгебраическая операция, если любой упорядоченной паре $$(a,b)$$ элементов $$a,b\in G$$ ставится в соответствие однозначно определённый элемент $$f(a,b)$$ этого же множества $$G$$.
Определение 3.2 Группоидом называется всякое непустое множество, в котором задана алгебраическая операция.
Иногда вместо $$f(a,b)$$ пишут $$afb$$, а ещё чаще бинарную операцию на $$G$$ обозначают каким-нибудь специальным символом: $$\ast$$, $$\circ$$, $$\cdot$$, $$+$$, так будем поступать и мы, называя $$a\cdot b$$ (или просто $$ab$$) произведением элементов $$a$$ и $$b$$. Таким образом, равенство
$$ab=c$$будет в дальнейшем иметь следующий смысл: упорядоченной паре $$a,b$$ из $$G$$ ставится в соответствие элемент $$c$$. Иногда (там, где это будет удобнее) вместо "произведение" будем заменять на "сумму", см. таблицу 3.1.
Замечание 1. Можно рассматривать бинарную операцию в "широком смысле": некоторым упорядоченным парам элементов из $$G$$ ставится в соответствие один или несколько элементов из $$G$$. Такой, более общий подход "имеет право на существование", он приводит к интересным результатам, однако мы, исходя из наших целей, будем придерживаться понятия алгебраической операции, приведённого выше.
Замечание 2. Наряду с бинарными алгебраическими операциями имеет смысл рассматривать и более общие $$n$$-арные операции (унарные при $$n=1$$, тернарные при $$n=3$$, и т.д.), а также и их комбинации. Нас же будут интересовать, за редкими исключениями, именно бинарные операции.
На множестве $$G$$ можно задать много различных операций. Если хотят выделить одну из них, то пишут $$(G,\ast)$$.
Пример 3.1
Для задания группоида нужно задать множество $$G$$ и то правило, по которому можно найти значение операции $$\ast$$ для любых двух элементов из $$G$$. В том случае, когда множество $$G$$ конечно, всю эту информацию можно записать таблицей, в которой входной строкой и входным столбцом является список элементов множества $$G$$, а на пересечении строки с входом $$a$$ и столбца с входом $$b$$ располагается значение операции $$a\ast b$$.
Такая таблица называется таблицей Кэли для группоида $$(G; \ast)$$ в честь английского математика Артура Кэли (1821-1895). Если $$G=\{a_1,\ldots,a_n\}$$, то таблица Кэли для группоида $$(G,\ast)$$ имеет следующий вид:
| $$\ast$$ | $$a_1$$ | $$\cdots$$ | $$a_j$$ | $$\cdots$$ | $$a_n$$$ |
| $$a_1$$ | $$a_1\ast a_1$$ | $$\cdots$$ | $$a_1\ast a_j$$ | $$\cdots$$ | $$a_1\ast a_n$$ |
| $$a_2$$ | $$a_2\ast a_1$$ | $$\cdots$$ | $$a_2\ast a_j$$ | $$\cdots$$ | $$a_2\ast a_n$$ |
| $$\vdots$$ | $$\vdots$$ | $$\vdots$$ | $$\vdots$$ | ||
| $$a_n$$ | $$a_n\ast a_1$$ | $$\cdots$$ | $$a_n\ast a_j$$ | $$\cdots$$ | $$a_n\ast a_n$$ |
Исходя из такого задания группоида, легко подсчитать, сколько различных операций можно определить на множестве $$G$$ порядка $$n$$. В каждую из $$n^2$$ клеток таблицы Кэли можно записать любой из $$n$$ элементов множества $$G$$. Отсюда видно, что таблицу Кэли можно составить в $$n^{n^2}$$ вариантах, то есть на множестве $$G$$ из $$n$$ элементов существуют $$n^{n^2}$$ различных группоидов.
| Мультипликативная терминология | Аддитивная терминология |
|---|---|
| Умножение $$a\cdot b = ab$$ | Сложение $$a+b$$ |
| $$a$$, $$b$$ - множители | $$a$$, $$b$$ - слагаемые |
| Нейтральный элемент - единица ($$1$$) | Нейтральный элемент - ноль ($$0$$) |
| Обратный элемент $$a^{-1}$$ | Противоположный элемент $$-a$$ |
| $$\underbrace{a\cdot a\cdots a}_{n\ \text{раз}} = a^n$$ - степень | $$\underbrace{a+ a+\ldots +a}_{n\ \text{раз}} = n\cdot a$$ - кратное |
Определение 3.3 Элемент $$e_r$$ (или $$e_l$$) группоида $$(G, \ast)$$ называется правым (соответственно, левым) нейтральным, если $$a\cdot e_r = a$$ для любого элемента $$a\in G$$ (соответственно, $$e_l*a=a$$). Элемент $$e$$ группоида $$(G, \ast)$$ называется нейтральным, если он является одновременно левым и правым нейтральным.
Ясно, что если в группоиде существует нейтральный элемент, то он единственный.
В зависимости от терминологии (см. таблицу 3.1), нейтральный элемент могут называть единицей или нулем.
Определение 3.4 Пусть $$G$$ - группоид, $$e$$ - его правый (или левый) нейтральный элемент, и $$a\in G$$, то правым (соответственно, левым) обратным элементом для элемента $$a$$ относительно правого (или левого) нейтрального элемента $$e$$ называется такой $$b\in G$$, что $$a\ast b=e$$ (соответствено, $$b\ast a=e$$).
В общем случае в группоиде с нейтральным элементом элемент может не иметь обратных, может иметь один или несколько обратных. Более определённо вопрос о числе обратных элементов решается в группоидах с ассоциативной операцией, см. ниже.
Конструировать разные бинарные операции на множестве можно неограниченно, но задача изучения произвольных алгебраических структур слишком обща. Поэтому рассматривают структуры при некоторых естественных ограничениях.
Чаще всего нас будет интересовать выполнимость ассоциативного и коммутативного законов для операции.
Определение 3.5 Бинарная операция $$\ast$$ на множестве $$G$$ называется ассоциативной, если $$a\ast(b\ast c)=(a\ast b)\ast c$$ для всех $$a, b, c\in G$$.
Определение 3.6 Бинарная операция $$\ast$$ на множестве $$G$$ называется коммутативной, если $$a\ast b = b\ast a$$ для всех $$a, b\in G$$.
Свойства ассоциативности и коммутативности независимы. Действительно, например операция на $$m\ast n = -m-n$$ на $$\mathbb{Z}$$ является коммутативной, но не ассоциативной, а операция умножения квадратных $$n \times n$$-матриц - ассоциативна, но не коммутативна.
Пример 3.2
Определение 3.7 Множество $$G$$ с определённой на нём ассоциативной бинарной операцией $$\times$$ называется полугруппой. Полугруппа, в которой есть нейтральный элемент, называется моноидом.
Примеры полугрупп.
$$(\mathbb{N}, \cdot)$$ - моноид.
$$(\mathbb{Z}, +)$$ - моноид.
$$(\mathbb{N}, {\nabla})$$, где $$a{\nabla}b=НОК(a, b)$$.
$$(\mathbb{R}, {\vee})$$, где $$a{\vee}b=\max\{a, b\}$$.
Пусть $$G$$ - произвольное (непустое) множество. Зададимся вопросом: можно ли превратить $$G$$ в полугруппу? Другими словами, можно ли задать на $$G$$ какую-нибудь ассоциативную операцию? Ответ утвердительный. Более того, если $$G$$ неодноэлементно, то это можно сделать многими способами, а при бесконечном $$G$$ - бесконечным числом способов. Укажем несколько таких способов.
Пусть $$A$$ - произвольное (непустое) множество. Будем называть $$A$$ алфавитом, а элементы $$A$$ - буквами. Через $$F(A)$$ обозначим множество всех конечных последовательностей букв из $$A$$. Зададим на $$F(A)$$ операцию умножения, полагая $$(a_1,\dots,a_m)\times (b_1, \dots, b_n)=(a_1,\dots,a_m,b_1,\dots,b_n)$$. Легко видеть, что эта операция (называемая иногда конкатенацией, то есть сцеплением) ассоциативна (упражнение: проверить), так что $$F(A)$$ становится полугруппой, которая называется свободной полугруппой над алфавитом $$A$$. Другое употребительное обозначение для нее : $$A^+$$. Отождествляя последовательность из одной буквы с самой этой буквой и опуская в записи знак для конкатенации, элементы свободной полугруппы записывают в виде $$a_1a_2\dots a_m$$ и называют словами. По определению, слова $$a_1a_2\dots a_m$$ и $$c_1c_2\dots c_k$$ равны, если $$m = k$$ и $$a_i=c_i$$ при $$i = 1,{\ldots}, m$$.
Свободные полугруппы играют важную роль как в общей теории полугрупп, так и в приложениях. Их прикладная роль объясняется, в частности, тем, что во многих процессах передачи информации передаваемые сообщения представляют собой цепочки символов ("реальных" букв или слов, других кодовых знаков, электрических сигналов и т.д.) и соединение двух таких цепочек есть не что иное, как конкатенация слов в подходящей свободной полугруппе. Свободные полугруппы (главным образом, над конечными алфавитами) являются исходным объектом в теории формальных языков и теории кодов, существенна их роль в теории автоматов. При этом обычно к элементам полугруппы $$F(A)$$ добавляют так называемое пустое слово, не содержащее букв и играющее роль единицы при умножении, получается полугруппа с единицей, обозначаемая $$ A^\ast$$ и называемая свободным моноидом над алфавитом $$A$$.
Формальным языком называется произвольное подмножество некоторого свободного моноида.
Определение 3.8 Полугруппа с единицей, в которой для каждого элемента существует обратный, называется группой.
Определение 3.9 Если операция в группе $$G$$ обладает коммутативностью, т.е.
$$a\times b=b\times a{\forall}a,b \in G,$$то группа $$G$$ называется коммутативной.
Определение 3.10 Мощность множества $$G$$, на котором задана групповая операция, называется порядком группы $$G$$.
Если множество конечно, то группа $$G$$ называется конечной.
Определение 3.11 Подмножество множества $$G$$, являющееся одновременно группой относительно той же самой операции, называется подгруппой группы $$G$$.
Определение 3.11 Подгруппа $$H$$ группы $$G$$ называется тривиальной, если либо $$H=G$$, либо $$H$$ состоит из одного нейтрального элемента.
Справедлива
Теорема 3.1 (Теорема Лагранжа) Порядок $$n$$ конечной группы $$G$$ делится на порядок $$m$$ любой её подгруппы $$H$$.
Определение 3.12 Число $$|G|/|H|$$ называется индексом подгруппы $$H$$ в группе $$G$$ и обозначается $$|G:H|$$.
Определение 3.13 Полугруппы $$G$$ и $$H$$ называются изоморфными, если существует взаимно однозначное отображение $$\varphi :G\rightarrow H$$, сохраняющее операцию, то есть такое, что $$\varphi \left(a\times b\right)=\varphi \left(a\right)\times \varphi \left(b\right)$$.
Определение 3.14 Подгруппа группы $$G$$ называется максимальной, если она не содержится в других собственных (не совпадающих с $$G$$) подгруппах группы $$G$$.
Определение 3.15 Минимальная подгруппа группы $$G$$, содержащая элементы $${a}_{1},{a}_{2},{\dots},{a}_{k}$$, называется подгруппой, порождённой этими элементами, и обозначается $${\langle}{a}_{1},{\dots},{a}_{k}{\rangle}$$.
Определение 3.16 Группа $${\langle}a{\rangle}$$, порождённая одним элементом, называется циклической, и состоит из элементов $$e={a}^{0},{a},{a}^{2},{a}^{3},{\dots}$$.
Существуют две возможности: либо все степени элемента $$a$$ различны, тогда список элементов группы $${\langle}a{\rangle}$$ будет продолжаться бесконечно, либо на каком-то шаге окажется: $${a}^{n}={a}^{0}$$.
Определение 3.17 Минимальное натуральне число $$n$$ такое, что $$a^n = 1$$, называется порядком элемента $$a$$ (пишут $$|a| = n$$). Если такого $$n$$ не существует, пишут $$|a|=\infty$$.
Одновременно такое $$n$$ является порядком подгруппы $${\langle}a{\rangle}$$.
Справедливо
Следствие 3.1 (из теоремы Лагранжа) Порядок конечной группы $$G$$ делится на порядок любого её элемента.
Отметим несколько свойств циклической группы, которые пригодятся нам в дальнейшем:
Пример 3.3 Множество $$\mathbb{Z}_{11}^{*}$$ чисел от $$1$$ до $$10$$ c умножением по модулю $$11$$ образует группу. Отметим, что в этой группе нейтральным элементом является $$1$$, элемент $$10$$ имеет порядок $$2$$, поскольку $$10 \cdot 10=100 \equiv 1\mod11$$, элементы $$4, 5, 9, 3$$ имеют порядок $$5$$, а остальные элементы имеют порядок, не делящий ни $$2$$, ни $$5$$, но делящий $$10$$. То есть элементы $$2, 6, 7, 8$$ имеют порядок $$10$$, то есть $$\mathbb{Z}_{11}^{*}=\left\langle 2\right\rangle =\left\langle 6\right\rangle =\left\langle 7\right\rangle ={\langle}8{\rangle}$$.
Пример 3.4 Пусть элемент $$a$$ группы $$G$$ имеет порядок $$60$$. Найти число $${N}_{20}$$ элементов порядка $$20$$ в группе $${\langle}a{\rangle}$$? Сколько элементов являются порождающими в $${\langle}a{\rangle}$$?
Решение. По свойству 2, элементы порядка 20 лежат в подгруппе $$\left\langle {a}^{3}\right\rangle$$ и, по свойствам 3,5, не лежат в её максимальных подгруппах: $${\langle}{a}^{6}{\rangle}$$ и $${\langle}{a}^{15}{\rangle}$$. Отсюда,
$${N}_{20}=\left|\left\langle {a}^{3}\right\rangle \right|-\left|\left\langle {a}^{6}\right\rangle {\cup}\left\langle {a}^{15}\right\rangle \right|.$$Порядок элементов из $$\left\langle {a}^{6}\right\rangle {\cap}{\langle}{a}^{15}{\rangle}$$ делит и 10 и 4, следовательно, равен 1 или 2, т.е. $$\left\langle {a}^{6}\right\rangle {\cap}\left\langle {a}^{15}\right\rangle =\left\langle {a}^{30}\right\rangle$$, $$\left|\left\langle {a}^{30}\right\rangle \right|=2.$$ Отсюда,
$${N}_{20}=20-10-4+2=8.$$Число $$N_{60}$$ порождающих элементов в $${\langle}a{\rangle}$$, то есть элементов порядка 60, можно найти по формуле:
$${N}_{60}=\varphi \left(60\right)=\varphi \left(4\right)\varphi \left(3\right)\varphi \left(5\right)=2 \cdot 2 \cdot 4=16,$$где $$\varphi$$ - функция Эйлера.
Определение 3.18 Множество $$F$$ с двумя алгебраическими операциями $$+$$, $$\times$$ называется ассоциативным кольцом, если в нём выполняются свойства:
Определение 3.19 Кольца $$K$$ и $$F$$ называются изоморфными, если существует отображение $$\varphi :K\rightarrow F$$, являющееся изоморфизмом аддитивных и мультипликативных групп этих колец.
Определение 3.20 Полем называется кольцо $$F$$, в котором $${F}^{*}$$ является коммутативной группой.
Определение 3.21 Характеристикой поля называется наименьшее такое натуральное число $$p$$, что $$p \cdot 1=1+1+1+{\dots}+1=0$$, или 0, если такого $$p$$ не существует. Характеристика поля может быть только простым числом или нулем.
Определение 3.22 Левым (правым) идеалом кольца называется любое его подкольцо, выдерживающее умножение слева (соответственно, справа) на любой элемент кольца. Подкольцо, являющееся левым и правым идеалом, называется двусторонним идеалом, или просто идеалом.
Подкольцо $$I$$ разбивает кольцо $$K$$ на классы эквивалентности: $$a \equiv b\Leftrightarrow a-b \in I$$. Класс, содержащий элемент $$a$$, можно записать в виде:
$$a+I=\left\{a+x\right|x \in I\}.$$Если подкольцо является идеалом, то на множестве таких классов можно ввести операции сложения и умножения, относительно которых множество классов образует кольцо, называемое фактор-кольцом:
$$(a+I)+(b+I) = (a+b)+I,\quad (a+I)\cdot (b+I)=(a\cdot b)+I.$$Из определения идеала следует, что результат операций не зависит от выбора представителей $$a$$, $$b$$, то есть операции заданы корректно.
Наиболее важными для нас будут следующие кольца и поля:
В криптографии нас будут интересовать больше всего конечные поля, то есть поля с конечным множеством $$F$$. Перечислим наиболее важные для нас свойства:
Рассмотрим несколько связанных с кольцами вычетов задач, часто возникающих в криптографии.
Пример 3.5 Найти мультипликативный порядок элемента $$16$$ по модулю $$101$$, то есть порядок элемента $$16$$ мультипликативной группы $$\mathbb{Z}_{101}$$.
Решение. Поскольку число 101 простое, порядок мультипликативной группы поля $$\mathbb{Z}_{101}$$ равен 100. По следствию из теоремы Лагранжа, мультипликативный порядок любого числа по модулю 101 является делителем 100, то есть одним из чисел: 1, 2, 4, 5, 10, 20, 25, 50, 100. Проверим каждое из чисел:
| $$d$$ | 1 | 2 | 4 | 5 | 10 | 20 | 25 | 50 | 100 |
|---|---|---|---|---|---|---|---|---|---|
| $${16}^{d}~(\mod 101)$$ | 16 | 54 | 88 | 95 | 36 | 84 | 1 | - | - |
После того, как обнаружили, что $$16^{25}=1~(\mod 101)$$, возводить в $$50$$-ю и $$100$$-ю степень излишне - видно, что наименьшая степень, в которой 16 даст единицу по модулю 101, это 25.
Пример 3.6 Найти случайный примитивный корень по модулю $$883$$.
Решение. Порядок мультипликативной группы поля вычетов по модулю 883 равен $$882=2 \cdot 9 \cdot 49$$. Будем выбирать случайное число $$x$$ и возводить его в степени $$882/2$$, $$882/3$$, $$882/7$$. Если в какой-то степени $$x$$ даст единицу, то его порядок меньше 882, и, следовательно, он не является примитивным корнем по модулю 883. Наоборот, порядок порождающего элемента является делителем числа 882, и если он не является делителем ни одного из чисел $$882/2$$, $$882/3$$, $$882/7$$, то равен 882. В первой колонке таблицы приводятся случайно выбранные элементы $$x$$, а в следующих колонках - результаты возведения в степень.
| $$x$$ | $${x}^{\frac{882}{2}}\mod883$$ | $${x}^{\frac{882}{3}}\mod883$$ | $${x}^{\frac{882}{7}}\mod883$$ |
|---|---|---|---|
| 94 | 1 | 545 | 626 |
| 537 | 882 | 1 | 71 |
| 787 | 882 | 1 | 199 |
| 326 | 882 | 337 | 199 |
Итак, 326 является примитивным корнем по модулю 883.
Пусть $$G$$ - группа, $$a$$ - её элемент, $$b={a}^{k} \in {\langle}a{\rangle}$$. Число $$k$$ называется дискретным логарифмом элемента $$b$$ по основанию $$a$$ (пишут $$k={\log }_{a}b$$). В случае, когда $$a$$ - примитивный корень по модулю $$n$$, дискретный логарифм $$k$$ ещё называют индексом числа $$b$$ по модулю $$n$$ при основании $$a$$. Пишут: $$k=ind_{a}b$$. Когда примитивный корень $$a$$ фиксирован, можно также писать: $$k=ind\ b$$.
Дискретное логарифмирование в произвольной группе является трудноразрешимой задачей. Приведём один из примеров, когда оно всё-таки легко осуществимо.
Пример 3.7 Вычислить дискретный логарифм числа $$a=5434$$ по основанию $$5$$ по модулю $$p = 102673$$.
Решение. Порядок мультипликативной группы поля вычетов по модулю 102673 равен $$102672={2}^{4} \cdot {3}^{2} \cdot 23 \cdot 31$$. Число, являющееся произведением большого количества небольших чисел, называется гладким. Для дискретного логарифмирования в таком поле существует алгоритм Полига-Хэллмана, который мы сейчас применим.
Если $$x$$ - решение нашей задачи, и $$x_1$$, $$x_2$$, $$x_3$$, $$x_4$$ - остатки от деления $$x$$ на $$16$$, $$9$$, $$23$$ и $$31$$ соответственно, то
$$ \begin{center} \begin{tabular}{ll} ${\left({5}^{{M}_{1}}\right)}^{{x}_{1}}=\left({a}^{{M}_{1}}\right)~(\mod p)$, ${\left({5}^{{M}_{2}}\right)}^{{x}_{2}}=\left({a}^{{M}_{2}}\right)~(\mod p)$, \\ ${\left({5}^{{M}_{3}}\right)}^{{x}_{3}}=\left({a}^{{M}_{3}}\right)~(\mod p)$, ${\left({5}^{{M}_{4}}\right)}^{{x}_{4}}=\left({a}^{{M}_{4}}\right)~(\mod p)$,\\ \end{tabular} \end{center} $$где
$${M}_{1}=\frac{p-1}{16},{M}_{2}=\frac{p-1}{9},{M}_{3}=\frac{p-1}{23},{M}_{4}=\frac{p-1}{31}.$$Наоборот, если мы найдём $$x_1$$, $$x_2$$, $$x_3$$ и $$x_4$$, а решение $$x$$ задачи всегда существует (так как $$5$$ - примитивный корень), то $$x$$ будет совпадать с единственным решением $$x'$$ системы:
$$\left\{\begin{array}{l}x'=x_1 ~(\mod 16), \\ x'=x_2 ~(\mod 9), \\ x'=x_3 ~(\mod 23),\\ x'=x_4 ~(\mod 31). \end{array}\right.$$Итак, для решения задачи, по китайской теореме об остатках нужно найти:
$$ \begin{center} \begin{tabular}{ll} ${M}_{1}=6417,$ ${\widetilde{{M}}}_{1}={M}_{1}^{-1}=1~(\mod 16);$ \\ ${M}_{2}=11408,$ ${\widetilde{{M}}}_{2}={M}_{2}^{-1}=2~(\mod 9);$ \\ ${M}_{3}=4464,$ ${\widetilde{{M}}}_{3}={M}_{3}^{-1}=12~(\mod 23);$ \\ ${M}_{4}=3312,$ ${\widetilde{{M}}}_{4}={M}_{4}^{-1}=6~(\mod 31);$ \end{tabular} \end{center} \end{center} $$ $$x={x}_{1} \cdot {M}_{1} \cdot {\widetilde{{M}}}_{1}+{x}_{2} \cdot {M}_{2} \cdot {\widetilde{{M}}}_{2}+{x}_{3} \cdot {M}_{3} \cdot {\widetilde{{M}}}_{3}+{x}_{4} \cdot {M}_{4} \cdot {\widetilde{{M}}}_{4}=\\6417{x}_{1}+22816{x}_{2}+53568{x}_{3}+19872{x}_{4}.$$Следовательно, нам нужно найти $$x_1$$, $$x_2$$, $$x_3$$, $$x_4$$.
Имеем:
$$ \begin{center} \begin{tabular}{ll} ${97697}^{{x}_{1}}=55814~(\mod p),$ ${170}^{{x}_{2}}=29684~(\mod p),$\\ ${24920}^{{x}_{3}}=56216~(\mod p),$ ${64646}^{{x}_{4}}=18591~(\mod p).$ \end{tabular} \end{center} $$Поскольку порядок группы $${\langle}{5}^{{M}_{3}}{\rangle}$$ равен 23, а группы $${\langle}{5}^{{M}_{4}}{\rangle}$$ - всего 31, то при различных $$x_3$$, $$x_4$$ величины $${24920}^{{x}_{3}}$$ и $${64646}^{{x}_{4}}$$ пробегают, соответственно, по 23 и 31 различным значениям.
Тогда $$x_3$$ и $$x_4$$ можно найти полным перебором, проверив $$x_3=0,1,\ldots,22$$, $$x_3=0,1,\ldots,30$$. В нашем случае $${x}_{3}=14$$, $${x}_{4}=12$$. Числа $${x}_{1}$$ и $${x}_{2}$$ также можно искать полным перебором, но для них можно ещё уменьшить количество попыток. Будем искать
$${x}_{1}={x}_{1,1}+2{x}_{1,2}+4{x}_{1,3}+8{x}_{1,4}, $$где $${x}_{1,i} \in \left\{0,1\right\}.$$
Имеем:
$${\left({97697}^{{x}_{1}}\right)}^{8}={\left({97697}^{8}~(\mod p)\right)}^{{x}_{1.1}}={(-1)}^{{x}_{1,1}}={55814}^{8}=(-1)~(\mod p).$$То есть $$(-1)^{x_{1,1}} = -1$$. Отсюда $${x}_{1,1}=1.$$
Далее,
$${\left({97697}^{{x}_{1}}\right)}^{4}={97697}^{4+8{x}_{1,2}}=15467 \cdot {(-1)}^{{x}_{1,2}}={55814}^{4}=87206~(\mod p).$$Проверим оба варианта $$x_{1,2}=0,1$$:
$$15467 \cdot {(-1)}^{0} \neq 87206~(\mod p),$$ $$15467 \cdot {(-1)}^{1} = 87206~(\mod p).$$Отсюда $${x}_{1,2}=1$$.
Далее,
$${\left({97697}^{{x}_{1}}\right)}^{2}={97697}^{2+4+8{x}_{1,3}}=101570 \cdot {\left(-1\right)}^{{x}_{1,3}}={55814}^{2}=1103~(\mod p).$$Опять, из двух вариантов выбираем верный: $${x}_{1,3}=1$$.
Наконец,
$${97697}^{1+2+4+8{x}_{1,4}}=46859 \cdot {\left(-1\right)}^{{x}_{1,4}}=55814~(\mod p),$$откуда $${x}_{1,4}=1.$$ Проверяем:
$${97697}^{15}=55814~(\mod p)\Rightarrow {x}_{1}=15.$$Аналогично находим $${x}_{2}={x}_{2,1}+3{x}_{2,2}=5$$.
По китайской теореме об остатках находим $$x=69359$$.
Для небольших $$p$$ бывает удобно вычислять все степени примитивного корня и строить на основе этих вычислений две таблицы, называемые таблицами индексов. Таблицы индексов используются для быстрого решения некоторых задач по модулю простого числа $$p$$.
Приведем эти таблицы для примитивного корня 2 по модулю 37:
|
|
Например, чтобы определить индекс по числу 13, нужно в первой таблице перейти к столбцу "1" и строке "3". Итак, $${ind}_{2}13=11$$. Наоборот, для нахождения числа по его индексу 11 нужно во второй таблице перейти в столбец "1" строку "1". Имеем: $${2}^{11}=13\mod37$$.
Пример 3.8 Решим с помощью таблицы индексов сравнение:
$$8x=-11\mod37.$$Будем далее использовать примитивный корень $$2$$ и построенные для него выше таблицы. Правую часть сравнения заменяем положительным вычетом:
$$8x=26\mod37.$$"Индексируем" левую и правую части сравнения:
$${ind}\ 8+{ind}\ x={ind}\ 26~(\mod 36).$$Находим в первой таблице для простого числа 37 значение $$ind\ 8$$ и $$ind\ 26$$ и подставляем в сравнение. Получим:
$$3+ind\ x=12~(\mod 36),$$Откуда
$$ind\ x=9~(\mod 36).$$По второй таблице находим число, соответствующее индексу 9. Получим: $$x=31~(\mod 37).$$
Пример 3.9 С помощью индексов решить сравнение:
$$13{x}^{4}=22~(\mod 37).$$Индексируем сравнение:
$$ind\ 13+4\cdot ind\ x=ind\ 22.$$По первой таблице индексов находим: $$ind\ 13=11$$, $$ind\ 22=31$$. Отсюда: $$11+4\cdot ind\ x=31~(\mod 36)$$, или $$4 ind\ x=20~(\mod 36)$$. Последнему сравнению удовлетворяют $$ind\ x=5,14,23,32$$. Для каждого из них по второй таблице индексов найдем $$x=32,30,5,7$$.
Для полиномов справедлив аналог теоремы о делении с остатком. Для любых полиномов $$f(x)$$ и $$g(x)$$ существуют полиномы $$q(x)$$, $$r(x)$$, такие, что
$$f\left(x\right)=q\left(x\right)g\left(x\right)+r\left(x\right),{deg}\left(r\left(x\right)\right)<{deg}\left(g\left(x\right)\right).$$Если $$r(x) = 0$$, то $$g(x)$$ называется делителем многочлена $$f(x)$$.
Определение 3.23 Наибольшим общим делителем многочленов $$f(x)$$ и $$g(x)$$ называется их общий делитель, который делится на любой другой их общий делитель.
Для полиномов наибольший общий делитель определён с точностью до умножения на константу. Будем всегда выбирать полином с единичным старшим членом. Полином, не имеющий нетривиальных делителей, называется неприводимым.
Определение 3.24 Более точно, полином $$f(x)$$ степени $$d$$ над полем $$F$$ называется неприводимым, если не существует двух таких полиномов $$g(x)$$, $$h(x)$$ степеней меньших $$d$$, что $$f(x) = g(x)h(x)$$.
В качестве примера рассмотрим алгоритм формирования контрольной суммы CRC (Cyclic Redundancy Code). Он используется для того, чтобы при передаче сообщения через подверженные помехам каналы выявлять ошибки передачи данных. Контрольная сумма передаётся вместе с данными, а затем принимающая сторона также вычисляет контрольную сумму и сравнивает её с принятой.
Для формирования контрольной суммы биты данных представляются как коэффициенты полинома над полем $$\mathbb{Z}_2$$. Затем вычисляется остаток от деления этого полинома на некоторый фиксированный полином, называемый порождающим. Остаток от деления - снова полином, коэффициенты которого вновь рассматриваются как биты некоторого числа, являющегося контрольной суммой.
Пример 3.10 Используя порождающий полином $$f\left(x\right)={x}^{5}+{x}^{2}+1$$, построить контрольную сумму сообщения: $$10001\ 01101\ 10001\ 10110\ 00010$$.
Решение. Представим сообщение в виде:
$$ g(x)=\left(\left(\left(\left({x}^{4}+1 \right) \cdot {x}^{5}+ \left({x}^{3}+{x}^{2}+1\right)\right) \cdot {x}^{5}+\left({x}^{4}+1 \right)\right) \cdot {x}^{5}+\right.\\ +\left.\left({x}^{4}+{x}^{2}+x\right)\right){x}^{5}+x= \\ =\left(\left(\left(g_{0}(x){x}^{5}+{g}_{1}(x)\right){x}^{5}+{g}_{2}(x) \right){x}^{5}+{g}_{3}(x)\right){x}^{5}+{g}_{4}(x). $$Обозначим $${c}_{i}\left(x\right)=\left(\left({\dots}\left({g}_{0}\left(x\right){x}^{5}+{g}_{1}\left(x\right)\right){x}^{5}{\dots}\right)+{g}_{i}\left(x\right)\right)~(\mod f\left(x\right)).$$
Очевидно, $${c}_{i+1}\left(x\right)={c}_{i}\left(x\right){x}^{5}+{g}_{i+1}\left(x\right)~(\mod f\left(x\right)).$$
По модулю $$f(x)$$ имеем:
$${x}^{5}=f\left(x\right)+{x}^{2}+1={x}^{2}+1;$$ $${c}_{0}\left(x\right)={g}_{0}\left(x\right)={x}^{4}+1;$$ $$ {c}_{1}\left(x\right)={c}_{o}\left(x\right){x}^{5}+{g}_{1}\left(x\right)= \left({x}^{4}+1\right)\left({x}^{2}+1\right)+{x}^{3}+{x}^{2}+1=\\ ={x}^{6}+{x}^{4}+{x}^{3}=xf\left(x\right)+{x}^{3}+x+{x}^{4}+{x}^{3}={x}^{4}+x; $$ $$ {c}_{2}\left(x\right)={c}_{1}\left(x\right){x}^{5}+{g}_{2}\left(x\right)=\left({x}^{4}+x\right)\left({x}^{2}+1\right)+{x}^{4}+1=\\ ={x}^{6}+{x}^{3}+x+1={xf}\left(x\right)+1=1; $$ $${c}_{3}\left(x\right)={c}_{2}\left(x\right){x}^{5}+{g}_{3}\left(x\right)={x}^{2}+1+{x}^{4}+{x}^{2}+x={x}^{4}+x+1;$$ $$ {c}_{4}\left(x\right)={c}_{3}\left(x\right){x}^{5}+{g}_{4}\left(x\right)=\left({x}^{4}+x+1\right)\left({x}^{2}+1\right)+x=\\ ={x}^{6}+{x}^{4}+{x}^{3}+x+{x}^{2}+1+x=x f(x)+{x}^{4}+{x}^{2}+x+1=\\ ={x}^{4}+{x}^{2}+x+1. $$Поэтому контрольная сумма равна (10111).
Пример 3.11 По каналу сначала была передана контрольная сумма сообщения $$01101$$, а затем начало передаваться сообщение. Злоумышленник смог испортить сообщение, и его контрольная сумма стала $$11011$$. Какие биты должен злоумышленник присоединить к хвосту сообщения, чтобы контрольная сумма совпала с переданной пользователю?
Решение. Имеем: $${c}_{n}\left(x\right)={x}^{4}+{x}^{3}+x+1$$, при этом требуется, чтобы $${c}_{n+1}\left(x\right)={x}^{3}+{x}^{2}+1$$. В то же время:
$${c}_{n+1}\left(x\right)={c}_{n}\left(x\right) \cdot {x}^{5}+{g}_{n+1}\left(x\right).$$Злоумышленник всего-навсего должен нужным образом подобрать $${g}_{n+1}(x)$$:
$${g}_{n+1}\left(x\right)={c}_{n+1}\left(x\right)-{x}^{5}{c}_{n}\left(x\right)={x}^{3}+{x}^{2}+1+{x}^{5}\left({x}^{4}+{x}^{3}+x+1\right)={x}^{4}+{x}^{2}+1.$$Итак, злоумышленник должен отправить 5 бит: 10101, и контрольная сумма испорченного сообщения совпадёт с контрольной суммой, которую ожидает пользователь.
Если полином $$f(x)$$ неприводим, то для любого полинома $$q(x)$$ степени меньше $$d$$ имеем $$\GCD(f(x), q(x)) = 1$$. Выполнив расширенный алгоритм Евклида, мы можем найти такие многочлены $$u(x)$$, $$v(x)$$, что $$f(x) u(x) + q(x) v(x) = 1$$. Очевидно, тогда $$q(x)v(x) - 1$$ лежит в идеале $$f(x) F[x]$$ всех многочленов, кратных $$f(x)$$, а $$q(x)v(x)$$ - в смежном классе, содержащем единицу. Другими словами, $$v(x)q(x) = 1 ~(\mod f(x))$$, или $$v(x) = q(x)^{- 1} ~(\mod f(x))$$.
Пример 3.12 Найти в кольце $$\mathbb{Z}_2[x]$$ полином, обратный к полиному $$g\left(x\right)={x}^{5}$$ по модулю $$f(x)=x^{7}+{x}^{3}+1$$.
Решение. Выполним расширенный алгоритм Евклида. Положим $${r}_{0}\left(x\right)=f\left(x\right),{r}_{1}\left(x\right)=g\left(x\right).$$
Следовательно, $${x}^{5}+{x}^{2}+x=g{\left(x\right)}^{-1}~(\mod f\left(x\right))$$.
Более подходящим для программной реализации будет следующее описание расширенного алгоритма Евклида:
Вход: полиномы $$f(x)$$, $$g(x)$$, степень $$f(x)$$ не меньше степени $$g(x)$$.
Выход: полиномы $$\GCD(f(x),g(x))$$, $$u(x)$$ и $$v(x)$$ такие, что $$\GCD(f(x),g(x)) = u(x) f(x) + v(x) g(x)$$.
Когда полином $$f(x)$$ над полем $$F$$ степени $$d$$ неприводим, множество полиномов над $$F$$ степени $$\leq d$$ относительно сложения и умножения по модулю $$f(x)$$ образуют поле. Известно, что над полем $$F$$ простого порядка существуют неприводимые многочлены любой степени. Поэтому описанным способом можно построить поля любого порядка $$p^d$$. Построение неприводимых полиномов является важной задачей.
Поскольку все поля одинакового порядка изоморфны, для поля данного порядка $$q$$ вводится единое обозначение: $$GF(q)$$.
Пример 3.13 Построить неприводимый полином степени $$5$$ над $$\mathbb{Z}_2$$.
Решение. Пока нам неизвестен более быстрый метод, будем использовать метод пробных делений. Если полином степени 5 приводим, то один из его сомножителей является неприводимым и имеет степень меньше 3. Полиномы степени меньше 3: $$x$$, $$x + 1$$, $$x^2$$, $$x^2+x$$, $$x^2+1$$, $$x^2+x+1$$. Из них неприводимыми являются $$x$$, $$x + 1$$, $$x^2 + x + 1$$.
Выберем случайно полином. Пусть им оказался $$x^5+x^4+1$$. Он не делится на $$x$$ и на $$x + 1$$, так как 0 и 1 не являются его корнями. Однако $$x^5+x^4+1 = (x^2+x+1)(x^3+x+1)$$.
Пусть случайно выбран полином $$x^5+x^2+1$$. Снова, 0 и 1 не являются его корнями, и $$x^5+x^2+1=(x^2+x+1)(x^3+x^2)+1$$. Следовательно, этот полином неприводим.
Разумеется, существуют более простые способы тестирования полиномов над конечным полем на приводимость, например, алгоритм Берлекемпа [1].
Вход: полином $$f(x)$$ степени $$d$$ над конечным полем $$F$$, не имеющий кратных корней (что проверяется вычислением его наибольшего общего делителя с производной $$f'(x)$$.
Выход: ответ на вопрос - приводим ли многочлен.
Пример 3.14 Протестировать на приводимость полином $${x}^{8}+{x}^{4}+{x}^{3}+x+1$$.
Решение. Вычислим, согласно алгоритму, остатки от деления
| $$k$$ | $${r}_{k}\left(x\right)={x}^{2k}~(\mod f\left(x\right)+{x}^{k})$$ |
| 1 | $${x}^{2}+x $$ |
| 2 | $${x}^{4}+{x}^{2}$$ |
| 3 | $${x}^{6}+{x}^{3}$$ |
| 4 | $${x}^{8}+{x}^{4}={x}^{3}+x+1 $$ |
| 5 | $${x}^{10}+{x}^{5}={x}^{6}+{x}^{3}+{x}^{2} $$ |
| 6 | $${x}^{12}+{x}^{6}={x}^{7}+{x}^{6}+x^{5}+{x}^{3}+x+1 $$ |
| 7 | $${x}^{14}+{x}^{7}={x}^{3}+x$$ |
Построим и приведём к трапецеидальному виду матрицу коэффициентов этих полиномов:
$$ A=\left(\begin{matrix} 1 1 \\ 1 1 1 1 1 1 \\ 1 1 1 \\ 1 1 1\\ 1 1 \\ 1 1 \\ 1 1 \\ \end{matrix}\right). $$Переместим вторую строку на первое место, третью строку - на второе, шестую - на третье, далее пойдут по порядку первая, четвертая, сумма пятой и третьей строк, седьмая строка. Имеем:
$$ A\sim \left(\begin{matrix} 1 1 1 1 1 1\\ 1 1 1 \\ 1 1 \\ 1 1 \\ 1 1 1\\ 1 \\ 1 1 \\ \end{matrix}\right)\sim \left( \begin{matrix} 1 1 1 1 1 1\\ 1 1 1 \\ 1 1 \\ 1 1 \\ 1 \\ 1 \\ 1\\ \end{matrix}\right). $$Итак, ранг матрицы равен $$7 = d - 1$$, следовательно, полином неприводим.
Мы предполагаем, что читатель владеет понятиями группа, кольцо, поле. Поэтому очень кратко изложим элементы теории с нужными нам для дальнейшего акцентами.
В основе всех понятий, изучаемых в различных разделах алгебры, лежит понятие алгебраической операции.
Пусть $$G$$ - множество (элементами $$G$$ могут быть числа или функции или объекты геометрической природы и т.д.).
Определение 3.1 Говорят, что на $$G$$ задана бинарная алгебраическая операция, если любой упорядоченной паре $$(a,b)$$ элементов $$a,b\in G$$ ставится в соответствие однозначно определённый элемент $$f(a,b)$$ этого же множества $$G$$.
Определение 3.2 Группоидом называется всякое непустое множество, в котором задана алгебраическая операция.
Иногда вместо $$f(a,b)$$ пишут $$afb$$, а ещё чаще бинарную операцию на $$G$$ обозначают каким-нибудь специальным символом: $$\ast$$, $$\circ$$, $$\cdot$$, $$+$$, так будем поступать и мы, называя $$a\cdot b$$ (или просто $$ab$$) произведением элементов $$a$$ и $$b$$. Таким образом, равенство
$$ab=c$$будет в дальнейшем иметь следующий смысл: упорядоченной паре $$a,b$$ из $$G$$ ставится в соответствие элемент $$c$$. Иногда (там, где это будет удобнее) вместо "произведение" будем заменять на "сумму", см. таблицу 3.1.
Замечание 1. Можно рассматривать бинарную операцию в "широком смысле": некоторым упорядоченным парам элементов из $$G$$ ставится в соответствие один или несколько элементов из $$G$$. Такой, более общий подход "имеет право на существование", он приводит к интересным результатам, однако мы, исходя из наших целей, будем придерживаться понятия алгебраической операции, приведённого выше.
Замечание 2. Наряду с бинарными алгебраическими операциями имеет смысл рассматривать и более общие $$n$$-арные операции (унарные при $$n=1$$, тернарные при $$n=3$$, и т.д.), а также и их комбинации. Нас же будут интересовать, за редкими исключениями, именно бинарные операции.
На множестве $$G$$ можно задать много различных операций. Если хотят выделить одну из них, то пишут $$(G,\ast)$$.
Пример 3.1
Для задания группоида нужно задать множество $$G$$ и то правило, по которому можно найти значение операции $$\ast$$ для любых двух элементов из $$G$$. В том случае, когда множество $$G$$ конечно, всю эту информацию можно записать таблицей, в которой входной строкой и входным столбцом является список элементов множества $$G$$, а на пересечении строки с входом $$a$$ и столбца с входом $$b$$ располагается значение операции $$a\ast b$$.
Такая таблица называется таблицей Кэли для группоида $$(G; \ast)$$ в честь английского математика Артура Кэли (1821-1895). Если $$G=\{a_1,\ldots,a_n\}$$, то таблица Кэли для группоида $$(G,\ast)$$ имеет следующий вид:
| $$\ast$$ | $$a_1$$ | $$\cdots$$ | $$a_j$$ | $$\cdots$$ | $$a_n$$$ |
| $$a_1$$ | $$a_1\ast a_1$$ | $$\cdots$$ | $$a_1\ast a_j$$ | $$\cdots$$ | $$a_1\ast a_n$$ |
| $$a_2$$ | $$a_2\ast a_1$$ | $$\cdots$$ | $$a_2\ast a_j$$ | $$\cdots$$ | $$a_2\ast a_n$$ |
| $$\vdots$$ | $$\vdots$$ | $$\vdots$$ | $$\vdots$$ | ||
| $$a_n$$ | $$a_n\ast a_1$$ | $$\cdots$$ | $$a_n\ast a_j$$ | $$\cdots$$ | $$a_n\ast a_n$$ |
Исходя из такого задания группоида, легко подсчитать, сколько различных операций можно определить на множестве $$G$$ порядка $$n$$. В каждую из $$n^2$$ клеток таблицы Кэли можно записать любой из $$n$$ элементов множества $$G$$. Отсюда видно, что таблицу Кэли можно составить в $$n^{n^2}$$ вариантах, то есть на множестве $$G$$ из $$n$$ элементов существуют $$n^{n^2}$$ различных группоидов.
| Мультипликативная терминология | Аддитивная терминология |
|---|---|
| Умножение $$a\cdot b = ab$$ | Сложение $$a+b$$ |
| $$a$$, $$b$$ - множители | $$a$$, $$b$$ - слагаемые |
| Нейтральный элемент - единица ($$1$$) | Нейтральный элемент - ноль ($$0$$) |
| Обратный элемент $$a^{-1}$$ | Противоположный элемент $$-a$$ |
| $$\underbrace{a\cdot a\cdots a}_{n\ \text{раз}} = a^n$$ - степень | $$\underbrace{a+ a+\ldots +a}_{n\ \text{раз}} = n\cdot a$$ - кратное |
Определение 3.3 Элемент $$e_r$$ (или $$e_l$$) группоида $$(G, \ast)$$ называется правым (соответственно, левым) нейтральным, если $$a\cdot e_r = a$$ для любого элемента $$a\in G$$ (соответственно, $$e_l*a=a$$). Элемент $$e$$ группоида $$(G, \ast)$$ называется нейтральным, если он является одновременно левым и правым нейтральным.
Ясно, что если в группоиде существует нейтральный элемент, то он единственный.
В зависимости от терминологии (см. таблицу 3.1), нейтральный элемент могут называть единицей или нулем.
Определение 3.4 Пусть $$G$$ - группоид, $$e$$ - его правый (или левый) нейтральный элемент, и $$a\in G$$, то правым (соответственно, левым) обратным элементом для элемента $$a$$ относительно правого (или левого) нейтрального элемента $$e$$ называется такой $$b\in G$$, что $$a\ast b=e$$ (соответствено, $$b\ast a=e$$).
В общем случае в группоиде с нейтральным элементом элемент может не иметь обратных, может иметь один или несколько обратных. Более определённо вопрос о числе обратных элементов решается в группоидах с ассоциативной операцией, см. ниже.
Конструировать разные бинарные операции на множестве можно неограниченно, но задача изучения произвольных алгебраических структур слишком обща. Поэтому рассматривают структуры при некоторых естественных ограничениях.
Чаще всего нас будет интересовать выполнимость ассоциативного и коммутативного законов для операции.
Определение 3.5 Бинарная операция $$\ast$$ на множестве $$G$$ называется ассоциативной, если $$a\ast(b\ast c)=(a\ast b)\ast c$$ для всех $$a, b, c\in G$$.
Определение 3.6 Бинарная операция $$\ast$$ на множестве $$G$$ называется коммутативной, если $$a\ast b = b\ast a$$ для всех $$a, b\in G$$.
Свойства ассоциативности и коммутативности независимы. Действительно, например операция на $$m\ast n = -m-n$$ на $$\mathbb{Z}$$ является коммутативной, но не ассоциативной, а операция умножения квадратных $$n \times n$$-матриц - ассоциативна, но не коммутативна.
Пример 3.2
Определение 3.7 Множество $$G$$ с определённой на нём ассоциативной бинарной операцией $$\times$$ называется полугруппой. Полугруппа, в которой есть нейтральный элемент, называется моноидом.
Примеры полугрупп.
$$(\mathbb{N}, \cdot)$$ - моноид.
$$(\mathbb{Z}, +)$$ - моноид.
$$(\mathbb{N}, {\nabla})$$, где $$a{\nabla}b=НОК(a, b)$$.
$$(\mathbb{R}, {\vee})$$, где $$a{\vee}b=\max\{a, b\}$$.
Пусть $$G$$ - произвольное (непустое) множество. Зададимся вопросом: можно ли превратить $$G$$ в полугруппу? Другими словами, можно ли задать на $$G$$ какую-нибудь ассоциативную операцию? Ответ утвердительный. Более того, если $$G$$ неодноэлементно, то это можно сделать многими способами, а при бесконечном $$G$$ - бесконечным числом способов. Укажем несколько таких способов.
Пусть $$A$$ - произвольное (непустое) множество. Будем называть $$A$$ алфавитом, а элементы $$A$$ - буквами. Через $$F(A)$$ обозначим множество всех конечных последовательностей букв из $$A$$. Зададим на $$F(A)$$ операцию умножения, полагая $$(a_1,\dots,a_m)\times (b_1, \dots, b_n)=(a_1,\dots,a_m,b_1,\dots,b_n)$$. Легко видеть, что эта операция (называемая иногда конкатенацией, то есть сцеплением) ассоциативна (упражнение: проверить), так что $$F(A)$$ становится полугруппой, которая называется свободной полугруппой над алфавитом $$A$$. Другое употребительное обозначение для нее : $$A^+$$. Отождествляя последовательность из одной буквы с самой этой буквой и опуская в записи знак для конкатенации, элементы свободной полугруппы записывают в виде $$a_1a_2\dots a_m$$ и называют словами. По определению, слова $$a_1a_2\dots a_m$$ и $$c_1c_2\dots c_k$$ равны, если $$m = k$$ и $$a_i=c_i$$ при $$i = 1,{\ldots}, m$$.
Свободные полугруппы играют важную роль как в общей теории полугрупп, так и в приложениях. Их прикладная роль объясняется, в частности, тем, что во многих процессах передачи информации передаваемые сообщения представляют собой цепочки символов ("реальных" букв или слов, других кодовых знаков, электрических сигналов и т.д.) и соединение двух таких цепочек есть не что иное, как конкатенация слов в подходящей свободной полугруппе. Свободные полугруппы (главным образом, над конечными алфавитами) являются исходным объектом в теории формальных языков и теории кодов, существенна их роль в теории автоматов. При этом обычно к элементам полугруппы $$F(A)$$ добавляют так называемое пустое слово, не содержащее букв и играющее роль единицы при умножении, получается полугруппа с единицей, обозначаемая $$ A^\ast$$ и называемая свободным моноидом над алфавитом $$A$$.
Формальным языком называется произвольное подмножество некоторого свободного моноида.
Определение 3.8 Полугруппа с единицей, в которой для каждого элемента существует обратный, называется группой.
Определение 3.9 Если операция в группе $$G$$ обладает коммутативностью, т.е.
$$a\times b=b\times a{\forall}a,b \in G,$$то группа $$G$$ называется коммутативной.
Определение 3.10 Мощность множества $$G$$, на котором задана групповая операция, называется порядком группы $$G$$.
Если множество конечно, то группа $$G$$ называется конечной.
Определение 3.11 Подмножество множества $$G$$, являющееся одновременно группой относительно той же самой операции, называется подгруппой группы $$G$$.
Определение 3.11 Подгруппа $$H$$ группы $$G$$ называется тривиальной, если либо $$H=G$$, либо $$H$$ состоит из одного нейтрального элемента.
Справедлива
Теорема 3.1 (Теорема Лагранжа) Порядок $$n$$ конечной группы $$G$$ делится на порядок $$m$$ любой её подгруппы $$H$$.
Определение 3.12 Число $$|G|/|H|$$ называется индексом подгруппы $$H$$ в группе $$G$$ и обозначается $$|G:H|$$.
Определение 3.13 Полугруппы $$G$$ и $$H$$ называются изоморфными, если существует взаимно однозначное отображение $$\varphi :G\rightarrow H$$, сохраняющее операцию, то есть такое, что $$\varphi \left(a\times b\right)=\varphi \left(a\right)\times \varphi \left(b\right)$$.
Определение 3.14 Подгруппа группы $$G$$ называется максимальной, если она не содержится в других собственных (не совпадающих с $$G$$) подгруппах группы $$G$$.
Определение 3.15 Минимальная подгруппа группы $$G$$, содержащая элементы $${a}_{1},{a}_{2},{\dots},{a}_{k}$$, называется подгруппой, порождённой этими элементами, и обозначается $${\langle}{a}_{1},{\dots},{a}_{k}{\rangle}$$.
Определение 3.16 Группа $${\langle}a{\rangle}$$, порождённая одним элементом, называется циклической, и состоит из элементов $$e={a}^{0},{a},{a}^{2},{a}^{3},{\dots}$$.
Существуют две возможности: либо все степени элемента $$a$$ различны, тогда список элементов группы $${\langle}a{\rangle}$$ будет продолжаться бесконечно, либо на каком-то шаге окажется: $${a}^{n}={a}^{0}$$.
Определение 3.17 Минимальное натуральне число $$n$$ такое, что $$a^n = 1$$, называется порядком элемента $$a$$ (пишут $$|a| = n$$). Если такого $$n$$ не существует, пишут $$|a|=\infty$$.
Одновременно такое $$n$$ является порядком подгруппы $${\langle}a{\rangle}$$.
Справедливо
Следствие 3.1 (из теоремы Лагранжа) Порядок конечной группы $$G$$ делится на порядок любого её элемента.
Отметим несколько свойств циклической группы, которые пригодятся нам в дальнейшем:
Пример 3.3 Множество $$\mathbb{Z}_{11}^{*}$$ чисел от $$1$$ до $$10$$ c умножением по модулю $$11$$ образует группу. Отметим, что в этой группе нейтральным элементом является $$1$$, элемент $$10$$ имеет порядок $$2$$, поскольку $$10 \cdot 10=100 \equiv 1\mod11$$, элементы $$4, 5, 9, 3$$ имеют порядок $$5$$, а остальные элементы имеют порядок, не делящий ни $$2$$, ни $$5$$, но делящий $$10$$. То есть элементы $$2, 6, 7, 8$$ имеют порядок $$10$$, то есть $$\mathbb{Z}_{11}^{*}=\left\langle 2\right\rangle =\left\langle 6\right\rangle =\left\langle 7\right\rangle ={\langle}8{\rangle}$$.
Пример 3.4 Пусть элемент $$a$$ группы $$G$$ имеет порядок $$60$$. Найти число $${N}_{20}$$ элементов порядка $$20$$ в группе $${\langle}a{\rangle}$$? Сколько элементов являются порождающими в $${\langle}a{\rangle}$$?
Решение. По свойству 2, элементы порядка 20 лежат в подгруппе $$\left\langle {a}^{3}\right\rangle$$ и, по свойствам 3,5, не лежат в её максимальных подгруппах: $${\langle}{a}^{6}{\rangle}$$ и $${\langle}{a}^{15}{\rangle}$$. Отсюда,
$${N}_{20}=\left|\left\langle {a}^{3}\right\rangle \right|-\left|\left\langle {a}^{6}\right\rangle {\cup}\left\langle {a}^{15}\right\rangle \right|.$$Порядок элементов из $$\left\langle {a}^{6}\right\rangle {\cap}{\langle}{a}^{15}{\rangle}$$ делит и 10 и 4, следовательно, равен 1 или 2, т.е. $$\left\langle {a}^{6}\right\rangle {\cap}\left\langle {a}^{15}\right\rangle =\left\langle {a}^{30}\right\rangle$$, $$\left|\left\langle {a}^{30}\right\rangle \right|=2.$$ Отсюда,
$${N}_{20}=20-10-4+2=8.$$Число $$N_{60}$$ порождающих элементов в $${\langle}a{\rangle}$$, то есть элементов порядка 60, можно найти по формуле:
$${N}_{60}=\varphi \left(60\right)=\varphi \left(4\right)\varphi \left(3\right)\varphi \left(5\right)=2 \cdot 2 \cdot 4=16,$$где $$\varphi$$ - функция Эйлера.
Определение 3.18 Множество $$F$$ с двумя алгебраическими операциями $$+$$, $$\times$$ называется ассоциативным кольцом, если в нём выполняются свойства:
Определение 3.19 Кольца $$K$$ и $$F$$ называются изоморфными, если существует отображение $$\varphi :K\rightarrow F$$, являющееся изоморфизмом аддитивных и мультипликативных групп этих колец.
Определение 3.20 Полем называется кольцо $$F$$, в котором $${F}^{*}$$ является коммутативной группой.
Определение 3.21 Характеристикой поля называется наименьшее такое натуральное число $$p$$, что $$p \cdot 1=1+1+1+{\dots}+1=0$$, или 0, если такого $$p$$ не существует. Характеристика поля может быть только простым числом или нулем.
Определение 3.22 Левым (правым) идеалом кольца называется любое его подкольцо, выдерживающее умножение слева (соответственно, справа) на любой элемент кольца. Подкольцо, являющееся левым и правым идеалом, называется двусторонним идеалом, или просто идеалом.
Подкольцо $$I$$ разбивает кольцо $$K$$ на классы эквивалентности: $$a \equiv b\Leftrightarrow a-b \in I$$. Класс, содержащий элемент $$a$$, можно записать в виде:
$$a+I=\left\{a+x\right|x \in I\}.$$Если подкольцо является идеалом, то на множестве таких классов можно ввести операции сложения и умножения, относительно которых множество классов образует кольцо, называемое фактор-кольцом:
$$(a+I)+(b+I) = (a+b)+I,\quad (a+I)\cdot (b+I)=(a\cdot b)+I.$$Из определения идеала следует, что результат операций не зависит от выбора представителей $$a$$, $$b$$, то есть операции заданы корректно.
Наиболее важными для нас будут следующие кольца и поля:
В криптографии нас будут интересовать больше всего конечные поля, то есть поля с конечным множеством $$F$$. Перечислим наиболее важные для нас свойства:
Рассмотрим несколько связанных с кольцами вычетов задач, часто возникающих в криптографии.
Пример 3.5 Найти мультипликативный порядок элемента $$16$$ по модулю $$101$$, то есть порядок элемента $$16$$ мультипликативной группы $$\mathbb{Z}_{101}$$.
Решение. Поскольку число 101 простое, порядок мультипликативной группы поля $$\mathbb{Z}_{101}$$ равен 100. По следствию из теоремы Лагранжа, мультипликативный порядок любого числа по модулю 101 является делителем 100, то есть одним из чисел: 1, 2, 4, 5, 10, 20, 25, 50, 100. Проверим каждое из чисел:
| $$d$$ | 1 | 2 | 4 | 5 | 10 | 20 | 25 | 50 | 100 |
|---|---|---|---|---|---|---|---|---|---|
| $${16}^{d}~(\mod 101)$$ | 16 | 54 | 88 | 95 | 36 | 84 | 1 | - | - |
После того, как обнаружили, что $$16^{25}=1~(\mod 101)$$, возводить в $$50$$-ю и $$100$$-ю степень излишне - видно, что наименьшая степень, в которой 16 даст единицу по модулю 101, это 25.
Пример 3.6 Найти случайный примитивный корень по модулю $$883$$.
Решение. Порядок мультипликативной группы поля вычетов по модулю 883 равен $$882=2 \cdot 9 \cdot 49$$. Будем выбирать случайное число $$x$$ и возводить его в степени $$882/2$$, $$882/3$$, $$882/7$$. Если в какой-то степени $$x$$ даст единицу, то его порядок меньше 882, и, следовательно, он не является примитивным корнем по модулю 883. Наоборот, порядок порождающего элемента является делителем числа 882, и если он не является делителем ни одного из чисел $$882/2$$, $$882/3$$, $$882/7$$, то равен 882. В первой колонке таблицы приводятся случайно выбранные элементы $$x$$, а в следующих колонках - результаты возведения в степень.
| $$x$$ | $${x}^{\frac{882}{2}}\mod883$$ | $${x}^{\frac{882}{3}}\mod883$$ | $${x}^{\frac{882}{7}}\mod883$$ |
|---|---|---|---|
| 94 | 1 | 545 | 626 |
| 537 | 882 | 1 | 71 |
| 787 | 882 | 1 | 199 |
| 326 | 882 | 337 | 199 |
Итак, 326 является примитивным корнем по модулю 883.
Пусть $$G$$ - группа, $$a$$ - её элемент, $$b={a}^{k} \in {\langle}a{\rangle}$$. Число $$k$$ называется дискретным логарифмом элемента $$b$$ по основанию $$a$$ (пишут $$k={\log }_{a}b$$). В случае, когда $$a$$ - примитивный корень по модулю $$n$$, дискретный логарифм $$k$$ ещё называют индексом числа $$b$$ по модулю $$n$$ при основании $$a$$. Пишут: $$k=ind_{a}b$$. Когда примитивный корень $$a$$ фиксирован, можно также писать: $$k=ind\ b$$.
Дискретное логарифмирование в произвольной группе является трудноразрешимой задачей. Приведём один из примеров, когда оно всё-таки легко осуществимо.
Пример 3.7 Вычислить дискретный логарифм числа $$a=5434$$ по основанию $$5$$ по модулю $$p = 102673$$.
Решение. Порядок мультипликативной группы поля вычетов по модулю 102673 равен $$102672={2}^{4} \cdot {3}^{2} \cdot 23 \cdot 31$$. Число, являющееся произведением большого количества небольших чисел, называется гладким. Для дискретного логарифмирования в таком поле существует алгоритм Полига-Хэллмана, который мы сейчас применим.
Если $$x$$ - решение нашей задачи, и $$x_1$$, $$x_2$$, $$x_3$$, $$x_4$$ - остатки от деления $$x$$ на $$16$$, $$9$$, $$23$$ и $$31$$ соответственно, то
$$ \begin{center} \begin{tabular}{ll} ${\left({5}^{{M}_{1}}\right)}^{{x}_{1}}=\left({a}^{{M}_{1}}\right)~(\mod p)$, ${\left({5}^{{M}_{2}}\right)}^{{x}_{2}}=\left({a}^{{M}_{2}}\right)~(\mod p)$, \\ ${\left({5}^{{M}_{3}}\right)}^{{x}_{3}}=\left({a}^{{M}_{3}}\right)~(\mod p)$, ${\left({5}^{{M}_{4}}\right)}^{{x}_{4}}=\left({a}^{{M}_{4}}\right)~(\mod p)$,\\ \end{tabular} \end{center} $$где
$${M}_{1}=\frac{p-1}{16},{M}_{2}=\frac{p-1}{9},{M}_{3}=\frac{p-1}{23},{M}_{4}=\frac{p-1}{31}.$$Наоборот, если мы найдём $$x_1$$, $$x_2$$, $$x_3$$ и $$x_4$$, а решение $$x$$ задачи всегда существует (так как $$5$$ - примитивный корень), то $$x$$ будет совпадать с единственным решением $$x'$$ системы:
$$\left\{\begin{array}{l}x'=x_1 ~(\mod 16), \\ x'=x_2 ~(\mod 9), \\ x'=x_3 ~(\mod 23),\\ x'=x_4 ~(\mod 31). \end{array}\right.$$Итак, для решения задачи, по китайской теореме об остатках нужно найти:
$$ \begin{center} \begin{tabular}{ll} ${M}_{1}=6417,$ ${\widetilde{{M}}}_{1}={M}_{1}^{-1}=1~(\mod 16);$ \\ ${M}_{2}=11408,$ ${\widetilde{{M}}}_{2}={M}_{2}^{-1}=2~(\mod 9);$ \\ ${M}_{3}=4464,$ ${\widetilde{{M}}}_{3}={M}_{3}^{-1}=12~(\mod 23);$ \\ ${M}_{4}=3312,$ ${\widetilde{{M}}}_{4}={M}_{4}^{-1}=6~(\mod 31);$ \end{tabular} \end{center} \end{center} $$ $$x={x}_{1} \cdot {M}_{1} \cdot {\widetilde{{M}}}_{1}+{x}_{2} \cdot {M}_{2} \cdot {\widetilde{{M}}}_{2}+{x}_{3} \cdot {M}_{3} \cdot {\widetilde{{M}}}_{3}+{x}_{4} \cdot {M}_{4} \cdot {\widetilde{{M}}}_{4}=\\6417{x}_{1}+22816{x}_{2}+53568{x}_{3}+19872{x}_{4}.$$Следовательно, нам нужно найти $$x_1$$, $$x_2$$, $$x_3$$, $$x_4$$.
Имеем:
$$ \begin{center} \begin{tabular}{ll} ${97697}^{{x}_{1}}=55814~(\mod p),$ ${170}^{{x}_{2}}=29684~(\mod p),$\\ ${24920}^{{x}_{3}}=56216~(\mod p),$ ${64646}^{{x}_{4}}=18591~(\mod p).$ \end{tabular} \end{center} $$Поскольку порядок группы $${\langle}{5}^{{M}_{3}}{\rangle}$$ равен 23, а группы $${\langle}{5}^{{M}_{4}}{\rangle}$$ - всего 31, то при различных $$x_3$$, $$x_4$$ величины $${24920}^{{x}_{3}}$$ и $${64646}^{{x}_{4}}$$ пробегают, соответственно, по 23 и 31 различным значениям.
Тогда $$x_3$$ и $$x_4$$ можно найти полным перебором, проверив $$x_3=0,1,\ldots,22$$, $$x_3=0,1,\ldots,30$$. В нашем случае $${x}_{3}=14$$, $${x}_{4}=12$$. Числа $${x}_{1}$$ и $${x}_{2}$$ также можно искать полным перебором, но для них можно ещё уменьшить количество попыток. Будем искать
$${x}_{1}={x}_{1,1}+2{x}_{1,2}+4{x}_{1,3}+8{x}_{1,4}, $$где $${x}_{1,i} \in \left\{0,1\right\}.$$
Имеем:
$${\left({97697}^{{x}_{1}}\right)}^{8}={\left({97697}^{8}~(\mod p)\right)}^{{x}_{1.1}}={(-1)}^{{x}_{1,1}}={55814}^{8}=(-1)~(\mod p).$$То есть $$(-1)^{x_{1,1}} = -1$$. Отсюда $${x}_{1,1}=1.$$
Далее,
$${\left({97697}^{{x}_{1}}\right)}^{4}={97697}^{4+8{x}_{1,2}}=15467 \cdot {(-1)}^{{x}_{1,2}}={55814}^{4}=87206~(\mod p).$$Проверим оба варианта $$x_{1,2}=0,1$$:
$$15467 \cdot {(-1)}^{0} \neq 87206~(\mod p),$$ $$15467 \cdot {(-1)}^{1} = 87206~(\mod p).$$Отсюда $${x}_{1,2}=1$$.
Далее,
$${\left({97697}^{{x}_{1}}\right)}^{2}={97697}^{2+4+8{x}_{1,3}}=101570 \cdot {\left(-1\right)}^{{x}_{1,3}}={55814}^{2}=1103~(\mod p).$$Опять, из двух вариантов выбираем верный: $${x}_{1,3}=1$$.
Наконец,
$${97697}^{1+2+4+8{x}_{1,4}}=46859 \cdot {\left(-1\right)}^{{x}_{1,4}}=55814~(\mod p),$$откуда $${x}_{1,4}=1.$$ Проверяем:
$${97697}^{15}=55814~(\mod p)\Rightarrow {x}_{1}=15.$$Аналогично находим $${x}_{2}={x}_{2,1}+3{x}_{2,2}=5$$.
По китайской теореме об остатках находим $$x=69359$$.
Для небольших $$p$$ бывает удобно вычислять все степени примитивного корня и строить на основе этих вычислений две таблицы, называемые таблицами индексов. Таблицы индексов используются для быстрого решения некоторых задач по модулю простого числа $$p$$.
Приведем эти таблицы для примитивного корня 2 по модулю 37:
|
|
Например, чтобы определить индекс по числу 13, нужно в первой таблице перейти к столбцу "1" и строке "3". Итак, $${ind}_{2}13=11$$. Наоборот, для нахождения числа по его индексу 11 нужно во второй таблице перейти в столбец "1" строку "1". Имеем: $${2}^{11}=13\mod37$$.
Пример 3.8 Решим с помощью таблицы индексов сравнение:
$$8x=-11\mod37.$$Будем далее использовать примитивный корень $$2$$ и построенные для него выше таблицы. Правую часть сравнения заменяем положительным вычетом:
$$8x=26\mod37.$$"Индексируем" левую и правую части сравнения:
$${ind}\ 8+{ind}\ x={ind}\ 26~(\mod 36).$$Находим в первой таблице для простого числа 37 значение $$ind\ 8$$ и $$ind\ 26$$ и подставляем в сравнение. Получим:
$$3+ind\ x=12~(\mod 36),$$Откуда
$$ind\ x=9~(\mod 36).$$По второй таблице находим число, соответствующее индексу 9. Получим: $$x=31~(\mod 37).$$
Пример 3.9 С помощью индексов решить сравнение:
$$13{x}^{4}=22~(\mod 37).$$Индексируем сравнение:
$$ind\ 13+4\cdot ind\ x=ind\ 22.$$По первой таблице индексов находим: $$ind\ 13=11$$, $$ind\ 22=31$$. Отсюда: $$11+4\cdot ind\ x=31~(\mod 36)$$, или $$4 ind\ x=20~(\mod 36)$$. Последнему сравнению удовлетворяют $$ind\ x=5,14,23,32$$. Для каждого из них по второй таблице индексов найдем $$x=32,30,5,7$$.
Для полиномов справедлив аналог теоремы о делении с остатком. Для любых полиномов $$f(x)$$ и $$g(x)$$ существуют полиномы $$q(x)$$, $$r(x)$$, такие, что
$$f\left(x\right)=q\left(x\right)g\left(x\right)+r\left(x\right),{deg}\left(r\left(x\right)\right)<{deg}\left(g\left(x\right)\right).$$Если $$r(x) = 0$$, то $$g(x)$$ называется делителем многочлена $$f(x)$$.
Определение 3.23 Наибольшим общим делителем многочленов $$f(x)$$ и $$g(x)$$ называется их общий делитель, который делится на любой другой их общий делитель.
Для полиномов наибольший общий делитель определён с точностью до умножения на константу. Будем всегда выбирать полином с единичным старшим членом. Полином, не имеющий нетривиальных делителей, называется неприводимым.
Определение 3.24 Более точно, полином $$f(x)$$ степени $$d$$ над полем $$F$$ называется неприводимым, если не существует двух таких полиномов $$g(x)$$, $$h(x)$$ степеней меньших $$d$$, что $$f(x) = g(x)h(x)$$.
В качестве примера рассмотрим алгоритм формирования контрольной суммы CRC (Cyclic Redundancy Code). Он используется для того, чтобы при передаче сообщения через подверженные помехам каналы выявлять ошибки передачи данных. Контрольная сумма передаётся вместе с данными, а затем принимающая сторона также вычисляет контрольную сумму и сравнивает её с принятой.
Для формирования контрольной суммы биты данных представляются как коэффициенты полинома над полем $$\mathbb{Z}_2$$. Затем вычисляется остаток от деления этого полинома на некоторый фиксированный полином, называемый порождающим. Остаток от деления - снова полином, коэффициенты которого вновь рассматриваются как биты некоторого числа, являющегося контрольной суммой.
Пример 3.10 Используя порождающий полином $$f\left(x\right)={x}^{5}+{x}^{2}+1$$, построить контрольную сумму сообщения: $$10001\ 01101\ 10001\ 10110\ 00010$$.
Решение. Представим сообщение в виде:
$$ g(x)=\left(\left(\left(\left({x}^{4}+1 \right) \cdot {x}^{5}+ \left({x}^{3}+{x}^{2}+1\right)\right) \cdot {x}^{5}+\left({x}^{4}+1 \right)\right) \cdot {x}^{5}+\right.\\ +\left.\left({x}^{4}+{x}^{2}+x\right)\right){x}^{5}+x= \\ =\left(\left(\left(g_{0}(x){x}^{5}+{g}_{1}(x)\right){x}^{5}+{g}_{2}(x) \right){x}^{5}+{g}_{3}(x)\right){x}^{5}+{g}_{4}(x). $$Обозначим $${c}_{i}\left(x\right)=\left(\left({\dots}\left({g}_{0}\left(x\right){x}^{5}+{g}_{1}\left(x\right)\right){x}^{5}{\dots}\right)+{g}_{i}\left(x\right)\right)~(\mod f\left(x\right)).$$
Очевидно, $${c}_{i+1}\left(x\right)={c}_{i}\left(x\right){x}^{5}+{g}_{i+1}\left(x\right)~(\mod f\left(x\right)).$$
По модулю $$f(x)$$ имеем:
$${x}^{5}=f\left(x\right)+{x}^{2}+1={x}^{2}+1;$$ $${c}_{0}\left(x\right)={g}_{0}\left(x\right)={x}^{4}+1;$$ $$ {c}_{1}\left(x\right)={c}_{o}\left(x\right){x}^{5}+{g}_{1}\left(x\right)= \left({x}^{4}+1\right)\left({x}^{2}+1\right)+{x}^{3}+{x}^{2}+1=\\ ={x}^{6}+{x}^{4}+{x}^{3}=xf\left(x\right)+{x}^{3}+x+{x}^{4}+{x}^{3}={x}^{4}+x; $$ $$ {c}_{2}\left(x\right)={c}_{1}\left(x\right){x}^{5}+{g}_{2}\left(x\right)=\left({x}^{4}+x\right)\left({x}^{2}+1\right)+{x}^{4}+1=\\ ={x}^{6}+{x}^{3}+x+1={xf}\left(x\right)+1=1; $$ $${c}_{3}\left(x\right)={c}_{2}\left(x\right){x}^{5}+{g}_{3}\left(x\right)={x}^{2}+1+{x}^{4}+{x}^{2}+x={x}^{4}+x+1;$$ $$ {c}_{4}\left(x\right)={c}_{3}\left(x\right){x}^{5}+{g}_{4}\left(x\right)=\left({x}^{4}+x+1\right)\left({x}^{2}+1\right)+x=\\ ={x}^{6}+{x}^{4}+{x}^{3}+x+{x}^{2}+1+x=x f(x)+{x}^{4}+{x}^{2}+x+1=\\ ={x}^{4}+{x}^{2}+x+1. $$Поэтому контрольная сумма равна (10111).
Пример 3.11 По каналу сначала была передана контрольная сумма сообщения $$01101$$, а затем начало передаваться сообщение. Злоумышленник смог испортить сообщение, и его контрольная сумма стала $$11011$$. Какие биты должен злоумышленник присоединить к хвосту сообщения, чтобы контрольная сумма совпала с переданной пользователю?
Решение. Имеем: $${c}_{n}\left(x\right)={x}^{4}+{x}^{3}+x+1$$, при этом требуется, чтобы $${c}_{n+1}\left(x\right)={x}^{3}+{x}^{2}+1$$. В то же время:
$${c}_{n+1}\left(x\right)={c}_{n}\left(x\right) \cdot {x}^{5}+{g}_{n+1}\left(x\right).$$Злоумышленник всего-навсего должен нужным образом подобрать $${g}_{n+1}(x)$$:
$${g}_{n+1}\left(x\right)={c}_{n+1}\left(x\right)-{x}^{5}{c}_{n}\left(x\right)={x}^{3}+{x}^{2}+1+{x}^{5}\left({x}^{4}+{x}^{3}+x+1\right)={x}^{4}+{x}^{2}+1.$$Итак, злоумышленник должен отправить 5 бит: 10101, и контрольная сумма испорченного сообщения совпадёт с контрольной суммой, которую ожидает пользователь.
Если полином $$f(x)$$ неприводим, то для любого полинома $$q(x)$$ степени меньше $$d$$ имеем $$\GCD(f(x), q(x)) = 1$$. Выполнив расширенный алгоритм Евклида, мы можем найти такие многочлены $$u(x)$$, $$v(x)$$, что $$f(x) u(x) + q(x) v(x) = 1$$. Очевидно, тогда $$q(x)v(x) - 1$$ лежит в идеале $$f(x) F[x]$$ всех многочленов, кратных $$f(x)$$, а $$q(x)v(x)$$ - в смежном классе, содержащем единицу. Другими словами, $$v(x)q(x) = 1 ~(\mod f(x))$$, или $$v(x) = q(x)^{- 1} ~(\mod f(x))$$.
Пример 3.12 Найти в кольце $$\mathbb{Z}_2[x]$$ полином, обратный к полиному $$g\left(x\right)={x}^{5}$$ по модулю $$f(x)=x^{7}+{x}^{3}+1$$.
Решение. Выполним расширенный алгоритм Евклида. Положим $${r}_{0}\left(x\right)=f\left(x\right),{r}_{1}\left(x\right)=g\left(x\right).$$
Следовательно, $${x}^{5}+{x}^{2}+x=g{\left(x\right)}^{-1}~(\mod f\left(x\right))$$.
Более подходящим для программной реализации будет следующее описание расширенного алгоритма Евклида:
Вход: полиномы $$f(x)$$, $$g(x)$$, степень $$f(x)$$ не меньше степени $$g(x)$$.
Выход: полиномы $$\GCD(f(x),g(x))$$, $$u(x)$$ и $$v(x)$$ такие, что $$\GCD(f(x),g(x)) = u(x) f(x) + v(x) g(x)$$.
Когда полином $$f(x)$$ над полем $$F$$ степени $$d$$ неприводим, множество полиномов над $$F$$ степени $$\leq d$$ относительно сложения и умножения по модулю $$f(x)$$ образуют поле. Известно, что над полем $$F$$ простого порядка существуют неприводимые многочлены любой степени. Поэтому описанным способом можно построить поля любого порядка $$p^d$$. Построение неприводимых полиномов является важной задачей.
Поскольку все поля одинакового порядка изоморфны, для поля данного порядка $$q$$ вводится единое обозначение: $$GF(q)$$.
Пример 3.13 Построить неприводимый полином степени $$5$$ над $$\mathbb{Z}_2$$.
Решение. Пока нам неизвестен более быстрый метод, будем использовать метод пробных делений. Если полином степени 5 приводим, то один из его сомножителей является неприводимым и имеет степень меньше 3. Полиномы степени меньше 3: $$x$$, $$x + 1$$, $$x^2$$, $$x^2+x$$, $$x^2+1$$, $$x^2+x+1$$. Из них неприводимыми являются $$x$$, $$x + 1$$, $$x^2 + x + 1$$.
Выберем случайно полином. Пусть им оказался $$x^5+x^4+1$$. Он не делится на $$x$$ и на $$x + 1$$, так как 0 и 1 не являются его корнями. Однако $$x^5+x^4+1 = (x^2+x+1)(x^3+x+1)$$.
Пусть случайно выбран полином $$x^5+x^2+1$$. Снова, 0 и 1 не являются его корнями, и $$x^5+x^2+1=(x^2+x+1)(x^3+x^2)+1$$. Следовательно, этот полином неприводим.
Разумеется, существуют более простые способы тестирования полиномов над конечным полем на приводимость, например, алгоритм Берлекемпа [1].
Вход: полином $$f(x)$$ степени $$d$$ над конечным полем $$F$$, не имеющий кратных корней (что проверяется вычислением его наибольшего общего делителя с производной $$f'(x)$$.
Выход: ответ на вопрос - приводим ли многочлен.
Пример 3.14 Протестировать на приводимость полином $${x}^{8}+{x}^{4}+{x}^{3}+x+1$$.
Решение. Вычислим, согласно алгоритму, остатки от деления
| $$k$$ | $${r}_{k}\left(x\right)={x}^{2k}~(\mod f\left(x\right)+{x}^{k})$$ |
| 1 | $${x}^{2}+x $$ |
| 2 | $${x}^{4}+{x}^{2}$$ |
| 3 | $${x}^{6}+{x}^{3}$$ |
| 4 | $${x}^{8}+{x}^{4}={x}^{3}+x+1 $$ |
| 5 | $${x}^{10}+{x}^{5}={x}^{6}+{x}^{3}+{x}^{2} $$ |
| 6 | $${x}^{12}+{x}^{6}={x}^{7}+{x}^{6}+x^{5}+{x}^{3}+x+1 $$ |
| 7 | $${x}^{14}+{x}^{7}={x}^{3}+x$$ |
Построим и приведём к трапецеидальному виду матрицу коэффициентов этих полиномов:
$$ A=\left(\begin{matrix} 1 1 \\ 1 1 1 1 1 1 \\ 1 1 1 \\ 1 1 1\\ 1 1 \\ 1 1 \\ 1 1 \\ \end{matrix}\right). $$Переместим вторую строку на первое место, третью строку - на второе, шестую - на третье, далее пойдут по порядку первая, четвертая, сумма пятой и третьей строк, седьмая строка. Имеем:
$$ A\sim \left(\begin{matrix} 1 1 1 1 1 1\\ 1 1 1 \\ 1 1 \\ 1 1 \\ 1 1 1\\ 1 \\ 1 1 \\ \end{matrix}\right)\sim \left( \begin{matrix} 1 1 1 1 1 1\\ 1 1 1 \\ 1 1 \\ 1 1 \\ 1 \\ 1 \\ 1\\ \end{matrix}\right). $$Итак, ранг матрицы равен $$7 = d - 1$$, следовательно, полином неприводим.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.