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

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

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

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

\[ a \equiv b \pmod{m} \]

Например, \( 17 \equiv 5 \pmod{12} \), так как \( 17 - 5 = 12 \) делится на 12. Отношение сравнения является отношением эквивалентности на множестве целых чисел: оно рефлексивно, симметрично и транзитивно. Каждый класс эквивалентности, называемый классом вычетов по модулю \( m \), содержит все целые числа, дающие одинаковый остаток при делении на \( m \). Всего существует \( m \) различных классов вычетов: \( 0, 1, 2, \dots, m-1 \).

Множество классов вычетов по модулю \( m \) обозначается \( \mathbb{Z}_m \) или \( \mathbb{Z}/m\mathbb{Z} \). На этом множестве можно определить операции сложения, вычитания и умножения, которые наследуют свойства соответствующих операций над целыми числами, но выполняются по модулю \( 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 \equiv b \pmod{m} \), то \( a^k \equiv b^k \pmod{m} \) для любого натурального \( k \).
• Сокращение общего множителя возможно только если он взаимно прост с модулем: если \( a \cdot c \equiv b \cdot c \pmod{m} \) и \( \gcd(c, m) = 1 \), то \( a \equiv b \pmod{m} \).
• Если \( a \equiv b \pmod{m} \) и \( d \) — делитель \( m \), то \( a \equiv b \pmod{d} \).

Алгебраическая структура

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

Обратный элемент по модулю

Для числа \( a \), взаимно простого с модулем \( m \), существует единственное число \( x \) такое, что:

\[ a \cdot x \equiv 1 \pmod{m} \]

Это число называется обратным к \( a \) по модулю \( m \) и обозначается \( a^{-1} \mod m \). Его можно найти с помощью расширенного алгоритма Евклида.

Применение в криптографии

Модульная арифметика лежит в основе многих криптографических алгоритмов. Например, алгоритм RSA использует возведение в степень по модулю произведения двух больших простых чисел. В основе обмена ключами Диффи — Хеллмана лежит дискретное логарифмирование в конечном поле, которое также опирается на модульную арифметику.

Криптосистема RSA

В RSA выбираются два больших простых числа \( p \) и \( q \), вычисляется их произведение \( n = p \cdot q \). Функция Эйлера \( \varphi(n) = (p-1)(q-1) \). Выбирается открытая экспонента \( e \), взаимно простая с \( \varphi(n) \), и секретная экспонента \( d \) как обратный элемент к \( e \) по модулю \( \varphi(n) \). Шифрование сообщения \( M \) выполняется как \( C = M^e \mod n \), расшифрование — \( M = C^d \mod n \).

Применение в вычислительной технике

В компьютерах модульная арифметика используется для представления целых чисел с фиксированной разрядностью. Например, 8-битное беззнаковое целое число может принимать значения от 0 до 255, и операции над ним выполняются по модулю 256. Аналогично, знаковые числа в дополнительном коде также используют модульную арифметику.

Модульная арифметика применяется в алгоритмах хеширования, таких как MD5, SHA-1, SHA-2, где операции сложения и сдвига выполняются по модулю \( 2^{32} \) или \( 2^{64} \). В генераторах псевдослучайных чисел, например, линейном конгруэнтном методе, используется рекуррентная формула \( X_{n+1} = (a \cdot X_n + c) \mod m \).

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

Китайская теорема об остатках (КТО) утверждает, что если модули \( m_1, m_2, \dots, m_k \) попарно взаимно просты, то система сравнений:

\[ x \equiv a_1 \pmod{m_1}, \quad x \equiv a_2 \pmod{m_2}, \quad \dots, \quad x \equiv a_k \pmod{m_k} \]

имеет единственное решение по модулю \( M = m_1 \cdot m_2 \cdot \dots \cdot m_k \). КТО используется для ускорения вычислений с большими числами, разбивая их на несколько независимых вычислений по малым модулям.

Применение в теории кодирования

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

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

Для эффективного выполнения модульных операций существуют специальные алгоритмы. Быстрое возведение в степень по модулю (бинарное возведение в степень) позволяет вычислить \( a^b \mod m \) за \( O(\log b) \) операций. Алгоритм Монтгомери ускоряет умножение по модулю, заменяя деление на модуль более быстрыми операциями сдвига и сложения.

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

• Понятие сравнения по модулю впервые систематически изложил Карл Гаусс в 1801 году в книге «Арифметические исследования», которая заложила основы современной теории чисел.
• Модульная арифметика используется в повседневной жизни: например, часы работают по модулю 12 (или 24).
• В криптографии на эллиптических кривых арифметика выполняется в конечных полях, которые являются частным случаем модульной арифметики.
• В 1977 году Рональд Ривест, Ади Шамир и Леонард Адлеман опубликовали описание алгоритма RSA, который до сих пор широко используется для шифрования и цифровых подписей.

Источники

• Гаусс К. Ф. Арифметические исследования. — 1801.
• Виноградов И. М. Основы теории чисел. — М.: Наука, 1972.
• Шнайер Б. Прикладная криптография. — М.: Триумф, 2002.
• Кнут Д. Э. Искусство программирования. Том 2. Получисленные алгоритмы. — М.: Вильямс, 2007.
• Лидл Р., Нидеррайтер Г. Конечные поля. — М.: Мир, 1988.