Разложение на множители (факторизация)

Разложение на множители числа (например, ) является одной из древнейших проблем теории чисел. Приступая к факторизации числа, следует сначала убедиться, что оно не простое. Это можно сделать с помощью одного из описан­ных выше тестов простоты. Их трудоемкость, как правило, значитель­но меньше, чем у алгоритмов факторизации.

Самые лучшие алгоритмы на сегодняшний день:

1. Решето общего числового поля (самый быстрый из известных алгоритмов для чисел размером и более десятичных разрядов).

2. Квадратичное решето для чисел размером (для чисел менее десятичных разрядов; в 1994г. за 8 месяцев на 1600 процессорах было разложено 129 разрядное число).

3. Метод эллиптической кривой.

4. Монте-Карло Поларда.

5. Метод непрерывных дробей (по времени не подходит для реализации).

6. Проверка делением (самый старый алгоритм разложения; состоит в проверке на деление на каждое простое число, меньше или равное квадратному корню из раскладываемого числа).

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

В лабораторной работе №7 мы рассмотрим более простые методы, имеющие экспоненциальную сложность.