Мультипликативная группа кольца вычетов

Мультипликативная группа кольца вычетов по модулю m — мультипликативная группа обратимых элементов кольца вычетов по модулю m. При этом в качестве множества элементов может рассматриваться любая приведенная система вычетов по модулю m.

Приведённая система вычетов


Приведённая система вычетов по модулю m — множество всех чисел полной системы вычетов по модулю m, взаимно простых с m. В качестве приведённой системы вычетов по модулю m обычно берутся взаимно простые с m числа от 1 до m - 1.
Пример: приведенной системой вычетов по модулю 42 будет: \{ 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41 \}.


Свойства 

  • Набор любых φ(m) (φ(m) — функция Эйлера) чисел, взаимно простых с m и несравнимых попарно по модулю m, образуют приведённую систему вычетов.
  • Если НОД(a,m) = 1'', то множество значений ax, где x пробегает приведенную систему вычетов по модулю m, также является приведенной системой вычетов по модулю m.
  • Если НОД(k,m) = 1, то множество значений kx + my, где x пробегает приведенную систему вычетов по модулю m и y пробегает приведенную систему вычетов по модулю k, является приведенной системой вычетов по модулю km.
  • В случае, когда число m простое, приведенная система вычетов по модулю m отличается от полной системы вычетов отсутствием нуля.
  • Если a — элемент приведенной системы вычетов по модулю m, то, для любого b сравнение axb(modm) разрешимо относительно x.

 Приведённая система вычетов с умножением по модулю m образует группу, называемую мультипликативной группой или группой обратимых элементов кольца вычетов по модулю m, которая обозначается Zm× или U(Zm).
 Если m простое, то, как отмечалось выше, элементы 1, 2, ...,m-1 входят в Zm×. В этом случае Zm× является полем.

Формы записи


 Кольцо вычетов по модулю n обозначают Z/nZ  или Zn. Его мультипликативную группу, как и в общем случае групп обратимых элементов колец, обозначают (Z/nZ),   (Z/nZ)×,   U(Z/nZ),   E(Z/nZ),   Zn×,   U(Zn).

Простейший случай


 Чтобы понять структуру группы U(Z/nZ), можно рассмотреть частный случай n=pa, где p — простое число, и обобщить его. Рассмотрим простейший случай, когда a=1, т.е. n=p.
 Теорема: U(Z/pZ) — циклическая группа.
Пример: Рассмотрим группу U(Z/9Z)


U(Z/9Z) = \{1,2,4,5,7,8\}
 Генератором группы является число 2.
212 (mod9)
224 (mod9)
238 (mod9)
247 (mod9)
255 (mod9)
261 (mod9)
 Как видим, любой элемент группы U(Z/9Z) может быть представлен в виде 2l, где 1<φ(m). То есть группа U(Z/9Z) - циклическая.

Общий случай


 Для рассмотрения общего случая необходимо определение примитивного корня. Примитивный корень по простому модулю p – это число, которое вместе со своим классом вычетов порождает группу U(Z/pZ).

Примеры: 2 — примитивный корень по модулю 11; 8 — примитивный корень по модулю 11; 3 не является примитивным корнем по модулю 11.
  В случае целого модуля n определение такое же.
 Структуру группы определяет следующая теорема: Если p — нечётное простое число и l – целое положительное, то существуют примитивные корни по модулю pl, то есть U(Z/plZ) — циклическая группа.
 Из китайской теоремы об остатках следует, что при n=p1a1p2a2...plal имеет место изоморфизм U(Z/nZ)U(Z/p1a1Z)×U(Z/p2a2Z)×U(Z/plalZ).
 Группа U(Z/piaiZ) — циклическая. Её порядок равен piai1(pi1).
 Группа U(Z/2aZ) — также циклическая. Её порядок равен a при a=1 или a=2. При a3 эта группа есть прямое произведение двух циклических групп, порядков 2 и 2a2.
 Группа U(Z/nZ) циклична тогда и только тогда, когда n=pa или n=2pa или n = 2 или n = 4, где p — нечётное простое число. В общем случае U(Z/nZ) как абелева группа представляется прямым произведением циклических примарных групп, изоморфных Zui+.

