Калькулятор модульной арифметики

Q: Что такое модульная арифметика простыми словами?

Это арифметика с «оборачиванием». Представьте часы: после 12 идёт снова 1. Точно так же в модульной арифметике после достижения модуля m числа начинают считаться заново. Например, 15 mod 12 = 3 (15 часов = 3 часа дня).

Q: Зачем нужен обратный элемент по модулю?

Обратный элемент — это аналог деления в модульной арифметике. Поскольку обычное деление не определено для остатков, вместо a/b mod m мы вычисляем a * b^(-1) mod m. Это критически важно для RSA-дешифрования и решения линейных сравнений.

Q: Почему обратный элемент не всегда существует?

Обратный элемент a^(-1) mod m существует тогда и только тогда, когда gcd(a, m) = 1, то есть числа взаимно просты. Например, 4^(-1) mod 6 не существует, потому что gcd(4, 6) = 2 ≠ 1.

Q: Что такое Китайская теорема об остатках?

КТО утверждает, что система сравнений x ≡ a_i (mod m_i) с попарно взаимно простыми модулями имеет единственное решение по модулю M = m_1 × m_2 × ... × m_k. Это позволяет разбивать вычисления с большими числами на параллельные вычисления с малыми модулями.

Q: Насколько надёжен тест Миллера-Рабина?

Вероятностный тест Миллера-Рабина с k раундами даёт вероятность ошибки не более 4^(-k). При 20 раундах вероятность ложного срабатывания менее 10^(-12). Для чисел до ~82 бит калькулятор использует детерминистический вариант с гарантированно верным результатом.

Q: Поддерживает ли калькулятор очень большие числа?

Да. Калькулятор использует JavaScript BigInt, что позволяет работать с целыми числами произвольной длины без потери точности. Вы можете вводить числа длиной в сотни цифр. Все вычисления выполняются в вашем браузере.

Q: Как быстрое возведение в степень ускоряет вычисления?

Вместо b умножений (наивный подход), алгоритм бинарного возведения выполняет всего log₂(b) умножений. Для b = 10^18 это разница между 10^18 операций (невозможно) и ~60 операций (мгновенно).

Q: Где применяется модульная арифметика в реальной жизни?

Проверка банковских карт (алгоритм Луна), контрольные суммы ISBN, штрих-кодов и паспортов, шифрование HTTPS (RSA, Диффи-Хеллман), блокчейн, хеш-таблицы в базах данных, расчёт дней недели, генераторы случайных чисел.

Q: Чем отличается расширенный алгоритм Евклида от обычного?

Обычный алгоритм Евклида находит только НОД(a, b). Расширенный дополнительно находит коэффициенты Безу x и y такие, что ax + by = gcd(a, b). Именно это позволяет вычислить обратный элемент по модулю.

Q: Безопасно ли использовать этот калькулятор?

Все вычисления выполняются исключительно в вашем браузере (client-side). Никакие данные не отправляются на сервер. Это означает полную конфиденциальность ваших расчётов. Однако для реальных криптографических задач рекомендуется использовать специализированные библиотеки с защитой от атак по побочным каналам.

Сложение, вычитание, умножение и возведение в степень по модулю. Обратный элемент, китайская теорема об остатках, тест простоты Миллера-Рабина. Поддержка произвольно больших чисел через BigInt.

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

Число a

Число b

Модуль m

Операция

BigInt поддержкаПроизвольная точностьПошаговое решениеВсе вычисления в браузере

Загрузка калькулятора...

Операций

Полный набор инструментов

BigInt

Поддержка

Произвольная точность

a⁻¹

Обратный элемент

Расширенный Евклид

φ(n)

Теорема Ферма

Эйлер и Ферма

Теория и определения

Что такое модульная арифметика?

Модульная арифметика — система вычислений, в которой числа «оборачиваются» после достижения определённого значения (модуля). Аналогия: часы работают по модулю 12 — после 12 счёт начинается заново.

a mod m = r, где 0 ≤ r < m

≡

Сравнения по модулю

Два числа a и b сравнимы по модулю m (пишется a ≡ b (mod m)), если их разность делится на m. Это отношение эквивалентности, разбивающее все целые числа на m классов вычетов.

a ≡ b (mod m) ⇔ m | (a - b)

∞

Применения

Модульная арифметика — фундамент криптографии (RSA, Диффи-Хеллман), хеш-функций, контрольных сумм (ISBN, банковские карты), коррекции ошибок, генерации псевдослучайных чисел и теории кодирования.

RSA, хеширование, CRC, Luhn, ECC

Где это используется?

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

🔐

Криптография RSA

Шифрование с открытым ключом основано на возведении в степень по модулю произведения двух больших простых чисел. Безопасность RSA опирается на сложность факторизации.

#️⃣

Хеш-функции

Хеширование данных использует операции mod для отображения входа произвольного размера в фиксированный диапазон. Применяется в хеш-таблицах, проверке целостности, blockchain.

✓

Контрольные цифры

Алгоритм Луна (банковские карты), ISBN, ИНН, штрих-коды, СНИЛС — все проверяют корректность с помощью остатка от деления.

🔄

Циклические структуры

Кольцевые буферы, round-robin планировщики, карусели в UI, дни недели — любая циклическая структура работает через mod.

