Наиболее наивный подход - просто делить на все числа подряд до корня из N. Если Вы хотели узнать это - дальше можно не читать ;-)

1. [Инициализация]
        Если N <= 5, вывести разложение 1 = 1, 2 = 2, 3 = 3, 4 = 2², 5 = 5 в зависимости от N и выйти. Иначе, i := -1, m := 0, L := [ N^1/2 ]
   
   
2. [Cледующее простое]
        Пусть m := m + 1. Если m > k, то i : = j - 1 и идти к шагу 5, иначе d : = p[m].
   
   
3. [Простое деление]
        Пусть r : = N mod d. Если r = 0, то вывести d как нетривиальный делитель N и выйти ( или N := N / d, L : = [ N^1/2 ] и повторить шаг 3, если мы хотим продолжить нахождение делителей N).
   
   
4. [Простое?]
        Если d >= L, то в случае N > 1 вывести сообщение, что оставшаяся часть N - простое и выйти. Иначе, если i < 0 идти на шаг 2.
   
   
5. [Следующий делитель]
        Пусть i := i + 1 mod 8, d := d + t[i]. Если d > B, то вывести сообщение о том, что оставшиеся простые делители N больше B, иначе идти на шаг 3.

     И, наконец, заметим, что нет необходимости в вычислении L := [ N^1/2 ] во время инициализации, так как проверка d >= L в шаге 4 может быть заменена на q <= L, где q - евклидово частное при делении N на d : N = q * d + r, обычно вычисляемое одновременно с остатком в шаге 3.

Методы Монте-Карло

  Метод Монте-Карло 1

Время работы этого метода порядка корень квадратный из минимального простого числа, делящего m. То есть в худшем случае, когда m есть произведение двух простых чисел примерно одного порядка, число m раскладывается этим методом на множители за время корень четвертой степени из m. Алгоритм очень прост, его запись намного короче, чем объяснение, почему он работает. Слова "Монте-Карло" присутствуют в его названии потому, что работа алгоритма зависит от случайного выбора начального числа.

Рассмотрим отображение f кольца Z_m в Z_m:

Последовательность представляет собой орбиту элемента b_0 при отображении f. Поскольку все элементы последовательности принадлежат конечному множеству, последовательность циклическая -- точнее, она содержит начальный апериодический отрезок и далее бесконечно повторяющийся период.

Пусть p -- делитель числа m. Рассмотрим элементы последовательности (2) по модулю p (т.е. образы элементов b_i при каноническом эпиморфизме Z_m --> Z_p):

Так как в Z_p меньше элементов, чем в Z_m, то с большой вероятностью период последовательности (3) меньше, чем период последовательности (2).
Следовательно, найдется пара индексов i, j такая, что

Это означает, что

Отсюда вытекает, что (b_i - b_j) делится на p, но не делится на m. Следовательно, НОД(b_i - b_j, m) нетривиален, и нам удалось разложить m на множители.

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

Можно предложить 2 способа решения задачи поиска цикла в последовательности. Первый способ наиболее простой. Второй чуть-чуть сложнее, но зато более быстрый.

Способ 1

Выполняется следующая последовательность сравнений:
 b0 <---> b1
 b1 <---> b3
 b2 <---> b5
 b3 <---> b7
 b4 <---> b9
 . . .
 b_i <---> b_{2*i+1}
 . . .
 
 

Рано или поздно мы дойдем до равенства двух элементов, поскольку расстояние между сравниваемыми элементами на каждом шаге увеличивается ровно на единицу; кроме того, левый элемент сдвигается вправо, так что он рано или поздно войдет в периодический участок последовательности.

Выпишем алгоритм нахождения делителя.

Выполняется следующая бесконечная последовательность сравнений

b0 <---> b1

b1 <---> b2

b1 <---> b3  

b2 <---> b4

b2 <---> b5

b2 <---> b6

b2 <---> b7

b4 <---> b8

b4 <---> b9

b4 <---> b10

. . .  

b4 <---> b15

b8 <---> b16

b8 <---> b17

. . .

b8 <---> b31

. . .

 Метод Монте-Карло 2

Пусть m --- целое число, которое мы раскладываем на множители. Оно представимо в виде произведения степеней простых чисел