Факториза́ция — разложение числа на простые множители. На предположении о сложности данного процесса основывается криптостойкость некоторых алгоритмов шифрования с открытым ключом, таких, как RSA.

Наиболее тривиальным алгоритмом факторизации чисел является полный перебор возможных делителей. Сложность этого алгоритма равна $O(N^\{1/2\})$. ρ-алгоритм Полларда имеет сложность $O(N^\{1/4\})$. Метод непрерывных дробей, метод квадратичного решета и метод на основе эллиптических кривых имеют сложность .

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

Решение задачи факторизации с полиномиальной сложностью возможно на квантовом компьютере с помощью алгоритма Шора.

Теория чисел | Алгоритмы

Primfaktorzerlegung | Prime factorization algorithm | Factorisation en nombres premiers