16.3. Группы

16.3.1. Свойства групп

Группой называется множество ${{\mathbb{G}}}$, на котором задана бинарная операция «$\circ$», удовлетворяющая следующим аксиомам:

• замкнутость:
  $$ \forall a,b \in {{\mathbb{G}}}~ a \circ b = c \in {{\mathbb{G}}}; $$
• ассоциативность:
  $$ \forall a,b,c \in {{\mathbb{G}}}~ (a \circ b) \circ c = a \circ (b \circ c); $$
• существование единичного элемента:
  $$ \exists ~ e \in {{\mathbb{G}}}: \forall a \in {{\mathbb{G}}}~ e \circ a = a \circ e = a; $$
• существование обратного элемента:
  $$ \forall a \in {{\mathbb{G}}}~ \exists ~ b \in {{\mathbb{G}}}: a \circ b = b \circ a = e. $$

Если

то такую группу называют коммутативной (или абелевой).

Если операция в группе задана как умножение «$\cdot$», то группа называется мультипликативной. Для мультипликативной группы будем использовать следующие соглашения об обозначениях:

• нейтральный элемент: $e \equiv 1$;
• обратный элемент: $a^{-1}$;
• повторение операции над одним аргументом $k$ раз (возведение в степень k): $a^k$.

Если операция задана как сложение «$+$», то группа называется аддитивной. Соглашение об обозначениях для аддитивной группы:

• нейтральный элемент: $e \equiv 0$;
• обратный элемент: $-a$;
• повторение операции над одним аргументом $k$ раз (умножение на k): $ka$.

Подмножество группы, удовлетворяющее аксиомам группы, называется подгруппой.

Порядком $|{{\mathbb{G}}}|$ группы ${{\mathbb{G}}}$ называется число элементов в группе. Пусть группа мультипликативная. Для любого элемента $a \in {{\mathbb{G}}}$ выполняется $a^{|{{\mathbb{G}}}|} = 1$.

Порядком элемента $a$ называется минимальное натуральное число

Порядок элемента, согласно теореме Лагранжа, делит порядок группы:

16.3.2. Циклические группы

Генератором $g \in {{\mathbb{G}}}$ называется элемент, порождающий всю группу:

Группа, в которой существует генератор, называется циклической.

Если конечная группа не циклическая, то в ней существуют циклические подгруппы, порождённые всеми элементами. Любой элемент $a$ группы порождает либо циклическую подгруппу

порядка $\ord(a)$, если порядок элемента $\ord(a) < |{{\mathbb{G}}}|$, либо всю группу

если порядок элемента равен порядку группы $\ord(a) = |{{\mathbb{G}}}|$. Порядок любой подгруппы, как и порядок элемента, делит порядок всей группы.

Представим циклическую группу через генератор $g$ как

и каждый элемент $g^i$ возведём в степени $1, 2, \ldots, |{{\mathbb{G}}}|$. Тогда

• элементы $g^i$, для которых число $i$ взаимно просто с $|{{\mathbb{G}}}|$, породят снова всю группу
  $$ {{\mathbb{G}}}= \{ g^i, g^{2i}, g^{3i}, \dots, g^{|{{\mathbb{G}}}| i} = 1 \}, $$
  так как степени $\{i, 2i, 3i, \dots, |{{\mathbb{G}}}| i \}$ по модулю $|{{\mathbb{G}}}|$ образуют перестановку чисел $\{1, 2, 3, \dots, |{{\mathbb{G}}}|\}$; следовательно, $g^i$ – тоже генератор, число таких чисел $i$ равно по определению функции Эйлера $\varphi(|{{\mathbb{G}}}|)$ ($\varphi(n)$ – количество взаимно простых с $n$ целых чисел в диапазоне $[1,n-1]$);
• элементы $g^i$, для которых $i$ имеют общие делители
  $$ d_i = \gcd(i, |{{\mathbb{G}}}|) \neq 1 $$
  c $|{{\mathbb{G}}}|$, породят подгруппы
  $$ \{ g^i, g^{2i}, g^{3i}, \dots, g^{\frac{i}{d_i} |{{\mathbb{G}}}|} = 1\}, $$
  так как степень последнего элемента кратна $|{{\mathbb{G}}}|$; следовательно, такие $g^i$ образуют циклические подгруппы порядка $d_i$.

Из предыдущего утверждения следует, что число генераторов в циклической группе равно

Для проверки, является ли элемент генератором всей группы, требуется знать разложение порядка группы $|{{\mathbb{G}}}|$ на множители. Далее элемент возводится в степени, равные всем делителям порядка группы, и сравнивается с единичным элементом $e$. Если ни одна из степеней не равна $e$, то этот элемент является примитивным элементом или генератором группы. В противном случае элемент будет генератором какой-либо подгруппы.

Задача разложения числа на множители является трудной для вычисления. На сложности её решения, например, основана криптосистема RSA. Поэтому при создании больших групп желательно заранее знать разложение порядка группы на множители для возможности выбора генератора.

