Алгебраические структуры

Множество элементов G с заданной на нем некоторой бинарной операцией "∙" называется группоидом, если для любых двух его элементов а, b однозначно определён элемент
c=а ∙ b, который также лежит в G и считается результатом выполнения этой бинарной операции над этими элементами а и b. Обычно используется обозначение (G,∙).

Множество элементов G с заданной на нем бинарной операцией "∙" называется группой, если выполнены три условия:

1. Операция "∙" ассоциативна, то есть (а ∙ b) ∙ с = а ∙ (b ∙ с), для любых элементов группы G.
2. Существует элемент е из G, такой, что для любого g из G выполняются равенства
   е ∙ g = g ∙ е = g,
3. Для любого g из G существует элемент g ' из G со свойством g ∙ g ' = g ' ∙ g = е.

Обычно используется обозначение (G,∙).

Элемент е из G называют нейтральным элементом группы, а элемент g ' – обратным элементом к g. Для обратного элемента g ' обычно используется обозначение g ' = g ^-1.

Следует отметить, что в группе G нейтральный элемент е и элемент g ^-1, обратный к элементу g, определены однозначно.

С точки зрения решения уравнений, основное свойство группы состоит в том, что в ней однозначно разрешимы уравнения вида

a ∙ х = b,
y ∙ a = b

при любых a, b ∈ G. Упражнение: найдите a и b.

Повторим, что группоидом (G,∙) называется любое множество G с любой определённой на ней бинарной операцией ∙.

Если при всех a, b и с эти уравнения

a ∙ х = b,
y ∙ a = b

однозначно разрешимы относительно х и у, то (G,∙) называется квазигруппой. Для квазигруппы не обязательно выполняются условия 1)-3) из определения группы. Вместе с тем ассоциативная квазигруппа всегда является группой. Ассоциативность – это выполнение тождества 1).

Упражнение: обоснуйте это.

Решение уравнения y ∙ a = b обычно обозначается как y=b / a.

Решение уравнения a ∙ х = b обычно обозначается как x=a \ b.

Это правое и левое деление в квазигруппе. Если она коммутативна, т.е. выполняется тождество u ∙ v = v ∙ u, то правое и левое деления совпадают, и тогда используется для обозначения операции деления обычная дробная черта.

Квазигруппы находят криптографические применения в эндоморфных совершенных шифрах с минимальным числом ключей. Шифр называется эндоморфным, если алфавиты шифрвеличин открытых X и закрытых Y текстов совпадают. Для таких шифров количество ключей минимально, если мощность множества ключей K совпадает с мощностью множеств шифрвеличин открытых X и закрытых Y текстов. Обычно при этом полагают K=X=Y. В таком случае пусть (G,∙) – квазигруппа на множестве G= K=X=Y.
Если x ∈X, y ∈Y, k ∈K, то уравнением зашифрования будет уравнение y= x ∙ k, уравнением расшифрования будет уравнение x=y / k, уравнением дешифрования (уравнением определения ключа) будет уравнение k= x \ y. Сообщение (открытый текст) из n шифрвеличин (слово из n букв) x ₁ … x_n на ключевом потоке (гамме шифра) k ₁ , …, k_n криптографически преобразуется в сообщение (закрытый текст) из n шифрвеличин (слово из n букв) y ₁ … y_n посредством последовательности уравнений зашифрования y_m= x_m ∙ k_m,
где m= 1 ,…n.

Операция "∙" называется коммутативной, если для любых двух элементов а и b из G выполнено равенство а ∙ b = b ∙ а. В этом случае группа G называется коммутативной или абелевой. Абелевы группы находят применение в асимметричных алгоритмах шифрования, в том числе с использованием задач дискретного логарифмирования в конечных полях и на эллиптических кривых.

Примером абелевой группы является множество комплексных корней степени п из 1 с операцией умножения корней как комплексных чисел – циклическая группа (Z _n,+), т.е. множество вычетов по модулю п с операцией сложения по модулю п.

Множество R с двумя бинарными ассоциативными операциями сложения "+" и умножения "∙" называется кольцом, если выполнены следующие условия:

• - множество R с бинарной операцией сложения "+" является абелевой группой,
• - операция "∙" удовлетворяет условию дистрибутивности относительно операции "+", т.е. (а + b) ∙ с = а ∙ с + b ∙ с и а ∙ (b + с) = а ∙ b + a ∙ с.

Если операция "∙" коммутативна, то кольцо называется коммутативным.

Если операция "∙" ассоциативна, то кольцо называется ассоциативным.

Примером кольца является множество Z_n, образующее полную систему вычетов целых чисел по модулю n с операциями сложения и умножения по модулю n, причем это кольцо является коммутативным и ассоциативным.

Нейтральный элемент кольца относительно операции "+" называют нулем кольца и обозначают через 0. При умножении на 0 любого элемента кольца будет получаться 0.

Можно отдельно рассмотреть множество всех ненулевых элементов кольца с операцией умножения "∙". Для этого множества можно ввести понятия нейтрального и обратного элементов относительно операции умножения "∙". Нейтральный элемент кольца относительно операции "∙" называют единицей кольца и обозначают через 1.

Единица существует не в любом кольце. Например, в кольце четных целых чисел единица отсутствует. Даже если в кольце и существует единица, то в общем случае обратные элементы определены не для всех ненулевых элементов кольца. Для данного кольца R, имеющего единицу, через обозначают R* обычно множество его обратимых элементов с операцией умножения.

Полем называется коммутативное кольцо с единицей, отличной от нуля, в котором любой ненулевой элемент обратим.

Кольцо вычетов целых чисел по модулю п является полем в том и только в том случае, когда п – простое число. Другими примерами полей являются хорошо известные множества рациональных, действительных и комплексных чисел с обычными операциями сложения и умножения.

Поиск по сайту: