Алгебраические структуры. 
Криптографические методы защиты информации. 
Часть 1. Математические аспекты

Полугруппы и группы

Рассмотрим непустое множество X как систему элементов, над которыми могут выполняться действия, называемые операциями. Внутренней операцией т множества X называется функция т: Х^п —> X, где натуральное число п называется арностью операции. Внутренняя операция арности 2 называется бинарной, арности 1 — унарной. Бинарную операцию т обозначают символом (+,-,* и др.) и вместо т (х, у) пишут, например, х * у или просто ху.

Внутренняя бинарная операция * на X (далее для краткости — операция) называется:

• 1) ассоциативной, если х * (у * z) = (х * у) * z для любых х, у, z е X;
• 2) коммутативной, если х * у — у * х для любых х, у е X.

Множество G с одной внутренней бинарной операцией * называется.

группоидом, обозначается (G; *). Подмножество G' группоида (G; *) называется подгруппоидом, если оно замкнуто относительно операции *, т. е. если g, g' е G', то и gg' е G'.

Таблицей Кэли операции группоида ((?; *), где G — {#, …, g_n}, называют квадратную таблицу, у которой строки и столбцы «занумерованы» элементами gj, …, g_r, и на пересечении строки g, и столбца gj записан результат операции gg_/t i, j е (1,…, п).

Говорят, что элементы g и g' группоида G коммутируют (или перестановочны), если gg' = g’g. Группоид (G; *) называется коммутативным, если операция * на G коммутативна.

Элемент е е G называется нейтральным или единичным относительно операции *, если ge = eg = g для любого элемента g е G. В группоиде имеется не более одного единичного элемента е. Действительно, если е' — другая единица группоида, то е' = е’е = е.

Пример 2.1.

Дана таблица Кэли группоида G = {a, b, с, d), из которой следует:

{a, b, с} — коммутативный подгруппоид некоммутативного группоида G (cd ф dc) элементы b и с коммутируют, элемент а нейтральный. О Группоид (G;*) называется полугруппой, если операция * ассоциативна. Элемент 0 называется нулем полугруппы G, если Og = gO = О для любого g g G. Если полугруппа G имеет нуль, то он единственный.

Идемпотентом полугруппы G называется ее элемент г, если ii = i. Полугруппа G_y содержащая единственный идемпотент, называется унипотентной.

Полугруппу с единичным элементом называют моноидом (или полугруппой с единицей). Элемент g моноида G с единицей е называется обратимым, если найдется элемент g' е G, для которого gg' = g’g = е_у элементы g и g' называются взаимно обратными.

Если в моноиде G для элемента g имеется обратный элемент g', то он единственный (обозначается g-¹). В самом деле, если g" — другой обратный к g элемент, то, используя ассоциативность операции, имеем:

g' = g’e = g'(gg") = (g'g)g" = eg" = g" .

Если элементы g и h моноида обратимы, то обратим и gh_} где (g/г)^-1 =.

= А-¹Г¹;

Пример 2.2.

Моноидами являются множества:

• а) ЛГ₀ относительно сложения, нейтральный элемент — число 0;
• б) N относительно умножения, нейтральный элемент — число 1;
• в) Z относительно умножения, нейтральный элемент — число 1. D>

Группой называется моноид, все элементы которого обратимы. Иначе, группа — множество с ассоциативной операцией, содержащее единицу, где любой элемент обратим.

Группу можно рассматривать как унипотентную полугруппу. Действительно, если в группе и = i, то, умножив обе части на г¹, получаем i = е. Порядок конечной полугруппы или группы G (число элементов в G) обозначается |G| или ordG.

В полугруппе G определим произведение gX (Xg) элемента g и подмножества X:

Тогда множество целых (натуральных) чисел, кратных числу т, равно mZ (равно mN).

Подгруппой полугруппы или группы G называется подмножество G', являющееся группой, подполугруппой полугруппы G называется подмножество G'_y являющееся полугруппой, обозначается G' < G. Подполугруппа (подгруппа) G' называется собственной, если G' — собственное подмножество полугруппы (группы) G, обозначается G' < G.

Подгруппа G' называется максимальной в подмножестве У группы G, если G' с У и не найдется группы G" со свойством G' < G" с У. Множество всех обратимых элементов моноида G непусто и образует максималь;

ную подгруппу моноида G, называемую группой обратимых элементов моноида G (обозначается I_G). Если G — группа, то I_G = G.

Группу с коммутативной операцией называют коммутативной, или абелевой. В зависимости от полугрупповой (групповой) операции, сложения или умножения, полугруппу (группу) называют аддитивной или мультипликативной. Аддитивная группа коммутативна.

Пример 2.3.

Группами являются множества: R относительно сложения и R {0} относительно умножения; Z относительно сложения, mZ < Z; Q относительно сложения и Q {0} относительно умножения.

Полугруппами, но не группами являются множества N i Z относительно умножения. >

В силу ассоциативности операции полугруппы (группы) G для любых g_x>…, g_te G произведение g.g_t при t > 1 не зависит от расстановки скобок, если g_x = … = g_t = g, то g_x …g_t = g<. Отсюда g^{g^r = g^t+r, (gO^r = g^rr> ^B группе также выполнено: g° = e, g~^f= (g~^{)⁽.

Уравнение вида ax-b разрешимо в группе G для любых a, be G ив полугруппе G для любого be G и любого а е I_G. В обоих случаях х = а~^хЬ.