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

Приведённая система вычетов — это в теории чисел подмножество полной системы вычетов по модулю \(n\), состоящее из всех классов вычетов, взаимно простых с \(n\). Иными словами, это множество чисел, взятых по одному из каждого класса вычетов по модулю \(n\), которые не имеют общих делителей с \(n\), кроме 1. Приведённая система вычетов является фундаментальным понятием в модульной арифметике, теории колец и криптографии, так как она образует мультипликативную группу обратимых элементов кольца вычетов \(\mathbb{Z}_n\).

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

Пусть \(n\) — натуральное число, большее 1. Полная система вычетов по модулю \(n\) — это множество \(\{0, 1, 2, \dots, n-1\}\), содержащее ровно \(n\) элементов, каждый из которых представляет свой класс эквивалентности по модулю \(n\). Приведённая система вычетов по модулю \(n\) — это подмножество полной системы, состоящее из тех чисел \(a\), для которых \(\gcd(a, n) = 1\) (наибольший общий делитель равен 1). Количество элементов в приведённой системе вычетов равно значению функции Эйлера \(\varphi(n)\).

Формально, приведённая система вычетов по модулю \(n\) — это множество: \[ \{a \in \mathbb{Z} \mid 0 \leq a < n, \ \gcd(a, n) = 1\}. \] Например, для \(n = 12\) полная система вычетов: \(\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}\). Числа, взаимно простые с 12: 1, 5, 7, 11. Таким образом, приведённая система вычетов по модулю 12: \(\{1, 5, 7, 11\}\), и \(\varphi(12) = 4\).

Свойства

• Мультипликативная замкнутость: Если \(a\) и \(b\) принадлежат приведённой системе вычетов по модулю \(n\), то их произведение \(a \cdot b \mod n\) также принадлежит этой системе. Это следует из того, что если \(\gcd(a, n) = 1\) и \(\gcd(b, n) = 1\), то \(\gcd(ab, n) = 1\).
• Обратимость: Для любого элемента \(a\) из приведённой системы существует единственный элемент \(b\) (также из этой системы), такой что \(a \cdot b \equiv 1 \pmod{n}\). Это означает, что приведённая система образует мультипликативную группу — группу единиц кольца \(\mathbb{Z}_n\), обозначаемую \(U(n)\) или \((\mathbb{Z}/n\mathbb{Z})^\times\).
• Цикличность: Группа \(U(n)\) является циклической тогда и только тогда, когда \(n = 1, 2, 4, p^k\) или \(2p^k\), где \(p\) — нечётное простое число, \(k \geq 1\). В противном случае группа нециклическая, но всегда абелева.

История

Понятие приведённой системы вычетов восходит к работам Леонарда Эйлера в XVIII веке. Эйлер ввёл функцию \(\varphi(n)\), названную в его честь, и изучал свойства чисел, взаимно простых с модулем. В 1763 году он опубликовал теорему, известную как теорема Эйлера: если \(\gcd(a, n) = 1\), то \(a^{\varphi(n)} \equiv 1 \pmod{n}\). Эта теорема является обобщением малой теоремы Ферма и напрямую связана с приведённой системой вычетов, так как \(\varphi(n)\) — это порядок мультипликативной группы \(U(n)\). Дальнейшее развитие теория получила в работах Карла Фридриха Гаусса, который в «Арифметических исследованиях» (1801) систематизировал модульную арифметику и ввёл понятие полной и приведённой систем вычетов в современном виде.

Способы построения

Приведённую систему вычетов по модулю \(n\) можно построить несколькими способами:

1. Прямой перебор: Выписать все числа от 0 до \(n-1\) и отобрать те, для которых \(\gcd(a, n) = 1\).
2. Использование функции Эйлера: Сначала вычислить \(\varphi(n)\), затем перебрать числа, проверяя взаимную простоту.
3. Рекурсивный метод: Если \(n = p^k\) (степень простого числа), то приведённая система состоит из всех чисел, не кратных \(p\). Например, для \(n = 9 = 3^2\): числа, не делящиеся на 3: 1, 2, 4, 5, 7, 8 — всего \(\varphi(9) = 6\).
4. Китайская теорема об остатках: Если \(n = n_1 \cdot n_2\) и \(\gcd(n_1, n_2) = 1\), то приведённая система по модулю \(n\) может быть получена как декартово произведение приведённых систем по модулям \(n_1\) и \(n_2\). Это свойство мультипликативности функции Эйлера: \(\varphi(n_1 n_2) = \varphi(n_1) \cdot \varphi(n_2)\).

Примеры

Малые модули

• \(n = 1\): Приведённая система вычетов по модулю 1 содержит только число 0, так как \(\gcd(0, 1) = 1\). Однако обычно рассматривают \(n > 1\).
• \(n = 2\): \(\{1\}\), \(\varphi(2) = 1\).
• \(n = 3\): \(\{1, 2\}\), \(\varphi(3) = 2\).
• \(n = 4\): \(\{1, 3\}\), \(\varphi(4) = 2\).
• \(n = 5\): \(\{1, 2, 3, 4\}\), \(\varphi(5) = 4\).
• \(n = 6\): \(\{1, 5\}\), \(\varphi(6) = 2\).
• \(n = 7\): \(\{1, 2, 3, 4, 5, 6\}\), \(\varphi(7) = 6\).
• \(n = 8\): \(\{1, 3, 5, 7\}\), \(\varphi(8) = 4\).
• \(n = 9\): \(\{1, 2, 4, 5, 7, 8\}\), \(\varphi(9) = 6\).
• \(n = 10\): \(\{1, 3, 7, 9\}\), \(\varphi(10) = 4\).

