| Остаток r | Частное q | Множитель t |
|---|
Модульные часы
Через пять часов после 9 часов будет 2 часа, потому что 9 + 5 = 14, а 14 на 2 больше 12. Это и есть модульная арифметика: счёт на циферблате, который после n снова начинается с 0. Выберите операцию, введите n, a и b, и калькулятор выдаст ответ с подробной записью каждого шага — от остатка от деления до повторного возведения в квадрат и расширенного алгоритма Евклида, а циферблат покажет, как получается ответ. Выберите операцию, затем введите модуль n и числа a и b; подходят целые числа длиной до 30 цифр, в том числе отрицательные, а n может быть до 10^18. На циферблате n позиций, 0 вверху, а стрелка указывает на ответ. Сложение и вычитание рисуются как спираль из b шагов, по одному витку на каждый полный оборот; умножение — как прыжки по a; степени — как хорды a, a², a³ …, которые замыкаются в цикл; обратный элемент и деление — как кратные, попадающие на 1 или на a. Шаги показывают то же вычисление в числах. До mod 20 показывается таблица операции; щёлкните по клетке, чтобы взять её числа. Кнопка «Пример» подставляет классическую задачу.
Как это работает
- Выберите операцию: a mod n, сложение, вычитание, умножение, деление, степень или обратный к a.
- Введите модуль n и числа a и b или выберите пример, например последнюю цифру 7^2026 или небольшое сообщение RSA.
- Прочитайте ответ и шаги, проследите путь на циферблате, а до mod 20 щёлкните по клетке таблицы, чтобы попробовать её числа.
Что означает a mod n
a mod n — это остаток от деления a на n: 17 mod 5 = 2, потому что 17 = 3 × 5 + 2. Остаток всегда находится в пределах от 0 до n − 1, в том числе для отрицательных чисел: −7 mod 3 = 2, потому что −7 = −3 × 3 + 2. На циферблате это означает пройти 7 шагов назад от 0. Два числа с одинаковым остатком сравнимы по модулю, что записывается как 17 ≡ 2 (mod 5); это обозначение ввёл Карл Фридрих Гаусс в 1801 году. Суммы, разности и произведения можно приводить по модулю n на любом шаге, и числа остаются небольшими.
Где применяется модульная арифметика
Часы и календари работают по модулю 12, 24 и 7: через 100 дней после среды наступит пятница, потому что 100 mod 7 = 2. Контрольные цифры используют её, чтобы ловить опечатки, — от номеров ISBN-10 (mod 11) до номеров банковских карт (mod 10) и IBAN (mod 97). Шифры сдвигают буквы по модулю 26, а для расшифровки аффинного шифра нужен обратный элемент по модулю 26. RSA, защищающий значительную часть интернета, шифрует сообщение m как m^e mod n и расшифровывает другой степенью: при n = 3233 получаем 65^17 mod 3233 = 2790 и 2790^413 mod 3233 = 65.
Часто задаваемые вопросы
Как вычислить a mod n для отрицательного числа?
Прибавляйте или вычитайте кратные n, пока число не окажется в пределах от 0 до n − 1. Для −7 mod 3: −7 + 9 = 2, значит, ответ 2. Некоторые языки программирования вместо этого дают −1 для −7 % 3, потому что округляют частное к нулю; в математике остаток никогда не бывает отрицательным.
Что такое обратный элемент по модулю?
Обратный к a по модулю n — это число x, для которого a × x ≡ 1 (mod n). Обратный к 7 по модулю 26 равен 15, потому что 7 × 15 = 105 = 4 × 26 + 1. Он существует, только если у a и n нет общих делителей, и находится расширенным алгоритмом Евклида. Делить на a по модулю n — значит умножать на обратный к нему элемент.
Как вычислить по модулю n степень вроде 7^2026?
Методом повторного возведения в квадрат: возводите 7 в квадрат снова и снова, каждый раз приводя по модулю n, чтобы получить 7^1, 7^2, 7^4, 7^8 и так далее, а затем перемножьте те из них, которые составляют 2026 в двоичной записи. Для этого нужно 10 возведений в квадрат и 7 умножений вместо 2 025 умножений, и числа никогда не превышают n². 7^2026 оканчивается на 9.
Почему на циферблате 0, а не 12?
В модульной арифметике остатки идут от 0 до n − 1, поэтому на циферблате с 12 позициями полдень — это 0. 12 ≡ 0 (mod 12); обычные часы просто пишут 12 там, где математика пишет 0.
Насколько большими могут быть числа?
a и b могут содержать до 30 цифр и быть отрицательными, а модуль может быть до 10^18. Калькулятор работает с точными целыми числами прямо в вашем браузере, поэтому даже примеры размера RSA дают точные ответы, и никакие данные никуда не отправляются.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор