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

Введение

В арифметике вычетов под множеством классов по модулю часто понимают кольцо вычетов, обозначаемое $\mathbb{Z}_n$. Внутри этого кольца множество обратимых элементов по умножению образует мультипликативную группу вычетов, которую обычно обозначают $\mathbb{Z}_n^{\times}$.

Идея состоит в том, что два целых числа считаются эквивалентными, если они совпадают по остатку при делении на модуль; это обозначается как $a\equiv b \pmod{n}$. Элемент вычета обратим тогда и только тогда, когда он взаимно прост с модулем, то есть выполняется условие $\gcd(a,n)=1$.

Понимание структуры группы $\mathbb{Z}_n^{\times}$ важно для теории чисел, компьютерной арифметики и криптографии: многие алгоритмы опираются на свойства обратимых остатков и их порядков.

Определение и основные свойства

Кольцо вычетов - множество классов вычетов по модулю, обычно записываемое как $\mathbb{Z}_n$, с операциями сложения и умножения по модулю.

Мультипликативная группа вычетов - множество обратимых по умножению классов в $\mathbb{Z}_n$, обозначаемое $\mathbb{Z}_n^{\times}$. Это действительно группа относительно умножения по модулю.

Множество $\mathbb{Z}_n^{\times}$ можно формально записать как $\mathbb{Z}_n^{\times}=\{[a]\in\mathbb{Z}_n:\gcd(a,n)=1\}$. Его порядок (число элементов) равен значению функции Эйлера: $|\mathbb{Z}_n^{\times}|=\varphi(n)$, где $\varphi(n)$ обозначает функцию Эйлера — количество чисел, меньших и взаимно простых с модулем.

Теоремы: теорема Эйлера и малая теорема Ферма

Теорема Эйлера - если элемент a взаимно прост с модулем n (то есть $\gcd(a,n)=1$), то выполняется равенство $a^{\varphi(n)}\equiv 1\pmod{n}$.

Частный случай этой теоремы — малая теорема Ферма: если модуль p прост, то для любого числа a, не делящегося на p, выполняется $a^{p-1}\equiv 1\pmod{p}$. В терминах групп это следует из того, что группа $\mathbb{Z}_n^{\times}$ при p является циклической группы порядка $\mathbb{Z}_p^{\times}\cong C_{p-1}$.

Идея доказательства Эйлера — рассмотреть произведение всех элементов группы $\mathbb{Z}_n^{\times}$ и умножить его на a; получаем, что возведение a в степень порядка группы даёт нейтральный элемент, то есть $a^{\varphi(n)}\equiv 1\pmod{n}$.

Порядок элемента и примитивные корни (генераторы)

Порядок элемента - для элемента a из группы $\mathbb{Z}_n^{\times}$ порядок определяется как наименьшее положительное целое k такое, что $\operatorname{ord}_n(a)=k:\;a^{k}\equiv 1\pmod{n}$.

Порядок каждого элемента делит порядок всей группы: если ord(a)=k, то выполняется соотношение $\operatorname{ord}_n(a)\mid\varphi(n)$. Элемент называют примитивным корнем или генератором, если его порядок равен φ(n), то есть $\operatorname{ord}_n(g)=\varphi(n)$.

Не для всех модулей существуют генераторы. Известная теорема утверждает, что примитивные корни существуют тогда и только тогда, когда n принадлежит множеству $n\in\{2,4,p^k,2p^k\}$, где под $p^k$ понимается степень нечетного простого числа, а под $2p^k$ — удвоенная такая степень.

Структура группы для разных модулей

Общая структура группы $\mathbb{Z}_n^{\times}$ для составного модуля обычно описывается с помощью китайской теоремы об остатках: справедливо изоморфизмное представление $\mathbb{Z}_n^{\times}\cong\prod \mathbb{Z}_{p_i^{k_i}}^{\times}$, из которого для мультипликативной группы вытекает $\mathbb{Z}_n\cong\prod \mathbb{Z}_{p_i^{k_i}}$.

В частных случаях получаются разные структуры: для модуля 8 группа обратимых вычетов изоморфна $\mathbb{Z}_8^{\times}\cong C_2\times C_2$, то есть нециклическая группа порядка 4, а для модуля 9 группа $\mathbb{Z}_9^{\times}\cong C_6$ и действительно $\varphi(9)=6$.

Понимание этих разложений позволяет предсказывать наличие генераторов и вычислять порядок элементов через разложение на простые множители и анализ групп на простых степенях.

Вычисления: нахождение обратного элемента и порядка

Для нахождения обратного элемента по модулю используют расширенный алгоритм Евклида: нужно найти целые x,y удовлетворяющие уравнению $ax+ny=1$. Тогда x — обратный к a в кольце вычетов, то есть $a^{-1}\equiv x\pmod{n}$.

Для определения порядка элемента a в группе часто достаточно проверить делители φ(n): если для простого делителя q числа φ(n) выполнено, что $a^{\varphi(n)/q}\not\equiv 1\pmod{n}$ для всех q, то ord(a)=φ(n). Это даёт практический алгоритм проверки, является ли элемент генератором.

Приложения

Мультипликативные группы вычетов лежат в основе криптографических схем. В RSA выборе ключей опираются на то, что при произведении двух простых p и q значение φ(n) известно тому, кто знает p и q. Ключи e и d выбирают так, чтобы выполнялось $ed\equiv 1\pmod{\varphi(n)}$.

Шифруют сообщение m, возводя в степень e по модулю n: $c\equiv m^{e}\pmod{n}$. Расшифровка осуществляется возведением в степень d: $m\equiv c^{d}\pmod{n}$, что следует из равенства $m^{ed}\equiv m\pmod{n}$ по теореме Эйлера при необходимых условиях.

В протоколах обмена ключами (например, Диффи-Хеллмана) используют генератор g в группе $\mathbb{Z}_p^{\times}\cong C_{p-1}$ (или другом подходящем циклическом подгруппе): участники отправляют значения вида $g^{a}\pmod{p}$, а общий ключ получается как $g^{ab}\pmod{p}$.

Заключение

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

Для дальнейшего изучения рекомендуется ознакомиться с доказательствами теорем о структуре групп вычетов, с китайской теоремой об остатках и с алгоритмами вычисления обратных и порядков элементов, а также с примерами разложения групп для разных типов модулей.