Тест Миллера — Рабина никогда не доказывает, что число простое.

Он может сказать только:

«вероятно простое».

И всё же этот вероятностный тест используют для генерации RSA-ключей, защищающих банки, SSH-серверы и HTTPS-соединения.

При достаточном количестве случайных свидетелей вероятность того, что составное число пройдёт проверку, становится астрономически малой.

@Cpportal