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

Мультипликативная группа кольца вычетов по модулю 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. Билхарц доказал аналог гипотезы Артина. Хули доказал гипотезуАртина с предположением справедливости расширенной гипотезы Римана вполях алгебраических чисел.