Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 62 стр.

Глава 2. Простые алгоритмы факторизации                                    63

       int ρ-Pollard (int n)
       { int x = random (1, n-2);
       int y = 1; int i = 0; int stage = 2;
       while(Н.О.Д.(n, abs(x − y)) = 1)
       {
           if (i = = stage ){
             y = x;
              stage = stage*2; }
           x=x ∗ x + 1(modn);
           i=i + 1;
       }
       return Н.О.Д.(n, abs(x − y)); }
      В этом варианте вычисление требует хранить в памяти всего три
переменные n, x и y , что выгодно отличает этот метод от других методов
факторизации.
      Еще одна вариация ρ-метода Полларда была разработана Флойдом
(Floyd). Согласно Флойду, значение y обновляется на каждом шаге по
формуле y = F 2 (y) = F (F (y)), поэтому на шаге i будут получены значения
xi = F i (x0 ), yi = x2i = F 2i (x0 ), и Н.О.Д. на этом шаге вычисляется между
n и y − x.

      Обоснование ρ-метода Полларда
      Приведем обоснование этого метода и оценим его трудоемкость.
Оценка основывается на известном «парадоксе дня рождения».

Теорема 2.1. (Парадокс дня рождения) Пусть λ > 0. Для случайной
                                                                √
выборки из l + 1 элементов, каждый из которых меньше q , где l = 2λq ,
вероятность того, что два элемента окажутся равными

                      p > 1 − e−λ .

Отметим, что вероятность p = 0, 5 в парадоксе дня рождения достигается
при λ ≈ 0, 69.