📅

Расписания и календари

Определение дня недели, расчёт високосных годов, периодические задачи (cron), расписание смен — всё это модульная арифметика в быту.

🔢

Теория чисел

Малая теорема Ферма, теорема Эйлера, квадратичные вычеты, символ Лежандра, дискретный логарифм — фундамент математики и криптоанализа.

Формулы и алгоритмы

Математический аппарат, реализованный в калькуляторе.

Операции по модулю

(a + b) mod m = ((a mod m) + (b mod m)) mod m

(a - b) mod m = ((a mod m) - (b mod m) + m) mod m

(a × b) mod m = ((a mod m) × (b mod m)) mod m

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

Если p простое и gcd(a,p) = 1:

a^(p-1) ≡ 1 (mod p)

Следовательно: a^(-1) ≡ a^(p-2) (mod p)

Теорема Эйлера

Если gcd(a, m) = 1:

a^φ(m) ≡ 1 (mod m)

φ(m) — функция Эйлера (количество чисел < m, взаимно простых с m)

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

Находит x, y такие что:

ax + by = gcd(a, b)

Используется для нахождения обратного элемента

modular_exponentiation.py

def mod_pow(base, exp, mod):
    """
    Быстрое возведение в степень по модулю.
    Сложность: O(log exp)
    """
    result = 1
    base = base % mod
    while exp > 0:
        if exp % 2 == 1:
            result = (result * base) % mod
        exp = exp >> 1     # exp //= 2
        base = (base * base) % mod
    return result

def mod_inverse(a, m):
    """
    Обратный элемент через расширенный
    алгоритм Евклида.
    """
    g, x, _ = extended_gcd(a, m)
    if g != 1:
        raise ValueError("Обратного не существует")
    return x % m

Продвинутые темы

RАлгоритм RSA

RSA — асимметричная криптосистема, безопасность которой основана на сложности факторизации больших чисел.

Выбрать два больших простых числа p и q
Вычислить n = p × q и φ(n) = (p-1)(q-1)
Выбрать e взаимно простое с φ(n)
Найти d = e^(-1) mod φ(n)
Шифрование: c = m^e mod n
Дешифрование: m = c^d mod n

Ключи RSA

Открытый: (e, n)

Закрытый: (d, n)

e × d ≡ 1 (mod φ(n))

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

Если m_1, m_2, ..., m_k попарно взаимно просты, то система сравнений:

x ≡ a_1 (mod m_1)
x ≡ a_2 (mod m_2)
...
x ≡ a_k (mod m_k)

имеет единственное решение по модулю M = m_1 × m_2 × ... × m_k.

Применения КТО:

Ускорение RSA-дешифрования (в 4 раза быстрее)
Секретное разделение (схема Шамира)
Вычисления с большими числами через малые модули
Параллельные вычисления в компьютерной алгебре

φТеорема Эйлера

Обобщение малой теоремы Ферма: для любого a, взаимно простого с m, выполняется a^φ(m) ≡ 1 (mod m). Функция Эйлера φ(n) считает количество чисел от 1 до n, взаимно простых с n.

φ(p^k) = p^k - p^(k-1)

logДискретный логарифм

Задача нахождения x из уравнения a^x ≡ b (mod p). Считается вычислительно трудной и лежит в основе протоколов Диффи-Хеллмана, ElGamal и эллиптической криптографии (ECDSA).

DLP: g^x ≡ h (mod p), найти x

Практические советы

Приводите к модулю заранее

При умножении больших чисел берите остаток на каждом шаге. Это предотвращает переполнение и ускоряет вычисления: (a * b) mod m = ((a mod m) * (b mod m)) mod m.

Используйте быстрое возведение в степень

Наивный подход a^b имеет сложность O(b), бинарное возведение в степень (binary exponentiation) — O(log b). Разница колоссальна для криптографических размеров.

Проверяйте взаимную простоту

Обратный элемент a^(-1) mod m существует тогда и только тогда, когда gcd(a, m) = 1. Всегда проверяйте это условие перед вычислением.

Отрицательные остатки

В программировании оператор % может давать отрицательный результат. Для корректного остатка используйте формулу: ((a % m) + m) % m.

BigInt для криптографии

RSA использует числа длиной 2048-4096 бит. Стандартные типы данных не справятся — используйте BigInt в JavaScript или GMP в C/C++.

Тест простоты для генерации ключей

Для RSA нужны большие простые числа. Тест Миллера-Рабина с 20+ раундами даёт вероятность ошибки менее 4^(-20) ≈ 10^(-12).

Как пользоваться калькулятором

Выберите вкладку

Определите тип задачи: базовые операции, обратный элемент, возведение в степень, КТО, тест простоты или НОД/расширенный Евклид.

Введите числа

Укажите необходимые параметры. Поддерживаются произвольно большие целые числа благодаря BigInt. Для КТО добавьте нужное количество сравнений.

Нажмите "Вычислить"

Калькулятор мгновенно выполнит расчёт. Все вычисления происходят в вашем браузере — данные никуда не отправляются.

Изучите решение

Помимо ответа, калькулятор показывает пошаговое решение: каждый шаг алгоритма Евклида, каждую итерацию быстрого возведения в степень, проверку результата.

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