Тест Миллера-Рабина на простоту — это надежный тест для простых чисел, хотя он может определить только вероятность того, что число является простым. Однако вероятность относительна: я могу выбросить сто семерок подряд за столом для игры в кости, но вероятность чрезвычайно низка.
Ссылка на Википедию выше хорошо подходит к математике Миллера-Рабина. Важной особенностью является то, что тест можно применять повторно со случайными значениями bases или k. Каждое выполнение теста с другим значением k снижает вероятность прохождения теста ложным простым числом. Верхний предел вероятности того, что будет сообщено ложное простое число, равен 4 в степени -k.
Тест в коде
Вы можете найти много примеров кода, реализующего Миллера-Рабина для разных языков. Я хотел версию JavaScript, которая использует новые собственные значения BigInt. Единственный код, который я нашел в Интернете, либо использовал целые числа, либо старую библиотеку, использующую пользовательские представления больших целых чисел.
В конце концов, я определил, что этот сайт имеет код JavaScript (в дополнение к реализациям на других языках), наиболее близкий к тому, что я хотел. Однако он использовал значения Integer, поэтому мне пришлось преобразовать его для использования значений BigInt. Это включало следующие шаги:
- Преобразование всех целочисленных литералов в нотацию «n»; например 2 становится 2н.
- Убедитесь, что нет смешанных операций Integer/BigInt.
- Математическая библиотека JavaScript не поддерживает BigInt; обойти это
Я прокомментировал приведенный ниже код (JML-) там, где были внесены необходимые изменения.
To test the test
В исходном коде есть генератор простых чисел ‹ 100. Это все хорошо, но я хочу генерировать БОЛЬШИЕ простые числа! Я создал приложение React именно для этого. Теперь я могу генерировать 25-значные простые числа за миллисекунды.
Я попытался посмотреть, смогу ли я факторизовать эти вероятные простые числа на этом сайте. Конечно же, никаких факторов — они были подлинным товаром. Вуаля!
Дополнительные материалы на plainenglish.io
