Модулярная арифметика

Модулярная арифметика — это раздел теории чисел, изучающий арифметические операции над целыми числами, при которых числа рассматриваются с точностью до их остатка при делении на фиксированное натуральное число, называемое модулем. Основывается на понятии сравнения по модулю, введённом Карлом Фридрихом Гауссом в его работе «Арифметические исследования» (1801). Модулярная арифметика является фундаментом для многих разделов математики, криптографии, теории кодирования и информатики.

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

Пусть \( m \) — фиксированное натуральное число, большее единицы (модуль). Два целых числа \( a \) и \( b \) называются сравнимыми по модулю \( m \), если их разность \( a - b \) делится на \( m \) без остатка. Это отношение записывается как: \[ a \equiv b \pmod{m} \] и читается: «\( a \) сравнимо с \( b \) по модулю \( m \)».

Например, \( 17 \equiv 5 \pmod{12} \), так как \( 17 - 5 = 12 \) делится на \( 12 \); \( 100 \equiv 1 \pmod{99} \).

Отношение сравнения по модулю является отношением эквивалентности на множестве целых чисел. Оно разбивает все целые числа на классы эквивалентности, называемые классами вычетов по модулю \( m \). Каждый класс состоит из чисел, дающих одинаковый остаток при делении на \( m \). Обычно в качестве представителя класса берут наименьший неотрицательный остаток — число от \( 0 \) до \( m-1 \). Множество всех классов вычетов по модулю \( m \) обозначается \( \mathbb{Z}_m \) или \( \mathbb{Z}/m\mathbb{Z} \).

История

Истоки модулярной арифметики восходят к древним цивилизациям. Вавилоняне и греки использовали циклические счисления (например, 12-часовой и 60-минутный счёт). Китайский математик Сунь Цзы (III–V века н. э.) в трактате «Сунь Цзы Суань Цзин» описал решение задач, сводящихся к системам сравнений — прообраз китайской теоремы об остатках.

Систематическое изложение теории сравнений принадлежит немецкому математику Карлу Фридриху Гауссу. В 1801 году он опубликовал «Арифметические исследования» (лат. Disquisitiones Arithmeticae), где ввёл современную символику сравнений, доказал основные свойства и заложил основы теории чисел. Гаусс показал, что модулярная арифметика является частным случаем теории колец и групп.

В XX веке модулярная арифметика получила широкое применение в криптографии (алгоритм RSA, эллиптическая криптография), теории кодирования (коды Рида — Соломона), вычислительной технике (арифметика остатков) и цифровой обработке сигналов.

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

Отношение сравнения по модулю обладает свойствами, аналогичными свойствам равенства:

Рефлексивность: \( a \equiv a \pmod{m} \).
Симметричность: если \( a \equiv b \pmod{m} \), то \( b \equiv a \pmod{m} \).
Транзитивность: если \( a \equiv b \pmod{m} \) и \( b \equiv c \pmod{m} \), то \( a \equiv c \pmod{m} \).

Кроме того, сравнения можно складывать, вычитать и умножать:

Если \( a \equiv b \pmod{m} \) и \( c \equiv d \pmod{m} \), то:
\( a + c \equiv b + d \pmod{m} \)
\( a - c \equiv b - d \pmod{m} \)
\( a \cdot c \equiv b \cdot d \pmod{m} \)

Деление в модулярной арифметике не всегда возможно. Уравнение \( a \cdot x \equiv b \pmod{m} \) имеет решение тогда и только тогда, когда \( b \) делится на \( \gcd(a, m) \). Если \( a \) и \( m \) взаимно просты (\( \gcd(a, m) = 1 \)), то существует единственное решение — обратный элемент \( a^{-1} \pmod{m} \), который можно найти с помощью расширенного алгоритма Евклида.

Кольцо вычетов

Множество \( \mathbb{Z}_m \) с операциями сложения и умножения по модулю \( m \) образует кольцо вычетов. Это коммутативное кольцо с единицей. Если \( m \) — простое число, то \( \mathbb{Z}_m \) является полем (полем Галуа \( GF(m) \)), так как каждый ненулевой элемент имеет мультипликативный обратный. Если \( m \) — составное, то кольцо содержит делители нуля (ненулевые элементы, произведение которых равно нулю).

Примеры колец вычетов

