2.1. Метод пробных делений.

Этот метод является методом специального назначения и рекомендуется для отсеивания маленьких делителей на первом шаге. Если известно, что число не имеет малых делителей (например, модуль RSA), то этот метод не стоит применять.

Прежде чем приступать к факторизации числа этим методом, следует выделить все степени двойки и тройки.

Задается некая теоретическая граница B ≤, которая задает максимальную величину испытываемых делителей и обусловливается доступным объемом памяти и вычислительными возможностями, а также некоторыми априорными сведениями о структуре числаn.

Если В невелико, то строим заранее таблицу простых чисел, меньших или равных В и проверяем делимость n на эти числа.

Иначе выбираем числа d₁=5, d₂=5+2=7, d₃=d₂+4=11, d₅=d₄+2, … , d_k > B. (чередуем шаг +2 и +4 с тем, чтобы отсеять числа, кратные «2» и «3»).

Эти d₁, … , d_k являются возможными делителями n. Осуществляем пробные деления на d_i (i = ). При этом действия осуществляются в следующем порядке:

Для каждого i:

Ш.1. Генерируем d_i.

Ш.2. Осуществляем пробное деление на d_i. Если d_i\n, то n=n/d_i и повторяем

Шаг 2. Если d_i не делит n, то идем на Шаг 3.

Ш.3. Уничтожаем d_i, освобождаем память.

Заметим, что все малые делители, выделенные вышеуказанным способом, будут простыми.