Защита информации 2 5 (стр. 3 из 14)

Если

по модулю принадлежит показателю , то числа по модулю несравнимы.

Если

по модулю принадлежит показателю , то тогда и только тогда, когда в частности (при ), , тогда и только тогда, когда делится на .

Пусть

по модулю принадлежит показателю . Тогда делится на . Таким образом, показатели, которым числа принадлежат по модулю , есть делители . Числа, принадлежащие показателю (если такие существуют), называются первообразными корнями по модулю .

Символ Лежандра. Функция чисел

и , определенная для простых нечетных и целых , не делящихся на называется символом Лежандра и обозначается

, если сравнение разрешимо, в противном случае же случае

Символ Якоби.Символ Якоби является обобщением символа Лежандра и служит для упрощения вычисления последнего. Пусть

- нечетное натуральное число,

- его разложение на простые множители. Для всякого целого , , символ Якоби определяется по формуле:

Цепные дроби. Цепная дробь – один из важнейших способов представления чисел и функций. Цепная дробь есть выражение вида

где

- любое целое число, - натуральные числа, называемые неполными частными.

2. Алгебраические основы

Понятие группы.

Группой называется непустое множество

с алгебраической операцией * на нём, для которой выполняется первые 3 из четырёх следующих аксиом.

1). Операция * ассоциативна, т.е. для любых

.

2). В G имеется единичный элемент (или единица) e такой, что для любого

3). Для каждого a Î G существует обратный элемент

такой, что

4). Для любых

Если дополнительно группа удовлетворяет четвертой аксиоме, то группа называется абелевой или коммутативной.

Множество

образует группу относительно операции сложения. То же можно сказать относительно рациональных чисел , вещественных чисел и комплексных чисел .

Через

будет отличать аддитивную группу классов вычетов по модулю m.

Если взять все классы вычетов, взаимно простые с модулем m, и определить их умножение по модулю m, то получится группа, обозначаемая через

. Число элементов конечной группы называется порядком группы и обозначается через .

Группа

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

Циклическими являются группы

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

Циклическая группа всегда коммутативна.

Подгруппы групп.

Подмножество

группы называется подгруппой этой группы, если H образует группу относительно операции группы .

Подгруппы группы

, отличные от тривиальных групп , называется собственными подгруппами.

Гамоморфизмы групп.

Отображение

группы в группу называется гомоморфизмом, если оно согласовано с операциями на группах и , т.е. для любых элементов

Кольца и поля.

Кольцом называется множество

с двумя бинарными операциями, обозначаемыми символами “+” и “*”, такими что:

1).

– абелева группа;

2). Операция умножения ассоциативна, т.е. для всех

;

3). Выполняются законы дистрибутивности, т.е. для всех