Тест простоты Миллера-Рабина

Калькулятор выполняет тест простоты Миллера-Рабина и выясняет может ли заданное число быть простым или нет. Если ответ отрицательный - число составное, если ответ положительный, то число с большой вероятностью простое. Тест использует заданное число оснований (пробных свидетелей простоты), которые вводятся списком или генерируются случайным образом в диапазоне от 2 до n-1, где n - проверяемое число. Калькулятор может выдавать пошаговую детализацию работы теста. Информацию по алгоритму Миллера-Рабина можно найти сразу за калькулятором.

Тест простоты Миллера-Рабина

Целое число

Основания

Случайные

Список

Количество раундов

Основания

Детали

Рассчитать

Может быть простым?

 

Разложение

 

Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.

Загрузить 

 Ссылка  Сохранить  Виджет

Алгоритм теста простоты Миллера-Рабина

Для проверки на простоту числа алгоритмом Миллера-Рабина мы должны привести четное число n-1 число к виду 2^sd, где n-тестируемое число, d - нечетное число, s - степень двойки. Числа s и d можно получить последовательным делением n-1 на 2.
Тогда мы проверяем, что для любого целого a, в диапазоне [2..n-1], справедливо хотя бы одно из условий:

В условии 2. r берется в диапазоне [0..s).

Если хотя бы одно условие выполняется - значит выбранное a - является свидетелем простоты числа n, и число n с большой вероятностью может быть простым. Для увеличения этой вероятности мы повторяем тест для другого случайно выбранного основания.
Если оба условия не выполняются, то число n - составное и дальнейшее тестирование можно прекратить.
Тест Миллера-Рабина успешно справляется с числами Кармайкла, которые не поддаются тесту Ферма. К примеру число 29341, ошибочно определяемое тестом Ферма, как возможно простое, определяется как составное тестом Миллера-Рабина, уже по основанию 3.
В отличие от теста Ферма, для теста Миллера-Рабина нет плохих тестируемых чисел. Для любого числа тест дает правильный ответ с большой вероятностью. Неверный результат работы определяется лишь случайным выбором пробных свидетелей, вероятность чего мала ¹.
Согласно исследованию Рабина не более четверти чисел в диапазоне [1..n) не являются свидетелями² (т.е. дают ошибочный результат в тесте Миллера-Рабина), поэтому, получая потенциальных свидетелей случайным образом k раз, вероятность ошибки теста будет не более 1/4^k.