homechevron_rightУчебаchevron_rightМатематика

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

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

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

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

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

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

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

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

  1. a^{d}\equiv 1{\pmod {n}}
  2. a^{2^{r}d}\equiv -1{\pmod {n}}

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

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


  1. Т. Кормен, Ч. Лейзерсон, Р. Ривест Алгоритмы: построение и анализ. 

  2. Michael O. Rabin, Probabilistic Algorithm for Testing Primality, Journal of number theory 12, 128-138 (1980) 

Ссылка скопирована в буфер обмена
Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Тест простоты Миллера-Рабина

Комментарии