Калькулятор теории чисел — простые числа, НОД/НОК, модулярная арифметика и другое
Калькулятор теории чисел
Исследуйте простые числа, разложение на множители, наибольший общий делитель, модулярную арифметику и многое другое. Все вычисления выполняются локально в вашем браузере: введённые данные никуда не загружаются.
Режим:
Проверка простоты
Введите число и нажмите «Проверить»
Подсказка: используется детерминированный тест Миллера — Рабина для чисел до 264. Нажмите «Следующее простое» или «Предыдущее простое», чтобы найти соседние простые числа.
Разложение на простые множители
Введите число и нажмите «Разложить»
Подсказка: поддерживаются целые числа до 1015. Разложение в дерево множителей с представлением в виде простых степеней.
Калькулятор НОД и НОК
Введите числа и нажмите «НОД», «НОК» или «Оба»
Подсказка: введите 2 или более целых чисел через запятую. НОД вычисляется алгоритмом Евклида; НОК считается как |a·b|/НОД(a,b).
Модулярная арифметика
Введите a, b, m и нажмите операцию
Подсказка: модульное возведение в степень использует быстрое возведение (возведение в квадрат и умножение). Обратный по модулю элемент существует только тогда, когда a и m взаимно просты.
Делители и функции делителей
Введите число и нажмите «Вычислить»
Подсказка: выводятся все положительные делители, количество делителей d(n), сумма делителей σ(n) и собственные делители. Поддерживаются числа до 1012.
Функция Эйлера и арифметические функции
Введите число и нажмите «Вычислить»
Подсказка: вычисляются функция Эйлера φ(n), функция Мёбиуса μ(n), σ(n), d(n) и связанные арифметические функции.
Простые числа и сравнения
Простое число имеет ровно два делителя: 1 и само себя; каждое целое число больше 1 единственным образом раскладывается на простые множители (основная теорема арифметики). Сравнение a ≡ b (mod n) означает, что n делит a−b: арифметика циферблата, где 10 + 5 ≡ 3 (mod 12), и основа НОД, НОК и модульного возведения в степень.
Перемножить два больших простых числа можно мгновенно, но восстановить их по произведению вычислительно очень трудно. Эта односторонняя асимметрия лежит в основе шифрования RSA и объясняет, почему φ(n) для модуля в 2048 бит не публикуется.
