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

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

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