Введение

Математический алгоритм

Метод пробного деления — самый трудоемкий, но при этом наиболее понятный из алгоритмов факторизации целых чисел. Основная идея метода пробного деления заключается в проверке, делится ли целое число n, которое требуется разложить на множители, на каждое число по порядку, меньшее квадратного корня из n. Например, для целого числа 12, его делителями являются только 1, 2, 3, 4, 6 и 12. Выбирая из этого списка только наибольшие степени простых чисел, получаем, что метод пробного деления впервые был описан Фибоначчи в его книге «Liber Abaci» (1202 год).

Скорость

В худшем случае, метод пробного деления — трудоёмкий алгоритм. Для числа в системе счисления с основанием 2 и *n* цифрами, *a*, если начинать с двух и проверять делители только до квадратного корня из *a*, алгоритму потребуется

пробных делений, где обозначает функцию распределения простых чисел, то есть количество простых чисел, меньших *x*. Это не учитывает накладные расходы на проверку простоты для получения простых чисел в качестве возможных делителей. Полезная таблица не должна быть слишком большой: P(3512) = 32749, последнее простое число, которое помещается в 16-битное знаковое целое, и P(6542) = 65521 для 16-битных беззнаковых целых. Этого достаточно для проверки простоты чисел до 655372 = 4 295 098 369. Подготовка такой таблицы (обычно с помощью решета Эратосфена) имеет смысл только в том случае, если необходимо проверить большое количество чисел. Если же используется вариант без проверки простоты, а просто деление на каждое нечётное число, меньшее квадратного корня из числа с основанием 2 и *n* цифрами *a*, независимо от того, является оно простым или нет, то это может занять до:

В обоих случаях требуемое время растёт экспоненциально с увеличением количества цифр в числе. Тем не менее, это вполне удовлетворительный метод, учитывая, что даже самые известные алгоритмы имеют экспоненциальный рост времени. Для числа, выбранного случайным образом из целых чисел заданной длины, существует 50% вероятность, что 2 является делителем *a*, 33% вероятность, что 3 является делителем *a*, и так далее. Можно показать, что 88% всех положительных целых чисел имеют делитель меньше 100, а 92% — делитель меньше 1000. Таким образом, при работе с произвольно большим *a* стоит проверить делимость на малые простые числа, поскольку для , в системе счисления с основанием 2
Однако, многие числа, не имеющие делителей среди малых простых чисел, могут потребовать дней или месяцев для факторизации методом пробного деления. В таких случаях используются другие методы, такие как квадратичное решето и общее решето числового поля (GNFS). Поскольку эти методы также имеют сверхполиномиальный рост времени, практический предел количества цифр *n* достигается очень быстро. По этой причине в криптографии с открытым ключом значения для *a* выбираются с большими простыми делителями примерно одинакового размера, чтобы их нельзя было разложить на множители каким-либо известным методом за разумное время на доступных компьютерных системах или кластерах, таких как суперкомпьютеры и вычислительные сети. Самое большое криптографически значимое число, которое было разложено на множители, — RSA-250, 250-значное число, с использованием GNFS и ресурсов нескольких суперкомпьютеров. Время работы составило 2700 процессорных лет.