calcal.ru

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

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

Загрузка калькулятора...
6
Операций
Полный набор инструментов
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, ИНН, штрих-коды, СНИЛС &mdash; все проверяют корректность с помощью остатка от деления.

🔄

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

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

📅

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

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

🔢

Теория чисел

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

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

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

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

(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 — асимметричная криптосистема, безопасность которой основана на сложности факторизации больших чисел.

  1. Выбрать два больших простых числа p и q
  2. Вычислить n = p × q и φ(n) = (p-1)(q-1)
  3. Выбрать e взаимно простое с φ(n)
  4. Найти d = e^(-1) mod φ(n)
  5. Шифрование: c = m^e mod n
  6. Дешифрование: 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

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

01

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

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

02

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

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

03

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

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

04

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

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

05

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

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

06

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

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

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

1

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

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

2

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

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

3

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

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

4

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

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

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

Это арифметика с «оборачиванием». Представьте часы: после 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). Никакие данные не отправляются на сервер. Это означает полную конфиденциальность ваших расчётов. Однако для реальных криптографических задач рекомендуется использовать специализированные библиотеки с защитой от атак по побочным каналам.
Лиана Арифметова
Создатель

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

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

Был ли этот калькулятор полезен?

⚖️

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

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

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

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

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

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

🧮

Калькулятор зарплаты (гросс/нет)

Зарплата на руки из оклада. НДФЛ 13%/15%/30%, страховые взносы, районные коэффициенты. Россия 2024-2025.

🏗️

Калькулятор календарного плана: критический путь, Гант, PERT

Расчёт календарного плана строительства. Критический путь, диаграмма Ганта, ресурсное планирование, нормативные сроки по СНиП.

🧮

Калькулятор размера плода по УЗИ

Оценка размера плода по данным УЗИ: БПР, ОЖ, ДБ. Нормы по неделям беременности.

🧮

Калькулятор волейбола: статистика, прыжок, подача, площадка

Волейбольный калькулятор. Статистика атаки и блока, калории, высота прыжка, скорость подачи, размеры площадки.

🧮

Калькулятор себестоимости изделия

Расчёт себестоимости: материалы, работа, накладные расходы. Наценка, маржа, рекомендуемая цена.

🧮

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

Расчёт размера выборки, критерий хи-квадрат, корреляция Пирсона и мощность теста. Инструменты для научных и маркетинговых исследований.

📐

Калькулятор площади и объёма фигур

Расчет площади, периметра, объёма и поверхности для 2D и 3D фигур. Формулы Герона, эллипсы, торы, инженерные задачи.

💻

Калькулятор веб-производительности: бюджет страницы, изображения, JS-бандл, CWV

Комплексный калькулятор веб-производительности: бюджет веса страницы (3G/4G/Broadband), оптимизация изображений (WebP/AVIF, responsive), анализ JS-бандла (parse/compile, code-splitting, tree-shaking), критический путь рендеринга (TTFB, FCP), стратегия кэширования (CDN, TTL) и трекер Core Web Vitals (LCP, FID, CLS, TTI, TBT, Lighthouse score).

🏗️

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

Расчёт демонтажа зданий и сооружений. Объём материалов, стоимость работ, необходимая техника, сроки, вывоз и утилизация отходов.

🏗️

Калькулятор монтажной пены

Расчёт расхода монтажной пены: количество баллонов по объёму заполнения. Бытовая, профессиональная, зимняя. Стоимость.

📐

Калькулятор логарифмов

Логарифм числа по любому основанию. Натуральный (ln), десятичный (lg), двоичный (log2) и произвольный.

⚙️

Геотермальный калькулятор

Расчёты геотермальной энергии: тепловые насосы, градиент, скважины, экономика

🏠

Калькулятор и тест памяти (digit span, мнемотехники)

Тест кратковременной памяти (digit span по Миллеру 7±2), дворец памяти, техники запоминания и ёмкость памяти. Для студентов и всех, кто развивает память.

⚙️

Калькулятор бережливого производства (Lean)

Расчёты Lean: время такта, OEE, канбан, 5S аудит, SMED, VSM метрики

🏗️

Калькулятор подоконника

Расчёт длины, ширины и стоимости подоконника. ПВХ, дерево, камень, МДФ. Кронштейны, заглушки, монтаж.