Loading [MathJax]/jax/element/mml/optable/SuppMathOperators.js

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

Мультипликативная группа кольца вычетов по модулю 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,которая обозначается Z×m или U(Zm).
 Если m простое, то, как отмечалось выше, элементы 1, 2,...,m-1 входят в Z×m. В этом случаеZ×m является полем.

Формызаписи


 Кольцо вычетов по модулю n обозначают Z/nZ или Zn. Его мультипликативную группу, как и в общем случаегрупп обратимых элементов колец, обозначают(Z/nZ),   (Z/nZ)×,  U(Z/nZ),   E(Z/nZ),  Z×n,   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=pa11pa22...pall имеет место изоморфизмU(Z/nZ)U(Z/pa11Z)×U(Z/pa22Z)×U(Z/pallZ).
 Группа U(Z/paiiZ) — циклическая. Её порядокравен pai1i(pi1).
 Группа U(Z/2aZ) — также циклическая. Её порядокравен a при a=1 или a=2. При a эта группа есть прямоепроизведение двух циклических групп, порядков 2 и 2^{a-2}.
 Группа U(\mathbb{Z}/n\mathbb{Z}) циклична тогда и только тогда, когдаn=p^a или n=2p^a или n = 2 или n = 4, где p —нечётное простое число. В общем случае U(\mathbb{Z}/n\mathbb{Z}) какабелева группа представляется прямым произведением циклических примарныхгрупп, изоморфных \mathbb{Z}_{u_i}^{+}.

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


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

  • a^t\equiv 1\pmod m

 или

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

    Свойства


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


     Экспонента группы равна функции Кармайкла\lambda(n)=\textstyle \operatornamelcm(p_1^{a_1-1}(p_1-1),\cdots, p_s^{a_s-1}(p_s-1)).

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


     Порядок группы равен функции Эйлера:|U(\mathbb{Z}/m\mathbb{Z})|=\varphi(m).. Отсюда и из изоморфизмаU(\mathbb{Z}/m\mathbb{Z})U(\mathbb{Z}/p_1^{a_1}\mathbb{Z})\times U(\mathbb{Z}/p_2^{a_2}\mathbb{Z})\times ... U(\mathbb{Z}/p_l^{a_l}\mathbb{Z})можно получить ещё один способ доказательства равенства\varphi(m) = \varphi(m_1)\varphi(m_2)...\varphi(m_t) приm = m_1m_2...m_t

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


    U(\mathbb{Z}/n\mathbb{Z}) — циклическая группа тогда и только тогда,когда \varphi(n)=\lambda(n). В случае циклической группы генераторназывается первообразным корнем.

    Пример


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

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


     Запись C_n означает «циклическая группа порядка n».
    n\;U(\mathbb{Z}/n\mathbb{Z})\varphi(n)\lambda(n)\;генератор n\;U(\mathbb{Z}/n\mathbb{Z})\varphi(n)\lambda(n)\;генератор
    2C\textsubscript111133C\textsubscript2×C\textsubscript10201010, 2
    3C\textsubscript222234C\textsubscript1616163
    4C\textsubscript222335C\textsubscript2×C\textsubscript1224126, 2
    5C\textsubscript444236C\textsubscript2×C\textsubscript612619, 5
    6C\textsubscript222537C\textsubscript3636362
    7C\textsubscript666338C\textsubscript1818183
    8C\textsubscript2×C\textsubscript2427, 339C\textsubscript2×C\textsubscript12241238, 2
    9C\textsubscript666240C\textsubscript2×C\textsubscript2×C\textsubscript416439,11, 3
    10C\textsubscript444341C\textsubscript4040406
    11C\textsubscript101010242C\textsubscript2×C\textsubscript612613, 5
    12C\textsubscript2×C\textsubscript2425, 743C\textsubscript4242423
    13C\textsubscript121212244C\textsubscript2×C\textsubscript10201043, 3
    14C\textsubscript666345C\textsubscript2×C\textsubscript12241244, 2
    15C\textsubscript2×C\textsubscript48414, 246C\textsubscript2222225
    16C\textsubscript2×C\textsubscript48415, 347C\textsubscript4646465
    17C\textsubscript161616348C\textsubscript2×C\textsubscript2×C\textsubscript416447,7, 5
    18C\textsubscript666549C\textsubscript4242423
    19C\textsubscript181818250C\textsubscript2020203
    20C\textsubscript2×C\textsubscript48419, 351C\textsubscript2×C\textsubscript16321650, 5
    21C\textsubscript2×C\textsubscript612620, 252C\textsubscript2×C\textsubscript12241251, 7
    22C\textsubscript101010753C\textsubscript5252522
    23C\textsubscript222222554C\textsubscript1818185
    24C\textsubscript2×C\textsubscript2×C\textsubscript2825, 7, 1355C\textsubscript2×C\textsubscript20402021, 2
    25C\textsubscript202020256C\textsubscript2×C\textsubscript2×C\textsubscript624613,29, 3
    26C\textsubscript121212757C\textsubscript2×C\textsubscript18361820, 2
    27C\textsubscript181818258C\textsubscript2828283
    28C\textsubscript2×C\textsubscript612613, 359C\textsubscript5858582
    29C\textsubscript282828260C\textsubscript2×C\textsubscript2×C\textsubscript416411,19, 7
    30C\textsubscript2×C\textsubscript48411, 761C\textsubscript6060602
    31C\textsubscript303030362C\textsubscript3030303
    32C\textsubscript2×C\textsubscript816831, 363C\textsubscript6×C\textsubscript63662, 5

    Применение


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

    История


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