16.3.3. Группа ${{\mathbb{Z}}}_p^*$Zp*

Группой ${{\mathbb{Z}}}_p^*$ называется группа

где $p$ – простое число, операция в группе – умножение $\ast$ по ${\operatorname{mod}}p$.

Группа ${{\mathbb{Z}}}_p^*$ – циклическая, порядок –

Число генераторов в группе –

Из того, что ${{\mathbb{Z}}}_p^*$ – группа, для простого $p$ и любого $a \in [2, p-1] \mod p$ следует малая теорема Ферма:

На малой теореме Ферма основаны многие тесты проверки числа на простоту.

Пример. Рассмотрим группу ${{\mathbb{Z}}}_{19}^*$. Порядок группы – 18. Делители: 2, 3, 6, 9. Является ли 12 генератором?

12 – генератор подгруппы 6-го порядка. Является ли 13 генератором?

13 – генератор всей группы.

Пример. В таблице [tab:Zp-sample] приведён пример группы ${{\mathbb{Z}}}_{13}^*$. Число генераторов – $\varphi(12) = 4$. Подгруппы:

верхний индекс обозначает порядок подгруппы.

16.3.4. Группа $\mathbb{Z}_n^*$Zn*

Функция Эйлера $\varphi(n)$ определяется как количество натуральных чисел, взаимно простых с $n$ на отрезке от 1 до $n-1$.

Если $n=p$ – простое число, то

Если $n$ – составное число и

разложено на простые множители $p_i$, то

Группой ${{\mathbb{Z}}}_n^*$ называется группа

с операцией умножения $\ast$ по ${\operatorname{mod}}n$.

Порядок группы –

Группа ${{\mathbb{Z}}}_p^*$ – частный случай группы ${{\mathbb{Z}}}_n^*$.

Если $n$ – составное (не простое) число, то группа ${{\mathbb{Z}}}_n^*$ – нециклическая.

Из того, что ${{\mathbb{Z}}}_n^*$ – группа, для любых $a \neq 0, n > 1: \gcd(a,n) = 1$ следует теорема Эйлера:

При возведении в степень, если $\gcd(a,n) = 1$, выполняется

Пример. В таблице [tab:Zn-sample] приведена нециклическая группа ${{\mathbb{Z}}}_{21}^*$ и её циклические подгруппы

верхний индекс обозначает порядок подгруппы, нижний индекс нумерует различные подгруппы одного порядка.

16.3.5. Конечные поля

Полем называется множество ${{\mathbb{F}}}$, для которого:

• заданы две бинарные операции, условно называемые операциями умножения «$\cdot$» и сложения «$+$»;
• выполняются аксиомы группы для операции «сложения»: 1. замкнутость:
  $$\forall a, b \in {{\mathbb{F}}}~ a + b \in {{\mathbb{F}}};$$
  2. ассоциативность:
  $$\forall a, b, c \in {{\mathbb{F}}}~ (a+b)+c = a+(b+c);$$
  3. существование нейтрального элемента по сложению (часто обозначаемого как «0»):
  $$\exists 0 \in {{\mathbb{F}}}: \forall a \in {{\mathbb{F}}}~ a + 0 = 0 + a = a; $$
  4. существование обратного элемента:
  $$\forall a \in {{\mathbb{F}}}\exists -a: a + (-a) = 0; $$
• выполняются аксиомы группы для операции «умножения», за одним исключением: 1. замкнутость:
  $$\forall a, b \in {{\mathbb{F}}}~ a \cdot b \in {{\mathbb{F}}}; $$
  2. ассоциативность:
  $$\forall a, b, c \in {{\mathbb{F}}}~ (a \cdot b) \cdot c = a \cdot (b \cdot c);$$
  3. существование нейтрального элемента по умножению (часто обозначаемого как «1»):
  $$\exists 1 \in {{\mathbb{F}}}: \forall a \in {{\mathbb{F}}}~ a \cdot 1 = 1 \cdot a = a;$$
  4. существование обратного элемента по умножению для всех элементов множества, кроме нейтрального элемента по сложению:
  $$\forall a \in {{{\mathbb{F}}}\setminus \{0\}} \exists a^{-1}: a \cdot a^{-1} = a^{-1} \cdot a = 1;$$
• операции «сложения» и «умножения» коммутативны:
  $$ \begin{array}{l} \forall a, b \in {{\mathbb{F}}}~ a + b = b + a, \\ \forall a, b \in {{\mathbb{F}}}~ a \cdot b = b \cdot a; \\ \end{array} $$
• выполняется свойство дистрибутивности:
  $$ \forall a, b, c \in {{\mathbb{F}}}~ a \cdot (b + c) = (a \cdot b) + (a \cdot c). $$

Примеры бесконечных полей (с бесконечным числом элементов): поле рациональных чисел ${\mathbb{Q}}$, поле вещественных чисел ${\mathbb{R}}$, поле комплексных чисел ${\mathbb{C}}$ с обычными операциями сложения и умножения.

