Определение. Группа – множество G с операцией, которая: замкнута, обладает нейтральным элементом, ассоциативна. Группу с коммутативной операцией называют коммутативной или абелевой.
Практически все группы в криптографии – абелевы. Обозначение группы: (G, знак операции).
Мультипликативная группа (G, · ):
Групповая операция – умножение · ;
Нейтральный элемент – единица 1 ;
Обратный элемент – a-1;
Многократное применение операции – возведение в степень
a5 = a · a · a · a · a.
Аддитивная группа (G, + ):
Групповая операция – сложение + ;
Нейтральный элемент – ноль 0 ;
Обратный элемент – – a;
Многократное применение операции – умножение
5 · a = a + a + a + a + a.
Образующая g – такой элемент группы, что любой другой элемент может быть получен путем многократного применения к нему групповой операции. Запись .
В мультипликативной группе:
В аддитивной группе:
Определение. Кольцо – множество R с двумя операциями: сложением и умножением, в котором обе операции замкнуты, ассоциативны, обладают нейтральным элементом, связаны законом дистрибутивности, а сложение коммутативно и для каждого элемента есть обратный по сложению. Обозначение кольца (R, ·, +).
В коммутативном кольце операция умножения дополнительно обладает свойством коммутативности.
Основное кольцо, важное для криптологии – коммутативное кольцо остатков от деления на натуральное число n, большее 1, которое также называют кольцом вычетов по модулю n и обозначают Zn или Z/nZ.