Как вероятность простых чисел используется в криптографии?

В криптографии вероятность простых чисел используется для генерации ключей во многих алгоритмах, включая RSA и ElGamal. ru.wikipedia.org ru.ruwiki.ru

Поскольку тестирование простоты больших чисел требует существенных временных затрат, часто применяют вероятностные методы, которые не дают строгого математического доказательства простоты числа, но обеспечивают быстрое выполнение проверки. cyberleninka.ru

Некоторые из таких методов:

• Проверка делимости на небольшие простые числа. ru.wikipedia.org ru.ruwiki.ru Это позволяет отсечь множество заведомо составных чисел, прежде чем проверять их посредством более трудоёмких алгоритмов. ru.wikipedia.org ru.ruwiki.ru
• Тест Миллера — Рабина. ru.wikipedia.org ru.ruwiki.ru Если число не проходит хотя бы одной проверки — оно не является простым. ru.ruwiki.ru В противном случае с большой вероятностью (зависящей от количества раундов) число является простым. ru.ruwiki.ru

Причина широкого использования простых чисел в криптографии — трудность их обнаружения. moluch.ru Например, открытый ключ в некоторых алгоритмах состоит из произведения двух больших простых чисел, используемых для шифрования сообщения, а секретный ключ — из этих же простых чисел, но используемых для расшифровки. stackoverflow.com