Разложение на множители числа (например, ) является одной из древнейших проблем теории чисел. Приступая к факторизации числа, следует сначала убедиться, что оно не простое. Это можно сделать с помощью одного из описанных выше тестов простоты. Их трудоемкость, как правило, значительно меньше, чем у алгоритмов факторизации.
Самые лучшие алгоритмы на сегодняшний день:
1. Решето общего числового поля (самый быстрый из известных алгоритмов для чисел размером и более десятичных разрядов).
2. Квадратичное решето для чисел размером (для чисел менее десятичных разрядов; в 1994г. за 8 месяцев на 1600 процессорах было разложено 129 разрядное число).
3. Метод эллиптической кривой.
4. Монте-Карло Поларда.
5. Метод непрерывных дробей (по времени не подходит для реализации).
6. Проверка делением (самый старый алгоритм разложения; состоит в проверке на деление на каждое простое число, меньше или равное квадратному корню из раскладываемого числа).
Почти все эти алгоритмы субэкспоненциальной сложности. Алгоритмов факторизации, имеющих оценки сложности лучше указанной, в настоящее время не существует.
В лабораторной работе №7 мы рассмотрим более простые методы, имеющие экспоненциальную сложность.