Группы, кольца

Определение. Группа – множество G с операцией, которая: замкнута, обладает нейтральным элементом, ассоциативна, относительно нее каждый элемент обладает обратным. Группу с коммутативной операцией называют коммутативной или абелевой.

Практически все группы в криптографии – абелевы. Обозначение группы: (G, знак операции).

Мультипликативная группа (G, ·):

Групповая операция – умножение ·;

Нейтральный элемент – единица 1;

Обратный элемент – a ^-1;

Многократное применение операции – возведение в степень

a ⁵ = a · a · a · a · a.

Аддитивная группа (G, +):

Групповая операция – сложение +;

Нейтральный элемент – ноль 0;

Обратный элемент – – a;

Многократное применение операции – умножение

5 · a = a + a + a + a + a.

Образующая g – такой элемент группы, что любой другой элемент может быть получен путем многократного применения к нему групповой операции. Запись .

В мультипликативной группе:

В аддитивной группе:

Определение. Кольцо – множество R с двумя операциями: сложением и умножением, в котором обе операции замкнуты, ассоциативны, обладают нейтральным элементом, связаны законом дистрибутивности, а сложение коммутативно и для каждого элемента есть обратный по сложению. Обозначение кольца (R, ·, +).

В коммутативном кольце операция умножения дополнительно обладает свойством коммутативности.

Основное кольцо, важное для криптологии – коммутативное кольцо остатков от деления на натуральное число n, большее 1, которое также называют кольцом вычетов по модулю n и обозначают Z _n или Z / n Z.