Как разложение на простые множители связано с криптографией?

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

В этом алгоритме для того, чтобы превратить исходное сообщение в зашифрованное, достаточно знать произведение двух чисел, а чтобы расшифровать его обратно — надо знать каждое из этих чисел по отдельности. yandex.ru Если взять два числа и опубликовать их произведение, каждый сможет с его помощью зашифровать своё сообщение. yandex.ru А вот чтобы его расшифровать, надо это произведение разложить на множители, именно поэтому множители должны быть простыми. yandex.ru

На сегодня не существует алгоритма, способного провести разложение действительно больших чисел за разумное время. yandex.ru Это позволяет считать, что единственным человеком, способным расшифровать сообщение, зашифрованное по алгоритму RSA, будет тот, кто знает, какие простые числа были выбраны изначально. yandex.ru