Тест простоты Миллера-Рабина
Калькулятор проверяет является ли число составным, используя тест Миллера-Рабина.
Этот материал распространяется на условиях лицензии Creative Commons Attribution/Share-Alike License 3.0 (Unported). Это означает, что вы можете размещать этот контент на своем сайте или создавать на его основе собственный (в том числе и в коммерческих целях), при условии сохранения оригинального лицензионного соглашения. Кроме того, Вы должны отметить автора этой работы, путем размещения HTML ссылки на оригинал работы https://planetcalc.ru/8995/. Пожалуйста оставьте без изменения все ссылки на других авторов данной работы или работы, на основе которой создана данная работа (если таковые имеются в спроводительном тексте).
Калькулятор выполняет тест простоты Миллера-Рабина и выясняет может ли заданное число быть простым или нет. Если ответ отрицательный - число составное, если ответ положительный, то число с большой вероятностью простое. Тест использует заданное число оснований (пробных свидетелей простоты), которые вводятся списком или генерируются случайным образом в диапазоне от 2 до n-1, где n - проверяемое число. Калькулятор может выдавать пошаговую детализацию работы теста. Информацию по алгоритму Миллера-Рабина можно найти сразу за калькулятором.
Тест простоты Миллера-Рабина
Алгоритм теста простоты Миллера-Рабина
Для проверки на простоту числа алгоритмом Миллера-Рабина мы должны привести четное число n-1 число к виду 2sd, где n-тестируемое число, d - нечетное число, s - степень двойки. Числа s и d можно получить последовательным делением n-1 на 2.
Тогда мы проверяем, что для любого целого a, в диапазоне [2..n-1], справедливо хотя бы одно из условий:
В условии 2. r берется в диапазоне [0..s).
Если хотя бы одно условие выполняется - значит выбранное a - является свидетелем простоты числа n, и число n с большой вероятностью может быть простым. Для увеличения этой вероятности мы повторяем тест для другого случайно выбранного основания.
Если оба условия не выполняются, то число n - составное и дальнейшее тестирование можно прекратить.
Тест Миллера-Рабина успешно справляется с числами Кармайкла, которые не поддаются тесту Ферма. К примеру число 29341, ошибочно определяемое тестом Ферма, как возможно простое, определяется как составное тестом Миллера-Рабина, уже по основанию 3.
В отличие от теста Ферма, для теста Миллера-Рабина нет плохих тестируемых чисел. Для любого числа тест дает правильный ответ с большой вероятностью. Неверный результат работы определяется лишь случайным выбором пробных свидетелей, вероятность чего мала 1.
Согласно исследованию Рабина не более четверти чисел в диапазоне [1..n) не являются свидетелями2 (т.е. дают ошибочный результат в тесте Миллера-Рабина), поэтому, получая потенциальных свидетелей случайным образом k раз, вероятность ошибки теста будет не более 1/4k.
Комментарии