Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Математика / Теория чисел / Разложение на множители /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Методы Монте-Карло - Программирование от RIN.RU
Методы Монте-Карло

Мы рассмотрим 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  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь