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

Сложение, вычитание, умножение и возведение в степень по модулю. Обратный элемент, китайская теорема об остатках, тест простоты Миллера-Рабина. Поддержка произвольно больших чисел через 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. Для КТО добавьте нужное количество сравнений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Создатель

Лиана Арифметова

Миссия: Демократизировать сложные расчеты. Превратить страх перед числами в ясность и контроль. Девиз: «Любая повторяющаяся задача заслуживает своего калькулятора».

⚖️

Отказ от ответственности

Только для информационных целей. Все расчёты, результаты и данные, предоставляемые данным инструментом, носят исключительно ознакомительный и справочный характер. Они не являются профессиональной консультацией — медицинской, юридической, финансовой, инженерной или иной.

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

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

Ограничение ответственности. Авторы и разработчики сервиса не несут никакой ответственности за прямой или косвенный ущерб, возникший в результате использования данных расчётов. Пользователь принимает на себя всю ответственность за интерпретацию и применение полученных результатов.

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

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

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

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

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

Применения

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

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

Хеш-функции

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

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

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

Теория чисел

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

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

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

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

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

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

RАлгоритм RSA

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лиана Арифметова

Отказ от ответственности

Похожие инструменты

Калькулятор стипендии для студентов России

Калькулятор ж/д перевозок (РЖД)

Калькулятор похода: снаряжение, питание, маршрут, бюджет

Калькулятор мощности котла отопления

Калькулятор кредиторской задолженности

Калькулятор совместимости лекарств

Калькулятор аквакультуры и рыбоводства

Калькулятор исполнительного сбора

Генератор Open Graph тегов

Удалитель дублирующих строк

Калькулятор удобрений NPK

Калькулятор акустики помещения (RT60)

NLP Калькулятор: токенизация, TF-IDF, BLEU, перплексия

Калькулятор эмбриологии

Калькулятор отмостки

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