Проблема факторизации больших чисел в контексте криптосистемы RSA заключается в вычислительной сложности разложения большого составного числа на простые множители. 4

В основу криптографической системы RSA положена сложность задачи факторизации произведения двух больших простых чисел. 1 Для шифрования используется операция возведения в степень по модулю большого числа, а для дешифрования (обратной операции) за разумное время необходимо уметь вычислять функцию Эйлера от данного большого числа, для чего нужно знать разложение числа на простые множители. 1

Факторизация больших чисел считается сложной задачей, особенно когда числа имеют несколько сотен или тысяч цифр. 4

Например, лучшим для разложения больших чисел считается алгоритм «решета числового поля» (NFS, Number Field Sieve), но эффективно реализовать его на ПК не представляется возможным, поэтому взлом 1024-битного ключа практически нереален. 2