Арифметика часов: как работает модулярная математика в хешах и не только

Часы — это калькулятор, который умеет считать только до двенадцати, а потом начинает сначала. Именно так считают компьютеры в самых важных местах.

Модулярная арифметика — это математика, которая ходит по кругу. И этот круг оказался невероятно полезным.

Спросите ребёнка: «Сейчас 10 утра, что будет через 5 часов?» Он ответит «3 часа дня», а не «15 утра». Сам того не зная, он только что выполнил вычисление по модулю 12. Эта повседневная интуиция — основа целой ветви математики, без которой не работал бы ни один современный компьютер.

Что значит «по модулю»

Записать $a \bmod m$ — значит взять остаток от деления $a$ на $m$. Часы живут по модулю $12$ (или $24$), дни недели — по модулю $7$, а минуты и секунды — по модулю $60$. Формально два числа «равны по модулю $m$», если дают одинаковый остаток:

$$17 \equiv 5 \pmod{12}$$

потому что и $17$, и $5$ при делении на $12$ оставляют один остаток. Мир остатков замкнут: сколько ни прибавляй, ты всегда остаёшься внутри круга от $0$ до $m-1$.

Хеш-таблицы: как мгновенно найти нужное

Представьте библиотеку, где книгу можно достать за одно движение, не перебирая полки. Так работает хеш-таблица — структура данных, лежащая в основе словарей почти во всех языках программирования.

Идея проста: у нас есть массив из $m$ ячеек. Чтобы решить, в какую ячейку положить значение по ключу, ключ превращают в число и берут остаток по модулю $m$:

$$\text{ячейка} = \text{hash}(\text{ключ}) \bmod m$$

Остаток от деления гарантированно попадает в диапазон от $0$ до $m-1$ — то есть всегда указывает на существующую ячейку. Поэтому поиск, вставка и удаление происходят почти мгновенно, не зависят от размера данных.

Когда двое метят в одну ячейку

Иногда разные ключи дают один остаток — это коллизия. С ней борются, например, складывая «спорщиков» в список внутри ячейки. Хороший выбор модуля $m$ (часто простое число) делает коллизии редкими, равномерно «размазывая» ключи по таблице.

Контрольные суммы и хеши

Когда вы скачиваете файл, рядом часто публикуют контрольную сумму. Это число, полученное прогоном данных через хеш-функцию, в сердце которой — всё те же операции по модулю. Если хоть один бит файла исказился, остаток изменится, и несовпадение выдаст повреждение.

Почему это любят шифры

В криптографии операции по модулю обладают волшебным свойством: их легко вычислить вперёд, но трудно обратить. Возвести число в степень по большому модулю — секундное дело. А вот восстановить исходную степень по результату (задача дискретного логарифма) — задача, на которой держится защита переписки. Круговая арифметика прячет следы.

Простая идея с огромными последствиями

От детского вопроса про часы до защиты банковских транзакций — всё это одна и та же математика остатков. Она элегантна тем, что превращает бесконечную числовую прямую в аккуратный замкнутый круг, внутри которого компьютеру удобно и быстро жить. В следующий раз, глядя на циферблат, помните: вы смотрите на фундамент цифровой эпохи.