Что такое модульная арифметика
Модульной арифметикой занимаются все: через 10 часов после 8 часов будет 6 часов, а после воскресенья наступает понедельник. Оказывается, у счёта, который после n шагов снова начинается с 0, есть своя полноценная арифметика — со своими правилами, неожиданностями и центральным местом в теории чисел и в криптографии, которая защищает интернет.
Остатки и сравнения по модулю
Разделите a на n и оставьте только остаток: это a mod n, число от 0 до n − 1. 26 mod 7 = 5, потому что 26 = 3 × 7 + 5. Числа с одинаковым остатком ведут себя по модулю n одинаково, поэтому их называют сравнимыми: 26 ≡ 5 ≡ −2 (mod 7). Карл Фридрих Гаусс ввёл это обозначение в своём труде Disquisitiones Arithmeticae («Арифметические исследования») 1801 года, и оно превратило давние наблюдения Ферма и Эйлера в самостоятельную арифметику. На циферблате с n позициями каждое целое число попадает на свой остаток; полные обороты забываются.
Сложение, вычитание и умножение
Три обычные операции работают как всегда, и приводить по модулю n можно когда угодно: остаток суммы равен остатку суммы остатков, и то же верно для разностей и произведений. Чтобы найти последнюю цифру 37 × 48, перемножьте только последние цифры: 7 × 8 = 56, значит, произведение оканчивается на 6. Именно это делает модульную арифметику такой полезной для компьютеров: какими бы большими ни были числа, промежуточные значения никогда не превышают n².
Для деления нужен обратный элемент
Деление — исключение. 2 × 3 ≡ 2 × 8 (mod 10), так как оба произведения дают 6 по модулю 10, но 3 и 8 различны, поэтому просто сократить на 2 нельзя. Делить на a — значит умножать на обратный к нему элемент, число x, для которого a × x ≡ 1, и он существует ровно тогда, когда у a и n нет общих делителей. Его находит расширенный алгоритм Евклида: он выполняет шаги деления Евклида для поиска наибольшего общего делителя и на каждом шаге отслеживает множитель, так что, когда остаток доходит до 1, множитель и есть обратный элемент. Если n простое, обратный элемент есть у каждого числа, кроме 0, и деление всегда возможно.
Степени, Ферма и Эйлер
Степени повторяются. Возьмите степени 3 по модулю 7: 3, 2, 6, 4, 5, 1, а затем снова 3. Длина этого цикла — порядок числа 3. В 1640 году Пьер де Ферма заметил, что для простого p выполняется a^(p − 1) ≡ 1 (mod p), если p не делит a, поэтому любой порядок делит p − 1. Леонард Эйлер доказал это и обобщил на любое n, заменив p − 1 количеством значений, взаимно простых с n. Огромные степени вычисляют методом повторного возведения в квадрат: a, a², a⁴, a⁸ … — каждая равна квадрату предыдущей, приведённому по модулю n, — а затем перемножают те из них, что соответствуют двоичным цифрам показателя.
Контрольные цифры и календари
Модульная арифметика ловит ошибки. Последнюю цифру ISBN-10 выбирают так, чтобы взвешенная сумма всех десяти цифр делилась на 11, поэтому обнаруживается любая одиночная неверная цифра и любая перестановка двух соседних цифр. Номера банковских карт используют проверку Luhn по модулю 10, а IBAN — проверку по модулю 97. Календари работают по модулю 7: день недели любой даты можно вычислить с помощью нескольких остатков — так устроены вечные календари и правило «судного дня».
Криптография
Современная криптография построена на модульных степенях, которые легко вычислить и трудно обратить. В протоколе обмена ключами Диффи — Хеллмана 1976 года два человека договариваются об общем секрете по открытому каналу, обмениваясь степенями по модулю большого простого числа. RSA, опубликованный в 1977 году Ривестом, Шамиром и Адлеманом, шифрует сообщение m как m^e mod n, где n — произведение двух больших простых чисел, а расшифровывает вторым показателем d, который может вычислить только тот, кто знает эти два простых числа. В учебном примере n = 3233 = 61 × 53, e = 17 и d = 413: 65 превращается в 2790, а 2790 — снова в 65.
Попробуйте сами
Откройте модульные часы, чтобы вычислять a mod n, а также суммы, разности, произведения, степени, обратные элементы и частные по модулю n для чисел длиной до 30 цифр. Каждый ответ сопровождается шагами: деление с остатком, степени из повторного возведения в квадрат или таблица расширенного алгоритма Евклида. Циферблат рисует, как получается ответ, — от спирали сложения до цикла степеней, а для небольших n таблица операции показывает сразу все ответы.
Часто задаваемые вопросы
Что означает символ ≡?
a ≡ b (mod n) означает, что a и b дают одинаковый остаток при делении на n, или, что то же самое, что n делит a − b. 38 ≡ 2 (mod 12), потому что 38 − 2 = 36 кратно 12.
mod — это то же самое, что оператор % в программировании?
Для положительных чисел — да. Для отрицательных чисел многие языки, например C, Java и JavaScript, возвращают отрицательный остаток: там −7 % 3 равно −1, тогда как −7 mod 3 = 2. Оператор % в Python следует математическому соглашению при положительном n.
Что такое порядок числа по модулю n?
Наименьшее k > 0, при котором a^k ≡ 1 (mod n). Он существует, только если у a и n нет общих делителей. Порядок 2 по модулю 7 равен 3, потому что 2³ = 8 ≡ 1, а порядок 3 по модулю 7 равен 6, поэтому степени 3 пробегают все ненулевые остатки: 3 — первообразный корень по модулю 7.
Кто придумал модульную арифметику?
Остатками пользовались задолго до этого, например в китайской теореме об остатках, относящейся к III–V векам, а также Ферма и Эйлер. Гаусс превратил её в систематическую арифметику с обозначением сравнений в 1801 году.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Открыть модульные часы