В лекции MIT OpenCourseWare профессор Анкур Мойтра раскрывает фундаментальные принципы модульной арифметики и её неожиданные применения в современных компьютерных науках. Отталкиваясь от привычных школьных правил деления, спикер демонстрирует, как «часовая математика» обеспечивает безопасность в криптографии и эффективность при передаче данных. Основной сюжет занятия строится вокруг алгоритмов поиска наибольшего общего делителя, доказательства ключевых теорем теории чисел и разбора концепций с нулевым разглашением.
⏰ Что такое модульная арифметика и «часовая математика» 0:00
Модульную арифметику проще всего определить как математику взаимосвязей между числами. Некоторые базовые проявления этой системы знакомы каждому со времён начальной школы. Например, всем известно, что сложение чётного и нечётного чисел всегда даёт нечётный результат, а сумма двух чётных чисел всегда чётна. Профессор Анкур Мойтра подчёркивает, что эти элементарные правила представляют собой не что иное, как арифметику по модулю 2.
Суть данного подхода заключается в том, что при вычислениях учитываются исключительно остатки, получаемые при делении на заданное число. Для формализации этого принципа вводится базовое математическое определение. Два целых числа $a$ и $b$ называются сравнимыми по модулю $n$, если их разность делится на $n$ без остатка. Математически это записывается в виде выражения:
$$a \equiv b \pmod n$$
В повседневной жизни модульную арифметику часто называют «часовой математикой». Если представить циферблат часов, то числа в такой системе ведут себя циклично. Главным инструментом для работы с остатками выступает классический алгоритм деления (следствие деления «уголком»). Согласно этому правилу, для любого целого числа $a$ и строго положительного делителя $n$ существует единственная пара целых чисел $q$ (частное) и $r$ (остаток), удовлетворяющая равенству:
$$a = qn + r$$
При этом остаток $r$ строго ограничен: он должен быть не меньше 0 и строго меньше делителя $n$, то есть находиться в диапазоне от 0 до $n - 1$. Это базовое ограничение помогает структурировать вычисления и переходить от бесконечного ряда целых чисел к конечному набору остатков.
📜 Ключевая лемма и правила умножения по модулю 4:31
Для полноценного использования модульной арифметики необходимо доказать важную лемму. Утверждение гласит, что выражение $a \equiv b \pmod n$ истинно тогда и только тогда, когда остаток от деления $a$ на $n$ в точности равен остатку от деления $b$ на $n$. Профессор Мойтра предлагает разобрать доказательство этой эквивалентности в обоих направлениях, чтобы продемонстрировать строгость математического аппарата.
Сначала доказывается обратное утверждение. Если предположить, что остатки равны, то числа можно представить в виде:
$$a = qn + r$$ $$b = q'n + r$$
При вычитании одного уравнения из другого остатки $r$ взаимно уничтожаются. В результате получается выражение $a - b = (q - q')n$. Поскольку разность частных $(q - q')$ является целым числом, разность $a - b$ оказывается кратна $n$, что полностью соответствует определению сравнимости по модулю.
Прямое утверждение доказывается аналогично, методом от противного. Предполагается, что $a$ и $b$ сравнимы, но имеют разные остатки $r$ и $r'$. Разность чисел приобретает вид:
$$a - b = (q - q')n + (r - r')$$
Поскольку $a - b$ делится на $n$, выражение $(r - r')$ также должно делиться на $n$. Однако разность двух остатков, каждый из которых строго меньше $n$, физически может находиться только в строгом интервале от $-n$ до $n$. Единственным числом в этом промежутке, которое делится на $n$, является 0. Следовательно, $r - r' = 0$, и остатки совпадают.
Визуализировать эту концепцию можно с помощью круга, напоминающего циферблат. Например, если расположить на окружности числа от 0 до 6 (модуль 7), то числа 5 и 12 попадут в одну и ту же точку. Число 12 делает один полный оборот вокруг воображаемых часов и останавливается на отметке 5. В модульной арифметике такие числа не различаются и относятся к одному классу эквивалентности.
Операции сложения и умножения по модулю выполняются стандартным образом. Например, если необходимо перемножить числа 10 (сравнимое с 3 по модулю 7) и 12 (сравнимое с 5 по модулю 7), можно пойти двумя путями:
- Перемножить исходные числа: $10 \times 12 = 120$. Затем убрать лишние кратные модуля 7 ($120 - 7 \times 17 = 120 - 119 = 1$), получив остаток 1.
- Перемножить их остатки: $3 \times 5 = 15$. Из полученного результата вычесть ближайшее кратное семи ($15 - 14 = 1$), что также даёт остаток 1.
Таким образом, для выполнения арифметических действий реальные значения чисел не имеют значения — важны только их остатки по заданному модулю. Алгебраическую структуру множества остатков по модулю 7 (обозначаемую как $\mathbb{Z}_7$) можно представить в виде таблиц сложения и умножения. В этой структуре сохраняются все привычные свойства обычной арифметики:
- Ассоциативность: $(a + b) + c = a + (b + c)$
- Коммутативность: $a + b = b + a$
- Дистрибутивность: $a \times (b + c) = a \times b + a \times c$
🔒 Криптография и доказательства с нулевым разглашением 18:08
Модульная арифметика служит фундаментом для многих разделов компьютерных наук, включая криптографию. Одним из самых ярких и весёлых примеров её применения являются протоколы доказательства с нулевым разглашением (Zero-Knowledge Proofs), концепция которых была разработана именно в Массачусетском технологическом институте (MIT).
Чтобы объяснить суть протокола доступным языком, профессор разыгрывает интерактивную сцену с аудиторией. Представьте ситуацию: двое друзей хотят посмотреть в выходные какой-нибудь «постыдный» фильм (в качестве примера студенты выбрали киноленту «Морбиус», отметив, что она настолько плоха, что стала культовой). Никто из друзей не хочет открыто признаваться в симпатии к этому фильму, опасаясь насмешек в случае несовпадения вкусов. Им нужен способ узнать, взаимен ли их интерес, сохранив при этом «правдоподобное отрицание» на случай отказа.
Для решения этой задачи Анкур Мойтра использует колоду из пяти карт, в которой три карты имеют красную рубашку (или масть), а две — чёрную. Профессор раздаёт двум добровольцам из зала по одной чёрной и одной красной карте, а оставшуюся красную карту кладёт по центру стола. Правила игры следующие:
- Если участник хочет посмотреть фильм, он кладёт свою красную карту ближе к центральной красной карте, а чёрную — скраю.
- Если участник против просмотра, он кладёт к центру чёрную карту, а красную смещает на внешний край.
После того как карты выложены рубашкой вверх, профессор собирает их в единую стопку и просит каждого участника случайно «сдвинуть» (снять) колоду несколько раз. Этот циклический сдвиг аналогичен вращению стрелки на часах. Если оба студента ответили согласием, то в замкнутом цикле окажутся три красные карты подряд. Если хотя бы один ответил отказом, конфигурация изменится, и подряд будут идти максимум две красные карты.
В ходе демонстрации на лекции совпадения не произошло. При вскрытии карт выяснилось, что один студент ответил «да», а второй — «нет». Однако благодаря случайному циклическому сдвигу колоды никто не может определить, кто именно высказался против. Отказавшийся участник сохранил лицо, а механика «часового» смещения обеспечила полную конфиденциальность данных.
🔄 Поиск мультипликативных обратных элементов 23:39
Переходя к более сложным структурам, профессор Мойтра ставит перед аудиторией ключевой вопрос: всегда ли в модульной арифметике для каждого элемента существует мультипликативный обратный элемент?. В обычной математике обратным для числа $x$ является $1/x$, поскольку их произведение равно 1. По модулю $n$ мультипликативным обратным для числа $a$ называется такое число $s$, что их произведение сравнимо с единицей:
$$a \times s \equiv 1 \pmod n$$
Например, если рассматривать вычисления по модулю 7, то для числа 2 обратным элементом будет 4, так как $2 \times 4 = 8 \equiv 1 \pmod 7$. Соответственно, для 4 обратным элементом будет 2. Аналогично, обратным для числа 5 является 3, поскольку $5 \times 3 = 15 \equiv 1 \pmod 7$. Наличие таких пар критически важно для криптографии, где умножение на число используется для «запутывания» (шифрования) секретного сообщения, а умножение на обратный элемент — для его последующего «распутывания» (дешифрования).
Для небольших модулей (например, 7) можно составить полную таблицу умножения и найти единицы в каждой строке. Но если модуль представляет собой гигантское 32-значное число, ручной перебор становится невозможным. Возникает необходимость в математической теории, которая гарантирует существование обратного элемента и указывает эффективный способ его поиска.
Для формулирования этой теории вводится понятие наибольшего общего делителя (НОД) — максимального целого числа, на которое без остатка делятся оба заданных числа $a$ и $b$. Простой и неэффективный способ вычисления НОД заключается в переборе всех чисел от 1 до меньшего из аргументов, однако компьютерные системы древности и современности опираются на гораздо более быстрый метод — алгоритм Евклида.
🧮 Алгоритм Евклида и его расширенная версия 29:54
В основе алгоритма Евклида лежат две структурные леммы. Первая лемма утверждает: если число $b$ больше или равно $a$, то наибольший общий делитель пары $(a, b)$ в точности равен наибольшему общему делителю пары $(a, b - a)$.
Доказательство строится на очевидном факте: если целое число $k$ делит $a$ и делит $b$, то оно обязано делить и их разность $(b - a)$. Из этого логически следует, что любой общий делитель первой пары является делителем и для второй пары, а значит, $\gcd(a, b) \le \gcd(a, b - a)$. Проведя аналогичные рассуждения в обратную сторону (ведь $b = (b - a) + a$), математики получают зеркальное неравенство $\gcd(a, b - a) \le \gcd(a, b)$, что доказывает их полное равенство.
Вторая лемма предлагает сделать качественный шаг вперёд: вместо последовательного вычитания одного числа из другого можно сразу перейти к делению с остатком. Математически это записывается как:
$$\gcd(a, b) = \gcd(a, b \pmod a)$$
Профессор поясняет, что этот шаг представляет собой просто многократное применение первой леммы. Вместо того чтобы отнимать число $a$ по одному разу, мы за один шаг вычитаем сразу $q$ копий числа $a$, сокращая вычисления до минимума. Это даёт колоссальное ускорение: если числа близки, шаг деления мгновенно уменьшает их значения, а если далеки — большее число резко сокращается до размеров остатка.
В качестве живого примера на доске рассчитывается НОД для чисел 46 и 360:
- $\gcd(46, 360)$ превращается в $\gcd(46, 38)$, так как $360 \pmod{46} = 38$.
- $\gcd(46, 38)$ превращается в $\gcd(8, 38)$, так как $46 \pmod{38} = 8$.
- $\gcd(8, 38)$ превращается в $\gcd(8, 6)$, так как $38 \pmod 8 = 6$.
- $\gcd(8, 6)$ превращается в $\gcd(2, 6)$, так как $8 \pmod 6 = 2$.
- $\gcd(2, 6)$ превращается в $\gcd(2, 0)$, поскольку 6 делится на 2 без остатка.
Алгоритм останавливается, выдавая ответ 2. Чтобы связать этот процесс с поиском обратных элементов, необходимо использовать расширенный алгоритм Евклида. Его суть заключается в ведении дополнительного учёта: на каждом шаге деления математики записывают, какое именно кратное числа было вычтено, выражая промежуточные остатки через линейную комбинацию исходных чисел.
В конечном итоге расширенный алгоритм позволяет найти такие целые коэффициенты $s$ и $t$, при которых выполняется тождество Безу (лемма 3):
$$sa + tb = \gcd(a, b)$$
Данное выражение служит неопровержимым «сертификатом» правильности ответа. Если бы существовал некий делитель $K$, который больше полученного значения НОД, то при делении левой части уравнения на $K$ должно было получиться целое число, однако правая часть равенства сделала бы это невозможным.
Связь с мультипликативным обратным элементом становится очевидной, если рассмотреть пример с числом 4 по модулю 7. Поскольку 7 — простое число, их НОД равен 1. Расширенный алгоритм Евклида позволяет найти коэффициенты для уравнения $4s + 7t = 1$. Если взять это выражение по модулю 7, слагаемое $7t$ обнулится, и мы получим $4s \equiv 1 \pmod 7$. Число $s$ и будет искомым обратным элементом. Данное правило гарантирует: любой элемент имеет мультипликативный обратный элемент тогда и только тогда, когда он взаимно прост с модулем вычислений.
🪙 Загадка о золотых монетах и Китайская теорема об остатках 54:20
В финальной части лекции профессор Мойтра предлагает студентам старинную математическую загадку. Представьте сундук с сокровищами, доверху наполненный золотыми монетами. Известно два факта:
- Если разделить все монеты на группы по 5 штук, то в остатке останется 4 монеты.
- Если же разделить эти монеты на группы по 7 штук, то лишней останется всего 1 монета.
Перед аудиторией ставится задача найти наименьшее возможное количество монет в сундуке. В терминах модульной арифметики эта загадка формулируется как система из двух уравнений с неизвестным числом $n$:
$$n \equiv 4 \pmod 5$$ $$n \equiv 1 \pmod 7$$
Путём несложного подбора можно быстро найти ответ — 29 монет. Однако за этой простой задачей скрывается один из древнейших математических законов — Китайская теорема об остатках, впервые сформулированная китайским математиком Сунь Цзы Суанем в IV веке нашей эры.
Теорема строго утверждает: если числа $a$ и $b$ взаимно просты (их НОД равен 1), то для любых заданных остатков $r$ и $s$ система уравнений имеет ровно одно уникальное решение в диапазоне от 0 до $a \times b - 1$. Между целыми числами из этого интервала и парами возможных остатков существует взаимно однозначное соответствие — биекция. Это можно представить в виде двудольного графа, где каждое число соединено ровно с одной парой остатков.
Доказательство теоремы проводится методом от противного. Предположим, что существуют два разных решения, $x$ и $y$, лежащих в указанном диапазоне, остатки которых совпадают. В таком случае разность $(x - y)$ должна одновременно делиться и на $a$, и на $b$. Поскольку $a$ и $b$ взаимно просты, их произведение $(a \times b)$ также обязано делить разность $(x - y)$. Однако два различных числа, находящихся в границах от 0 до $a \times b - 1$, физически не могут отличаться друг от друга на величину, равную или превышающую их произведение. Полученное противоречие полностью доказывает истинность теоремы.
Для нахождения решения системы уравнений в общем виде применяется пошаговая алгебраическая процедура. Сначала неизвестное число записывается через его деление на один из модулей: $n = kb + t$. Затем к обеим частям равенства применяется операция взятия остатка по второму модулю $a$:
$$kb + t \equiv s \pmod a$$
Путём несложного переноса слагаемых выражение преобразуется к виду $kb \equiv s - t \pmod a$. Чтобы изолировать неизвестную переменную $k$, обе части уравнения умножаются на мультипликативный обратный элемент для $b$ по модулю $a$ (существование которого гарантировано взаимной простотой чисел). Итоговая формула для вычисления коэффициента приобретает законченный вид:
$$k \equiv b^{-1}(s - t) \pmod a$$
📡 Фонтанные коды и раздача контента 1:14:08
В завершение занятия профессор приводит пример практического использования Китайской теоремы об остатках в современных интернет-технологиях, а именно в концепции фонтанных кодов (Fountain Codes), применяемых для стриминга данных.
Представьте огромный файл, содержание которого можно закодировать в виде одного колоссального целого числа $n$. Этот файл одновременно пытаются скачать или посмотреть в режиме онлайн тысячи пользователей (например, в момент выхода нового сезона популярного сериала). Вместо того чтобы отправлять каждому пользователю копию файла целиком, сервер начинает непрерывно транслировать в сеть бесконечный поток маленьких фрагментов — остатков от деления числа $n$ на различные простые числа $a_i$.
Пользовательские устройства улавливают эти сообщения из сети. Согласно принципам Китайской теоремы об остатках, как только устройство соберёт достаточное количество фрагментов, произведение модулей $\prod a_i$ которых превысит размер исходного файла $n$, оно сможет мгновенно восстановить исходный файл целиком.
Этот подход метафорически сравнивается с питьевым фонтанчиком, который непрерывно разбрызгивает капли воды во всех направлениях. Любому человеку достаточно подойти со своей бутылкой и дождаться, пока она наполнится до краёв. При этом абсолютно неважно, какие именно капли попали в бутылку. Точно так же устройствам пользователей при скачивании файла не нужно запрашивать конкретные недостающие пакеты данных — им достаточно набрать любой необходимый объём уникальных остатков из общего потока, чтобы полностью восстановить цифровую информацию.
