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

Этот метод является методом специального назначения и рекомендуется для отсеивания маленьких делителей на первом шаге. Если известно, что число не имеет малых делителей (например, модуль 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, освобождаем память.

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

Метод Ферма.

Метод специального назначения, применяется для 2-факторизации, или сплиттинга.

Если n – нечетное составное число, не являющееся степенью целого числа, то этот метод находит целые числа x, y: n=x²—y² . Тогда n=(x+y)(x—y).

Алгоритм:

Ш.1. Вычисляем x= +1.

Ш.2. Если x= , то идем на Выход с сообщением «n – простое число».

Ш.3. Вычисляем z=x²—n и y= . Если y²=z, то идем на Выход, a=x+y, b=x—y.

Ш.4. Вычисляем x=x+1. Идем на Шаг 2.

Выход: n=a·b.

Отметим, что делители a и b, получившиеся в результате 2-факторизации Ферма, в общем случае не являются простыми и требуют проверки на простоту и дальнейшей факторизации.