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

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

Глава 2. Простые алгоритмы факторизации 64
Пусть последовательность {u
n
} состоит из разностей
|x
i
− x
j
|, проверяемых в ходе работы алгоритма. Определим новую
последовательность {z
n
}, где z
n
= u
n
mod q, q – меньший из делителей
n. Все члены последовательности {z
n
} меньше
√
n. Если рассматривать
{z
n
} как случайную последовательность чисел, меньших q , то, согласно
парадоксу близнецов, вероятность того, что среди первых l + 1 ее членов
попадутся два одинаковых, превысит 1/2 при λ ≈ 0, 69, тогда l должно
быть не меньше
√
2λq ≈
√
1.4q ≈ 1, 18
√
q .
Если z
i
= z
j
, тогда x
i
− x
j
≡ 0 mod q → x
i
− x
j
= kq для некоторого
k ∈ Z. Если x
i
6= x
j
, что выполняется с большой вероятностью, то искомый
делитель q числа n будет найден как Н.О.Д.(n, x
i
− x
j
). Поскольку
√
q ≤
n
1/4
, то с вероятностью, превышающей 0,5, делитель n может быть найден
за 1, 18 · n
1/4
итераций.
Таким образом, ρ-метод Полларда является вероятностным методом,
позволяющим найти нетривиальный делитель q числа n за O(q
1/2
) ≤
O(n
1/4
) итераций. Сложность вычисления нетривиального делителя в этом
методе зависит только от размера этого делителя, а не от размера числа n.
Поэтому, ρ–метод Полларда применим в тех случаях, когда другие методы
факторизации, зависящие от размера n, становятся не эффективными.
Отметим, что в некоторых случаях, последовательность {y
n
} может
зацикливаться (т.е. на некотором шаге t появляется x
t
= x
0
, после чего
последовательность повторяется), тогда надо поменять исходный элемент x
0
или полином F (x) на какой–нибудь другой.
Упражнения.
1. Подберите несколько составных чисел n одинаковой длины, и
выполните пробное разложение этих чисел методом Полларда.
Вычислите среднее время (количество итераций) до нахождения
нетривиального делителя n. Как сильно отличается время вычисления
для различных n?
2. Выполните упражнение 1 с алгоритмом Флойда. Сравните среднее
время вычисления делителя в первом и втором случаях.
Глава 2. Простые алгоритмы факторизации                                64

      Пусть      последовательность   {un }    состоит    из    разностей
|xi − xj |, проверяемых в ходе работы алгоритма. Определим новую
последовательность {zn }, где zn = un mod q , q – меньший из делителей
                                                √
n. Все члены последовательности {zn } меньше n. Если рассматривать
{zn } как случайную последовательность чисел, меньших q , то, согласно
парадоксу близнецов, вероятность того, что среди первых l + 1 ее членов
попадутся два одинаковых, превысит 1/2 при λ ≈ 0, 69, тогда l должно
               √      √           √
быть не меньше 2λq ≈ 1.4q ≈ 1, 18 q .
      Если zi = zj , тогда xi − xj ≡ 0 mod q → xi − xj = kq для некоторого
k ∈ Z. Если xi 6= xj , что выполняется с большой вероятностью, то искомый
                                                                     √
делитель q числа n будет найден как Н.О.Д.(n, xi − xj ). Поскольку q ≤
n1/4 , то с вероятностью, превышающей 0,5, делитель n может быть найден
за 1, 18 · n1/4 итераций.
      Таким образом, ρ-метод Полларда является вероятностным методом,
позволяющим найти нетривиальный делитель q числа n за O(q 1/2 ) ≤
O(n1/4 ) итераций. Сложность вычисления нетривиального делителя в этом
методе зависит только от размера этого делителя, а не от размера числа n.
Поэтому, ρ–метод Полларда применим в тех случаях, когда другие методы
факторизации, зависящие от размера n, становятся не эффективными.
      Отметим, что в некоторых случаях, последовательность {yn } может
зацикливаться (т.е. на некотором шаге t появляется xt = x0 , после чего
последовательность повторяется), тогда надо поменять исходный элемент x0
или полином F (x) на какой–нибудь другой.

Упражнения.

  1. Подберите несколько составных чисел n одинаковой длины, и
     выполните пробное разложение этих чисел методом Полларда.
     Вычислите среднее время (количество итераций) до нахождения
     нетривиального делителя n. Как сильно отличается время вычисления
     для различных n?

  2. Выполните упражнение 1 с алгоритмом Флойда. Сравните среднее
     время вычисления делителя в первом и втором случаях.

Страницы