PricingLoginStart free
Cryptology Academy · Урок

Основы модульной арифметики

Разберитесь в арифметике часов и узнайте, почему она важна для криптографии

Урок 2 из 413 шагов

«Основы модульной арифметики» — бесплатный урок Cryptology Academy на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Cryptology Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Cryptology Academy содержит 4 уроков всего.

Добро пожаловать

Модульная арифметика, которую иногда называют «арифметикой часов», — математическая основа AES, RSA, Диффи — Хеллмана и почти любого современного шифра.

Что такое остаток от деления?

a mod m — это остаток, который получается при делении a на m. 17 mod 5 = 2 (поскольку 17 = 3×5 + 2). В Python: 17 % 5 == 2.

Интуиция арифметики часов

На 12-часовых часах 10 + 5 = 3, а не 15. Это арифметика по модулю 12. Модульная арифметика «зацикливается» при достижении модуля — именно это нужно для математических операций с шифрами.

Сложение и вычитание по модулю

(a + b) mod m = ((a mod m) + (b mod m)) mod m Пример: (19 + 23) mod 7 = (5 + 2) mod 7 = 7 mod 7 = 0

Умножение по модулю

(a × b) mod m = ((a mod m) × (b mod m)) mod m Пример: (13 × 17) mod 11 = (2 × 6) mod 11 = 12 mod 11 = 1

Возведение в степень по модулю

RSA использует a^b mod m. Для больших показателей степени применяется алгоритм возведения в квадрат и умножения: 2^10 mod 13: 2^2=4, 4^2=16≡3, 3^2=9, 9×2^2=9×4=36≡10. Python: pow(2, 10, 13) → 10

Обратный элемент по модулю

a^(-1) mod m — это такое значение x, что a×x ≡ 1 (mod m). Пример: 3^(-1) mod 7 = 5, поскольку 3×5=15≡1 (mod 7). Используется при расшифровке RSA и аффинного шифра.

Расширенный алгоритм Евклида

Расширенный алгоритм Евклида эффективно вычисляет обратные элементы по модулю. Python: pow(3, -1, 7) == 5 (Python 3.8+ поддерживает отрицательные показатели степени в pow).

Малая теорема Ферма

Если p — простое число: a^p ≡ a (mod p), поэтому a^(p-1) ≡ 1 (mod p). Это означает, что a^(-1) ≡ a^(p-2) (mod p). Используется при генерации ключей RSA и проверках простоты.

Китайская теорема об остатках (CRT)

CRT позволяет решать системы одновременных сравнений по модулю. При расшифровке RSA CRT ускоряет вычисления: сначала результаты вычисляются отдельно по модулям p и q, а затем объединяются.

Модульная арифметика в AES

AES работает в GF(2^8) — поле Галуа, где сложение выполняется с помощью XOR, а умножение — с помощью полиномиальной арифметики по модулю неприводимого многочлена. Вся арифметика AES является модульной.

Быстрая проверка

Чему равно pow(2, 10, 7) в Python?
Ответь в интерактивном уроке

Итоги

Вы освоили модульную арифметику! Далее мы изучим простые числа: почему они особенные и почему их разложение на множители лежит в основе безопасности RSA.
Можно начать бесплатно

Изучай Cryptology Academy с ИИ-репетитором — бесплатно

Пиши и запускай код прямо в браузере, получай мгновенную помощь от ИИ-репетитора 24/7 и продолжи учиться на сайте или в приложении.

Курсы
67
Уроки
261
Начать учиться бесплатноПосмотреть полный курс

Часто задаваемые вопросы

Урок «Основы модульной арифметики» бесплатный?

Да — полный текст урока «Основы модульной арифметики» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Cryptology Academy, подпишись на CoddyKit PRO. Курс Cryptology Academy содержит 4 уроков всего.

Чему я научусь в уроке «Основы модульной арифметики»?

Разберитесь в арифметике часов и узнайте, почему она важна для криптографии Ты практикуешь Cryptology Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Cryptology Academy?

Предыдущий опыт не требуется. Cryptology Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.

Сколько времени занимает урок «Основы модульной арифметики»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Cryptology Academy?

Да. Каждый урок Cryptology Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Основы двоичной и шестнадцатеричной систем
  2. Основы модульной арифметики
  3. Простые числа и факторизация
  4. GCD, функция Эйлера и введение в теорию чисел
← Назад к Cryptology Academy