Мы рассмотрим 2 весьма изящных метода факторизации, предложенных Поллардом. Они очень просты и позволяют быстро извлечь из составного числа все его небольшие простые делители. Метод Монте-Карло 1 Время работы этого метода порядка корень квадратный из минимального простого числа, делящего m. То есть в худшем случае, когда m есть произведение двух простых чисел примерно одного порядка, число m раскладывается этим методом на множители за время корень четвертой степени из m. Алгоритм очень прост, его запись намного короче, чем объяснение, почему он работает. Слова "Монте-Карло" присутствуют в его названии потому, что работа алгоритма зависит от случайного выбора начального числа. Рассмотрим отображение f кольца Zm в Zm: f: Zm --> Zm f(x) = x^2 + 1 (mod m) Выберем случайным образом элемент b_0 кольца Zm.Рассмотрим бесконечную последовательность элементов кольца Zm: b_0, b_1 = f(b_0), b_2 = f(b_1), b_3 = f(b_2), ... (2) Последовательность представляет собой орбиту элемента b_0 при отображении f.Поскольку все элементы последовательности принадлежат конечному множеству, последовательность циклическая -- точнее, она содержит начальный апериодический отрезок и далее бесконечно повторяющийся период. Пусть p -- делитель числа m. Рассмотрим элементы последовательности (2) по модулю p (т.е. образы элементов b_i при каноническом эпиморфизме Zm --> Zp): c_0 == b_0 (mod p), c_1 == b_1 (mod p), c_2 == b_2 (mod p), ... (3) Так как в Zp меньше элементов, чем в Zm, то с большой вероятностьюпериод последовательности (3) меньше, чем период последовательности (2). Следовательно, найдется пара индексов i, j такая, что c_i = c_j, b_i != b_j. Это означает, что b_i == b_j (mod p), b_i != b_j (mod m). Отсюда вытекает, что (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} . . . Рано или поздно мы дойдем до равенства двух элементов, поскольку расстояние между сравниваемыми элементами на каждом шаге увеличивается ровно на единицу; кроме того, левый элемент сдвигается вправо, так что он рано или поздно войдет в периодический участок последовательности. Выпишем алгоритм нахождения делителя. алгоритм факторизация1(вход: целое число m, выход: целое число d): успех | дано: целое число m | надо: получить нетривиальный делитель d числа m | возвращаемое значение: true, если удалось разложить, | false в противном случае начало | maxSteps := 1000000 // Максимальное число шагов | step := 0 | | b0 := случайное число в интервале 0..m | b1 := mod(b0 * b0 + 1, m) | d := gcd(b1 - b0, m) | | цикл пока step < maxSteps && d == 1 выполнять // Пока НОД тривиален | | b0 = mod(b0 * b0 + 1, m) // Применяем отображение f | | b1 = mod(b1 * b1 + 1, m); // один раз к b0 и дважды | | b1 = mod(b1 * b1 + 1, m) // к b1 | | d := gcd(b1 - b0, m) | | step := step + 1 | конец_цикла | | вернуть (d != 1) // Успех := d нетривиален конец_алгоритма На каждом шаге цикла мы трижды вычисляем значение отображения f. Небольшая модификация алгоритма позволяет делать это только один раз. Способ 2 -------- Выполняется следующая бесконечная последовательность сравнений 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 . . . Вся последовательность сравнений разбивается на серии. В очередной серии мы сравниваем элемент b_s, где s -- степень двойки, последовательно с элементами b_{2s}, b_{2s+1}, b_{2s+2}, ..., b_{4s-1}. Серия содержит 2s сравнений. Выпишем алгоритм. алгоритм факторизация2(вход: целое число m, выход: целое число d): успех | дано: целое число m | надо: получить нетривиальный делитель d числа m | возвращаемое значение: true, если удалось разложить, | false в противном случае начало | maxSteps := 19 // Максимальная длина серии 2^19 | step := 0 | | b0 := случайное число в интервале 0..m | b1 := mod(b0 * b0 + 1, m) | a := b1 // Первый элемент серии | seriesLength := 1 // Длина серии | | цикл пока step < maxSteps && d == 1 выполнять // пока НОД тривиален | | Инвариант: b0 -- элемент последовательности с индексом, | | равным нулю или степени двойки | | a -- элемент, индекс которого равен удвоенному индексу | | элемента b0 (или 1, если индекс b0 равен 0) | | seriesLength == удвоенному индексу элемента a | | d := gcd(b1 - b0, m) | | len := 0 | | | | цикл пока d == 1 и len < seriesLength выполнять | | | b1 = mod(b1 * b1 + 1, m); | | | d := gcd(b1 - b0, m) | | | len := len + 1 | | конец_цикла | | | | b0 := a | | a := b1 | | seriesLength := seriesLength * 2 | конец_цикла | | вернуть (d != 1) // Успех := d нетривиален конец_алгоритма Вперед  >>>  1  2   8  Комментарии к статье  8 8  Обсудить в чате