\( \mathbb{Z}_2 \): элементы 0 и 1. Сложение по модулю 2 эквивалентно исключающему ИЛИ (XOR), умножение — логическому И (AND). Используется в булевой алгебре и цифровой электронике.
\( \mathbb{Z}_6 \): элементы 0,1,2,3,4,5. 2 и 3 — делители нуля, так как \( 2 \cdot 3 = 6 \equiv 0 \pmod{6} \). Обратимы только 1 и 5 (так как \( \gcd(1,6)=1, \gcd(5,6)=1 \)).
\( \mathbb{Z}_p \) (p простое): поле. Например, \( \mathbb{Z}_7 \) — поле из 7 элементов. Все ненулевые элементы обратимы: \( 2^{-1}=4 \), так как \( 2 \cdot 4 = 8 \equiv 1 \pmod{7} \).

Китайская теорема об остатках

Одна из центральных теорем модулярной арифметики — китайская теорема об остатках (КТО). Она утверждает, что система сравнений с попарно взаимно простыми модулями имеет единственное решение по модулю произведения этих модулей.

Формулировка: Пусть \( m_1, m_2, \dots, m_k \) — попарно взаимно простые натуральные числа (\( \gcd(m_i, m_j) = 1 \) для \( i \neq j \)). Тогда для любого набора остатков \( a_1, a_2, \dots, a_k \) существует единственное целое число \( x \), такое что: \[ \begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \dots \\ x \equiv a_k \pmod{m_k} \end{cases} \] и \( 0 \le x < M \), где \( M = m_1 \cdot m_2 \cdot \dots \cdot m_k \).

КТО лежит в основе многих алгоритмов: быстрого преобразования Фурье (через модулярные операции), криптосистемы RSA (для ускорения вычислений с помощью китайской теоремы), а также в системах счисления с избыточным основанием.

Применение модулярной арифметики

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

Модулярная арифметика — основа современной криптографии с открытым ключом. Наиболее известный пример — алгоритм RSA (Rivest–Shamir–Adleman), использующий модулярное возведение в степень и свойство мультипликативности функции Эйлера. Шифрование и дешифрование выполняются по модулю \( n = p \cdot q \), где \( p \) и \( q \) — большие простые числа. Безопасность RSA основана на трудности факторизации больших чисел. Другие криптосистемы: Эль-Гамаля, Диффи — Хеллмана, схемы на эллиптических кривых — также опираются на модулярные операции.

Вычислительная техника

Арифметика остатков (Residue Number System, RNS) — система счисления, в которой число представляется набором остатков от деления на несколько взаимно простых модулей. Операции сложения, вычитания и умножения в RNS выполняются параллельно по каждому модулю независимо, что значительно ускоряет вычисления. RNS применяется в цифровых сигнальных процессорах (DSP), в системах цифровой обработки сигналов (фильтры, БПФ), в криптографических ускорителях и в нейросетевых вычислениях.

Теория кодирования

В теории кодирования модулярная арифметика используется при построении кодов, исправляющих ошибки. Например, коды Рида — Соломона (Reed–Solomon) основаны на операциях в полях Галуа \( GF(2^k) \), которые являются частным случаем модулярной арифметики по модулю неприводимого многочлена. Эти коды применяются в CD/DVD, QR-кодах, спутниковой связи и системах хранения данных.

Цифровая обработка сигналов

Модулярная арифметика позволяет реализовать быстрое преобразование Фурье (БПФ) с использованием китайской теоремы об остатках, что уменьшает количество операций и повышает точность вычислений. Также она используется в фильтрации и спектральном анализе.

Повседневные примеры

Часы: время вычисляется по модулю 12 или 24. Например, 14:00 — это 2 часа дня по модулю 12.
Календарь: дни недели повторяются по модулю 7.
Контрольные суммы: алгоритмы CRC (Cyclic Redundancy Check) основаны на делении многочленов по модулю 2, что является частным случаем модулярной арифметики в поле \( GF(2) \).

Обратные элементы и алгоритм Евклида

Нахождение обратного элемента по модулю \( m \) является ключевой операцией. Для взаимно простых \( a \) и \( m \) существует единственное \( x \), такое что \( a \cdot x \equiv 1 \pmod{m} \). Обратный элемент находится с помощью расширенного алгоритма Евклида. Этот алгоритм позволяет выразить наибольший общий делитель \( \gcd(a, m) = 1 \) в виде линейной комбинации: \( 1 = a \cdot u + m \cdot v \). Тогда \( u \) является обратным к \( a \) по модулю \( m \) (с точностью до знака). Если \( \gcd(a, m) \neq 1 \), обратный элемент не существует.

Модулярное возведение в степень

Возведение числа в большую степень по модулю — одна из важнейших операций в криптографии. Для эффективного вычисления \( a^b \pmod{m} \) используется алгоритм быстрого возведения в степень (бинарное возведение в степень). Он основан на разложении показателя \( b \) в двоичной системе и последовательном возведении в квадрат и умножении. Сложность алгоритма — \( O(\log b) \) операций умножения по модулю.