Введение
Стойкость наиболее распространенной системы открытого шифрования RSA и стойкость схемы электронной подписи на основе RSA определяется сложностью задачи факторизации больших целых чисел. Поэтому эта задача -- одна из наиболее важных математических задач современной криптографии. По популярности она превосходит задачу дискретного логарифмирования, а также является составной частью известных алгоритмов дискретного логарифмирования. 
Задача факторизации целых чисел -- это задача нахождения по данному натуральному числу различных простых чисел и натуральных чисел таких, что . Отметим, что если известен некоторый простой делитель числа , то соответствующее может быть легко найдено (например, перебором) за полиномиальное от время. Поэтому основная трудность задачи факторизации заключается в нахождении простых делителей . 
Все описываемые ниже алгоритмы факторизации сводятся к нахождению нетривиальных (т. е. положительных и отличных от  и ) делителей числа , если составное. Если мы умеем находить нетривиальные делители, то разложение на простые множители может быть получено следующим образом. Сначала разложим число на два нетривиальных множителя (если составное), затем, в свою очередь, разложим каждый из этих множителей на два нетривиальных множителя (если этот исходный множитель составной), потом то же самое проделаем со всеми составными множителями, найденными на предыдущем этапе и т. д., пока все множители не станут простыми. Очевидно, что для вычисления разложения на простые множители потребуется находить нетривиальные делители полиномиальное от число раз. 
В свою очередь, для нахождения нетривиального делителя часто используется следующее замечание. Пусть каким-либо образом найдены целые числа такие, что . Тогда если для некоторого , то  -- искомый нетривиальный делитель . Как обычно, запись здесь и далее обозначает наибольший общий делитель чисел и . 
В настоящее время нет достаточно быстрых алгоритмов для факторизации целых чисел. Имеющиеся алгоритмы факторизации по сложности (числу арифметических операций, необходимых для их реализации) разделяются на три группы ( обозначает некоторую константу): 
    1) алгоритмы экспоненциальной сложности, делающие арифметических операций; 
    2) алгоритмы субэкспоненциальной сложности, делающие , арифметических операций, где ; 
    3) алгоритм, называемый методом решета числового поля, и его дальнейшие обобщения, имеющие сложность арифметических операций. 
В криптографических схемах, стойкость которых основана на сложности задачи факторизации целых чисел, в качестве сложно разлагаемого числа часто выбирают произведение двух различных простых чисел. Отметим, что если мы умеем эффективно вычислять дискретные логарифмы по модулю такого , то мы можем эффективно разложить на простые множители: 
Теорема 1.  Пусть , где и  -- различные простые числа. Предположим, что существует вероятностный полиномиальный алгоритм, вычисляющий по и некоторый дискретный логарифм по основанию (т. е. некоторое целое , для которого ) с вероятностью не менее для некоторого полинома . Тогда существует вероятностный полиномиальный алгоритм, разлагающий на простые множители и с вероятностью не менее . 
Через в теореме 1 обозначена подгруппа, порожденная элементом группы . 
Таблицы разложений на множители и больших простых чисел можно найти.