Мультипликативные группы вычетов
Введение
В арифметике вычетов под множеством классов по модулю часто понимают кольцо вычетов, обозначаемое \(\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)\) обозначает функцию Эйлера — количество чисел, меньших и взаимно простых с модулем.
Например, для модуля 10 группа обратимых вычетов записывается как \(\mathbb{Z}_{10}^{\times}=\{[1],[3],[7],[9]\}\), и действительно \(\varphi(10)=4\).
Теоремы: теорема Эйлера и малая теорема Ферма
если элемент 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}\).
Проверим для примера: поскольку \(\varphi(10)=4\), то для a=3 имеет место равенство \(3^{4}\equiv 1\pmod{10}\).
Реті элемента и примитивные корни (генераторы)
для элемента 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\) — удвоенная такая степень.
Так, модуль 7 обладает примитивным корнем 3: степени 3 дают все ненулевые вычеты по модулю 7, что можно записать как \(\{3^1,3^2,3^3,3^4,3^5,3^6\}\equiv\{1,2,3,4,5,6\}\pmod{7}\) (последовательные вычисления: \(3^1\equiv 3\pmod{7}\), \(3^2\equiv 2\pmod{7}\), \(3^3\equiv 6\pmod{7}\), \(3^4\equiv 4\pmod{7}\), \(3^5\equiv 5\pmod{7}\), \(3^6\equiv 1\pmod{7}\)).
Структура группы для разных модулей
Общая структура группы \(\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}\).
Например, обратный к 3 по модулю 11 равен 4, поскольку \(3^{-1}\equiv 4\pmod{11}\) и \(3\cdot 4\equiv 1\pmod{11}\).
Для определения порядка элемента 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}\).
Заключение
Мультипликативные группы вычетов — это центральный объект в изучении свойств вычетов и их применений. Понимание порядка элементов, структуры групп и способов вычисления обратных важно как в теории чисел, так и в практических алгоритмах.
Для дальнейшего изучения рекомендуется ознакомиться с доказательствами теорем о структуре групп вычетов, с китайской теоремой об остатках и с алгоритмами вычисления обратных и порядков элементов, а также с примерами разложения групп для разных типов модулей.