Подгруппа свидетелей простоты


 Пусть m — нечётное число большее 1. Число m1 однозначно представляется в виде m1=2st, где t нечётно. Целое число a, 1<a<m, называется свидетелем простоты числа m, если выполняется одно из условий:

  • at1(modm)

 или

  • существует целое число k, $0\leq k
     Если число m — составное, существует подгруппа мультипликативной группы кольца вычетов, называемая подгруппой свидетелей простоты. Её элементы, возведённые в степень m1, совпадают с 1 по модулю m.
    Пример: m=9. Есть 6 остатков, взаимно простых с 9, это 1,2,4,5,7 и 8. 8 эквивалентно 1 по модулю 9, значит 88 эквивалентно 1 по модулю 9. Значит, 1 и 8 — свидетели простоты числа 9. В данном случае \{1, 8\} — подгруппа свидетелей простоты.

    Свойства


    Экспонента группы


     Экспонента группы равна функции Кармайкла λ(n)=\operatornamelcm(p1a11(p11),,psas1(ps1)).

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


     Порядок группы равен функции Эйлера: |U(Z/mZ)|=φ(m).. Отсюда и из изоморфизма U(Z/mZ)U(Z/p1a1Z)×U(Z/p2a2Z)×...U(Z/plalZ) можно получить ещё один способ доказательства равенства φ(m)=φ(m1)φ(m2)...φ(mt) при m=m1m2...mt

    Порождающее множество


    U(Z/nZ) — циклическая группа тогда и только тогда, когда φ(n)=λ(n). В случае циклической группы генератор называется первообразным корнем.

    Пример


     Приведённая система вычетов по модулю 10 состоит из 4 классов вычетов: [1]10,[3]10,[7]10,[9]10. Относительно определённого для классов вычетов умножения они образуют группу, причём [3]10 и [7]10 взаимно обратны (то есть [3]10[7]10=[1]10), а [1]10 и [9]10 обратны сами себе.

    Структура группы


     Запись Cn означает «циклическая группа порядка n».
    nU(Z/nZ)φ(n)λ(n)генератор nU(Z/nZ)φ(n)λ(n)генератор
    2C111133C2×C10201010, 2
    3C222234C1616163
    4C222335C2×C1224126, 2
    5C444236C2×C612619, 5
    6C222537C3636362
    7C666338C1818183
    8C2×C2427, 339C2×C12241238, 2
    9C666240C2×C2×C416439, 11, 3
    10C444341C4040406
    11C101010242C2×C612613, 5
    12C2×C2425, 743C4242423
    13C121212244C2×C10201043, 3
    14C666345C2×C12241244, 2
    15C2×C48414, 246C2222225
    16C2×C48415, 347C4646465
    17C161616348C2×C2×C416447, 7, 5
    18C666549C4242423
    19C181818250C2020203
    20C2×C48419, 351C2×C16321650, 5
    21C2×C612620, 252C2×C12241251, 7
    22C101010753C5252522
    23C222222554C1818185
    24C2×C2×C2825, 7, 1355C2×C20402021, 2
    25C202020256C2×C2×C624613, 29, 3
    26C121212757C2×C18361820, 2
    27C181818258C2828283
    28C2×C612613, 359C5858582
    29C282828260C2×C2×C416411, 19, 7
    30C2×C48411, 761C6060602
    31C303030362C3030303
    32C2×C816831, 363C6×C63662, 5

    Применение


     На сложности дискретного логарифмирования в мультипликативной группе кольца вычетов основана криптографическая стойкость шифрсистемы Эль-Гамаля.

    История


     Вклад в исследование структуры мультипликативной группы кольца вычетов внесли Артин, Билхарц, Брауэр, Вильсон, Гаусс, Лагранж, Лемер, Уоринг, Ферма, Хули, Эйлер. Лагранж доказал лемму о том, что если f(x)k[x], и k — поле, то f имеет не более n различных корней, где n — степень f. Он же доказал важное следствие этой леммы, заключающееся в сравнении xp11(x1)(x2)...(xp+1)mod(p). Эйлер доказал малую теорему Ферма. Уоринг сформулировал теорему Вильсона, а Лагранж её доказал. Эйлер предположил существование примитивных корней по модулю простого числа. Гаусс это доказал. Артин выдвинул свою гипотезу о существовании и количественной оценке простых чисел, по модулю которых заданное целое число является первообразным корнем. Брауэр внес вклад в исследование проблемы существования наборов последовательных целых чисел, каждое из которых — k-ая степень по модулю p. Билхарц доказал аналог гипотезы Артина. Хули доказал гипотезу Артина с предположением справедливости расширенной гипотезы Римана в полях алгебраических чисел.