Математические основы защиты информации. Ишмухаметов Ш.Т - 18 стр.

Глава 1. Системы шифрования с открытым ключом                            19

теорема была доказана знаменитым французским математиком Жозефом
Луи Ланранжем (1736–1813).

Теорема 2.1. (Лагранж). Порядок любого элемента конечной группы
является делителем порядка группы.

       Доказательство. Пусть элемент a конечной группы < G, · > имеет
порядок k > 1. Тогда элементы a, a2 , ... , ak−1 , ak = 1 различны и сами
образуют группу A, содержащую k элементов и являющуюся подгруппой
G. Различные смежные классы b · A для b ∈ G имеют также мощность k , а
объединение их дает в совокупности группу G. Значит, число элементов G
равно k · m, где m–число смежных классов, откуда вытекает утверждение
теоремы.
       Пример.         Рассмотрим кольцо Z p при p = 29. Ненулевые элементы
этого кольца образуют группу по умножению, порядок которой равен p −
1 = 28. По теореме Лагранжа порядок любого элемента a этой группы
является делителем 28, т.е. может принимать одно из следующих значений:
1, 2, 4, 7, 14 и 28.
           Элемент a ∈ G называется примитивным элементом или
генератором группы, если его порядок ordG (a) равен порядку группы.
Не любая группа имеет генератор. Группа, в которой есть генератор,
порождается одним элементом и называется циклической.

Малая теорема Ферма

      Знаменитый французский математик Пьер Ферма (1601–1665) доказал
теорему, которая известна как малая теорема Ферма.

Теорема 2.2. (Малая теорема Ферма) Если число p–простое, то для
любого натурального числа, не сравнимого с p выполняется сравнение

                                ap−1 ≡ 1 ( mod p)                     (2.1)

       Эта теорема является частным случаем теоремы Лагранжа (теор.2.1).
Действительно, при простом p множество ненулевых элементов кольца Zp