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

Глава 1. Простые числа                                                   12

       Алгебраические структуры, содержащие абелеву группы по сложению
и группу по умножению, связанные законами дистрибутивности, называются
полями. Конечные поля называют также полями Галуа по имени гениального
французского математика Эвариста Галуа (1811 – 1832), исследовавшего
эти поля, и обозначают GF (q). Более подробные сведения о конечных
полях читатель может получить из монографии Р.Лидла и Г.Нидеррайтера
«Конечные поля» [73].
       Пусть G–произвольная группа по умножению.

Определение 1.2. Порядком элемента a группы G ( обозначается через
ordG (a)) называется наименьшее число k такое, что ak = 1. Порядком
группы называется число ее элементов.

       Следующее свойство, связывающее порядки элементов с порядком
группы, широко используется в различных алгоритмах, описанных ниже. Эта
теорема была доказана знаменитым французским математиком Жозефом
Луи Ланранжем (1736–1813).

Теорема 1.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) равен порядку группы.