В криптографии рассматриваются конечные поля (с конечным числом элементов), называемые также полями Галуа.

Число элементов в любом конечном поле равно $p^n$, где $p$ – простое число и $n$ – натуральное число. Обозначения поля Галуа: ${{\mathbb{GF}}(p)}, {{\mathbb{GF}}(p^n)}, {{\mathbb{F}}}_p, {{\mathbb{F}}}_{p^n}$ (аббревиатура от англ. Galois field). Все поля Галуа ${{\mathbb{GF}}(p^n)}$ изоморфны друг другу (существует взаимно однозначное отображение между полями, сохраняющее действие всех операций). Другими словами, существует только одно поле Галуа ${{\mathbb{GF}}(p^n)}$ для фиксированных $p, n$.

Приведём примеры конечных полей.

Двоичное поле ${{\mathbb{GF}}(2)}$ состоит из двух элементов. Однако задать его можно разными способами.

• Как множество из двух чисел «0» и «1» с определёнными на нём операциями «сложение» и «умножение» как сложение и умножение чисел по модулю 2. Нейтральным элементом по сложению будет «0», по умножению – «1»:
  $$\begin{array}{ll} 0 + 0 = 0, & 0 \cdot 0 = 0, \\ 0 + 1 = 1, & 0 \cdot 1 = 0, \\ 1 + 0 = 1, & 1 \cdot 0 = 0, \\ 1 + 1 = 0, & 1 \cdot 1 = 1. \\ \end{array}$$
• Как множество из двух логических объектов «ЛОЖЬ» ($F$) и «ИСТИНА» ($T$) с определёнными на нём операциями «сложение» и «умножение» как булевые операции «исключающее или» и «и» соответственно. Нейтральным элементом по сложению будет «ЛОЖЬ», по умножению – «ИСТИНА»:
  $$\begin{array}{ll} F + F = F, & F \cdot F = F, \\ F + T = T, & F \cdot T = F, \\ T + F = T, & T \cdot F = F, \\ T + T = F, & T \cdot T = T. \\ \end{array}$$
• Как множество из двух логических объектов «ЛОЖЬ» ($F$) и «ИСТИНА» ($T$) с определёнными на нём операциями «сложение» и «умножение» как булевые операции «эквивалентность» и «или» соответственно. Нейтральным элементом по сложению будет «ИСТИНА», по умножению – «ЛОЖЬ»:
  $$\begin{array}{ll} F + F = T, & F \cdot F = F, \\ F + T = F, & F \cdot T = T, \\ T + F = F, & T \cdot F = T, \\ T + T = T, & T \cdot T = T. \\ \end{array}$$
• Как множество из двух чисел «0» и «1» с определёнными на нём операциями «сложение» и «умножение», заданными в табличном представлении. Нейтральным элементом по сложению будет «1», по умножению – «0»:
  $$\begin{array}{ll} 0 + 0 = 1, & 0 \cdot 0 = 0, \\ 0 + 1 = 0, & 0 \cdot 1 = 1, \\ 1 + 0 = 0, & 1 \cdot 0 = 1, \\ 1 + 1 = 1, & 1 \cdot 1 = 1. \\ \end{array}$$

Все перечисленные выше варианты множеств изоморфны друг другу. Поэтому в дальнейшем под конечным полем ${{\mathbb{GF}}(p)}$, где $p$ – простое число, будем понимать поле, заданное как множество целых чисел от $0$ до $p-1$ включительно, на котором операции «сложение» и «умножение» заданы как операции сложения и умножения чисел по модулю числа $p$. Например, поле ${{\mathbb{GF}}(7)}$ будем считать состоящим из 7 чисел $\{0, 1, 2, 3, 4, 5, 6\}$ с операциями умножения $(\cdot \mod 7)$ и сложения $(+ \mod 7)$ по модулю.

Конечное поле ${{\mathbb{GF}}(p^n)}, n > 1$ строится расширением базового поля ${{\mathbb{GF}}(p)}$. Элемент поля представляется как многочлен степени $n-1$ (или меньше) с коэффициентами из базового поля ${{\mathbb{GF}}(p)}$:

Операция сложения элементов в таком поле традиционно задаётся как операция сложения коэффициентов при одинаковых степенях в базовом поле ${{\mathbb{GF}}(p)}$. Операция умножения – как умножение многочленов со сложением и умножением коэффициентов в базовом поле ${{\mathbb{GF}}(p)}$ и дальнейшим приведением результата по модулю некоторого заданного (для поля) неприводимого

многочлена $m(x)$. Количество элементов в поле равно $p^n$.

Многочлен $g(x)$ называется примитивным элементом (генератором) поля, если его степени порождают все ненулевые элементы, то есть ${{\mathbb{GF}}(p^n)} \setminus \{0\}$, заданное неприводимым многочленом $m(x)$, за исключением нуля:

Пример. В таблице [tab:irreducible-gf2] приведены примеры многочленов над полем ${{\mathbb{GF}}(2)}$.