Калькулятор теста простоты Ферма

Введите число и основание, чтобы выполнить тест простоты Ферма.

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

  1. Введите нужные значения в поля.
  2. Нажмите «Рассчитать», чтобы увидеть результат.
  3. Скопируйте или поделитесь результатом с помощью кнопки «Поделиться».

Об этом калькуляторе

Малая теорема Ферма утверждает, что если n — простое число, то для любого целого основания a, не делящегося на n, a^(n-1) ≡ 1 (mod n). Этот калькулятор выполняет эту проверку в обратную сторону: по числу n и выбранному основанию a он вычисляет a^(n-1) mod n — если результат не равен 1, то n заведомо составное; если равен 1, то n лишь вероятно простое, поскольку редкие составные числа (псевдопростые числа Ферма и особенно упрямые числа Кармайкла) могут проходить тест для многих оснований; число Кармайкла проходит его для любого основания, не имеющего общих делителей с n.

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

Была ли эта страница полезной?

Можно выбрать до 3 реакций.

Комментарии

  • Оставьте первый комментарий.

Популярные калькуляторы

Все калькуляторы