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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Криптостойкость RSA. Алгоритмы факторизации 58
x
i
= F
i
(x
0
), y
i
= x
2i
= F
2i
(x
0
), и Н.О.Д. на этом шаге вычисляется между
n и y − x.
Обоснование ρ-метода Полларда
Приведем обоснование этого метода и оценим его трудоемкость.
Оценка основывается на известном «парадоксе дня рождения».
Теорема 3.1. (Парадокс дня рождения) Пусть λ > 0. Для случайной
выборки из l + 1 элементов, каждый из которых меньше q , где l =
√
2λq ,
вероятность того, что два элемента окажутся равными
p > 1 − e
−λ
.
Отметим, что вероятность p = 0, 5 в парадоксе дня рождения достигается
при λ ≈ 0, 69.
Пусть последовательность {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
̸= 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, становятся не эффективными.
Глава 2. Криптостойкость RSA. Алгоритмы факторизации                       58

xi = F i (x0 ), yi = x2i = F 2i (x0 ), и Н.О.Д. на этом шаге вычисляется между
n и y − x.

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

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

                    p > 1 − e−λ .

Отметим, что вероятность p = 0, 5 в парадоксе дня рождения достигается
при λ ≈ 0, 69.
      Пусть      последовательность      {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 ̸= 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, становятся не эффективными.

Страницы