Модуль, равный простому числу

Если \(n = p\) — простое число, то все числа от 1 до \(p-1\) взаимно просты с \(p\). Следовательно, приведённая система вычетов по модулю \(p\) — это \(\{1, 2, \dots, p-1\}\), и \(\varphi(p) = p-1\). Группа \(U(p)\) является циклической порядка \(p-1\).

Применение

Криптография

Приведённая система вычетов лежит в основе многих криптографических алгоритмов. В частности, в алгоритме RSA выбор открытого ключа \(e\) и закрытого ключа \(d\) основан на том, что \(e \cdot d \equiv 1 \pmod{\varphi(n)}\), где \(n = p \cdot q\) — произведение двух простых чисел. Обратимость \(e\) по модулю \(\varphi(n)\) гарантируется, если \(\gcd(e, \varphi(n)) = 1\), то есть \(e\) принадлежит приведённой системе вычетов по модулю \(\varphi(n)\). Кроме того, в криптосистеме Эль-Гамаля и в протоколе Диффи — Хеллмана используются циклические подгруппы группы \(U(p)\) для простого \(p\).

Теоретико-числовые вычисления

• Теорема Эйлера: \(a^{\varphi(n)} \equiv 1 \pmod{n}\) для \(\gcd(a, n) = 1\) используется для упрощения вычислений степеней по модулю.
• Малая теорема Ферма: частный случай для простого модуля: \(a^{p-1} \equiv 1 \pmod{p}\).
• Китайская теорема об остатках: позволяет разбивать вычисления по составному модулю на вычисления по взаимно простым модулям, что часто используется в алгоритмах быстрого возведения в степень.

Теория групп

Группа \(U(n)\) является важным примером конечной абелевой группы. Её структура изучается в теории чисел и алгебре. Знание порядка группы \(\varphi(n)\) и её цикличности позволяет решать задачи дискретного логарифмирования и строить генераторы псевдослучайных чисел.

Связь с функцией Эйлера

Функция Эйлера \(\varphi(n)\) определяется как количество чисел от 1 до \(n\), взаимно простых с \(n\). Это в точности мощность приведённой системы вычетов по модулю \(n\). Основные свойства:

• \(\varphi(p) = p-1\) для простого \(p\).
• \(\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)\).
• \(\varphi(mn) = \varphi(m) \cdot \varphi(n)\), если \(\gcd(m, n) = 1\).
• Для произвольного \(n = p_1^{k_1} p_2^{k_2} \dots p_r^{k_r}\):

\[ \varphi(n) = n \prod_{i=1}^r \left(1 - \frac{1}{p_i}\right). \]

Интересные факты

• Приведённая система вычетов по модулю \(n\) может быть выбрана не единственным образом. Например, для \(n = 12\) можно взять \(\{1, 5, 7, 11\}\) или \(\{5, 7, 11, 13\}\) (последнее число 13 ≡ 1 mod 12, но 13 не входит в стандартный диапазон 0–11, однако по модулю 12 оно эквивалентно 1). Обычно выбирают наименьшие неотрицательные представители.
• Группа \(U(n)\) является циклической для \(n = 2, 4, p^k, 2p^k\). Например, \(U(5)\) циклическая с образующим элементом 2 (так как 2^1=2, 2^2=4, 2^3=3, 2^4=1). Для \(n = 8\) группа \(U(8) = \{1, 3, 5, 7\}\) нециклическая, так как каждый элемент в квадрате даёт 1 (3^2=9≡1, 5^2=25≡1, 7^2=49≡1), то есть группа изоморфна \(\mathbb{Z}_2 \times \mathbb{Z}_2\).
• В криптографии на эллиптических кривых (ECC) аналогом приведённой системы вычетов является группа точек эллиптической кривой над конечным полем, которая также является конечной абелевой группой.

Критика и ограничения

Приведённая система вычетов эффективна только для модулей, для которых можно быстро вычислить функцию Эйлера. Для больших составных чисел, не являющихся произведением известных простых, вычисление \(\varphi(n)\) требует факторизации \(n\), что является вычислительно сложной задачей. Это свойство, однако, используется в криптографии RSA как основа безопасности: злоумышленник, не зная разложения \(n\) на простые множители, не может вычислить \(\varphi(n)\) и, следовательно, найти закрытый ключ. Кроме того, для некоторых модулей (например, степеней двойки) группа \(U(n)\) нециклическая, что может усложнять построение генераторов.

Источники

• Виноградов И. М. Основы теории чисел. — М.: Наука, 1972.
• Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966.
• Кострикин А. И. Введение в алгебру. Часть I. Основы алгебры. — М.: Физматлит, 2004.
• Ireland K., Rosen M. A Classical Introduction to Modern Number Theory. — Springer, 1990.