Математические основы криптологии
 Скачать 1.3 Mb.
|
ГруппыИзвестны две операции на множестве Z целых чисел: сложение и умножение. Обобщим понятие операции на произвольное множество. Пусть S - некоторое множество и пусть  обозначает множество упорядоченных пар (s,t) , где  и  . Тогда произвольное отображение из в S будем называть операцией (бинарной) на множестве S. В этом определении потребуем, чтобы образ каждой пары, был непременно элементом множества S. Это так называемое свойство замкнутости операции. Под алгебраической структурой или системой будем понимать некоторое множество S с одной или несколькими операциями на нем. Одной из таких алгебраических структур с одной операцией является группа.Определение. Группой (G,*) (в дальнейшем группу будем называть просто G) называется некоторое множество G c бинарной операцией * на нем, для которых выполняются следующие условия: 1. Операция * ассоциативна, т.е. для любых а,b,c, G справедливо a*(b*c)=(a*b)*с. 2. В G существует единичный элемент (или единица) е такой, что для любого аG а*е = e*a = a 3. Для каждого аG существует обратный элемент a -1G, такой что a * a -1 = a -1 * a = e Если группа G удовлетворяет также следующему условию: для любых а,bG справедливо а*b=b*а , то она называется коммутативной или абелевой группой. Единичный e и обратный а -1элемент группы G для каждого данного элемента аG определяется однозначно указанными выше условиями. Для всех элементов а,b G имеет место равенство (a*b) -1 = b -1*a -1. Для групповой операции * может быть использовано мультипликативное обозначение, как для обычного умножения. Тогда вместо а*b можно просто записать аb или аb . Однако при этом не предполагается, что операция * -это простое умножение. В ряде случаев для групповой операции * может быть использована аддитивная запись а+b вместо а*b. Тогда элемент группы G а+b называют суммой элементов а,b и 0 вместо е (единичный элемент в мультипликативной записи ) и -а вместо a -1. Такие обозначения обычно используются для абелевых групп. Если а G и n N в мультипликативной записи пишут an = aa ... a (nсомножителейa) и элемент anназывают nй степенью числа а. Если для групповой операции используется + т.е. аддитивное обозначение, то вместо an будем иметь nа=а + а + ... + а (n слагаемых а). Используя мультипликативные и аддитивные обозначения в общем случае имеем следующие правила:
|