Операция взятия остатка в информатике¶

Операция взятия остатка (от англ. modulo, сокращённо mod) — арифметическая операция, возвращающая остаток от деления одного числа на другое. В информатике она применяется повсеместно: от элементарной арифметики и хеширования до криптографии и компьютерной графики. Результат операции a mod n — это число r, такое что a = n · q + r, где q — целая часть от деления, а 0 ≤ r < |n|.

¶Математическое определение

Пусть a — делимое, n — делитель (модуль). Тогда:

`` a mod n = a − n · ⌊a / n⌋ ``

где ⌊·⌋ — функция округления вниз (флор). Для положительных a и n результат всегда лежит в диапазоне [0, n). Для отрицательных чисел существуют два подхода к определению остатка:

• Евклидов остаток — всегда неотрицателен: (−7) mod 3 = 2.
• Остаток по знаку делимого (используется в C, C++, Java, Python для оператора %): (−7) mod 3 = −1.

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

¶Операция mod в языках программирования

Большинство языков предоставляют оператор остатка. В C, C++, Java и C# это %, в Python — %, в Pascal — mod, в SQL и Haskell — тоже mod или rem. Семантика для отрицательных чисел отличается: C и производные языки возвращают остаток со знаком делимого, Python — всегда неотрицательный результат (при положительном модуле).

``python 7 % 3 # 1 -7 % 3 # 2 в Python, -1 в C 7 % -3 # -2 в Python ``

Отдельно существуют функции деления с остатком: divmod(a, n) в Python возвращает пару (частное, остаток), аналогично std::div в C.

¶Применение

¶Хеширование и таблицы рассеяния

Операция mod — основа вычисления индекса в хеш-таблице: index = hash(key) mod table_size. Выбор размера таблицы простым числом помогает распределить ключи равномернее. В стандартной библиотеке C++ (std::unordered_map) и в реализациях хеш-таблиц Java и Python mod используется именно так.

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

Модульная арифметика лежит в основе большинства криптосистем с открытым ключом. Алгоритм RSA использует возведение в степень по модулю: шифрование — это m^e mod n, расшифрование — c^d mod n, где n — произведение двух больших простых чисел. Эллиптическая криптография также оперирует координатами точек по модулю простого числа или над конечными полями. Для эффективного возведения в степень по модулю применяется алгоритм быстрого возведения в степень.

¶Компьютерная графика и игры

В графике mod применяется для создания бесшовных текстур и циклических анимаций: координата текстуры вычисляется как x mod texture_width, что обеспечивает «заворачивание» за границу. В процедурной генерации ландшафтов модульная арифметика используется для тайлинга шумов Перлина.

¶Циклические счётчики и таймеры

Часы с 12-часовым форматом используют mod 12 для преобразования 24-часового времени. Дни недели вычисляются как дата mod 7. Операция mod применяется в алгоритмах, работающих с кольцами целых чисел, например при вычислении индекса в кольцевом буфере (ring buffer): pos = (pos + 1) mod capacity.

¶Числовые методы и генераторы псевдослучайных чисел

Линейный конгруэнтный генератор (LCG) — один из старейших алгоритмов генерации псевдослучайных чисел — построен на mod:

`` X_{n+1} = (a · X_n + c) mod m ``

Такой генератор использовался в стандартной библиотеке C (rand()) и в ранних версиях Java (java.util.Random).

¶Вычислительная сложность

На современных процессорах операция целочисленного остатка выполняется за один-два такта (инструкции IDIV на x86, SDIV на ARM). Однако в криптографии, где модуль — число в сотни бит, mod выполняется специализированными алгоритмами: алгоритмом Монтгомери, алгоритмом Барретта или с помощью китайской теоремы об остатках. Эти методы позволяют заменить дорогие операции деления на умножения и сдвиги.

¶Связанные понятия

• Целочисленное деление — операция, возвращающая только частное; в паре с mod даёт полное разложение делимого.
• Кольцо вычетов — множество классов вычетов по модулю n, обозначается ℤ/nℤ; фундаментальная конструкция абстрактной алгебры, на которой строится вся модульная арифметика.
• Обратный элемент по модулю — число a⁻¹, такое что a · a⁻¹ ≡ 1 (mod n); существует тогда и только тогда, когда gcd(a, n) = 1. Находится расширенным алгоритмом Евклида и применяется в RSA для вычисления секретного ключа.

¶Историческая справка

Операция остатка известна с античности: она описана в «Началах» Евклида (около 300 года до н. э.) и в трудах индийских математиков, в частности у Ариабхаты (V век), использовавшего модульную арифметику для астрономических вычислей. Термин «modulo» в современном смысле ввёл Карл Фридрих Гаусс в работе «Арифметические исследования» (1801 году), заложивший основы теории чисел.

Источники:

• Гаусс К. Ф. «Арифметические исследования» (1801)
• Кормен Т., Лейзерсон Ч., Ривест Р., Штейн К. «Введение в алгоритмы»
• Седжвик Р., Уэйн К. «Алгоритмы на Java»
• Donald Knuth. «The Art of Computer Programming», Vol. 2: Seminumerical Algorithms
• cppreference.com — оператор %