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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Криптостойкость RSA. Алгоритмы факторизации 56
2. Строим последовательность простых чисел 2 < 3 < 5 < ... < p
m
,
меньших B и последовательность степеней a
i
такую, что p
a
i
i
< B .
3. Полагаем число R =
∏
m
i=1
q
a
i
i
. Если p является B –степенно-гладким,
то R делится на p.
4. Выбираем случайным образом числа P и Q и строим
последовательность чисел Люка, пока не вычислим u
R
.
5. Далее вычислим Н.О.Д.(n, u
R
) = d. Если 1 < d < n, то задача решена.
Доказано, что если Q взаимно просто с p и
(
P
2
− 4Q
p
)
= −1,
то свойства последовательности Люка обеспечивают нахождение
нетривиального делителя числа n.
3.4. ρ-метод Полларда
Этот метод был разработан Джоном Поллардом в 1975 г. Пусть n –
число, которое следует разложить. ρ-метод Полларда работает следующим
образом:
1. Выбираем небольшое число x
0
и строим последовательность чисел
{x
n
}, n = 0, , 1, 2, ..., определяя каждое следующее x
n+1
по формуле
x
n+1
= (x
2
n
− 1) (mod n).
2. Одновременно на каждом шаге i вычисляем Н.О.Д d числа n и
всевозможных разностей |x
i
− x
j
|, где j < i.
3. Когда будет найдем d =Н.О.Д.(n, |x
i
−x
j
|), отличный от 1, вычисление
заканчивается. Найденное d является делителем n. Если n/d не
является простым числом, то процедуру можно продолжить, взяв
вместо n число n/d.
Глава 2. Криптостойкость RSA. Алгоритмы факторизации                         56

     2. Строим последовательность простых чисел 2 < 3 < 5 < ... < pm ,
       меньших B и последовательность степеней ai такую, что pai i < B .
                             ∏m      ai
     3. Полагаем число R =      i=1 qi .   Если p является B –степенно-гладким,
       то R делится на p.

     4. Выбираем    случайным      образом      числа   P   и   Q   и   строим
       последовательность чисел Люка, пока не вычислим uR .

     5. Далее вычислим Н.О.Д.(n, uR ) = d. Если 1 < d < n, то задача решена.

Доказано, что если Q взаимно просто с p и
                          ( 2       )
                            P − 4Q
                                       = −1,
                               p
то     свойства    последовательности        Люка    обеспечивают   нахождение
нетривиального делителя числа n.


3.4. ρ-метод Полларда
        Этот метод был разработан Джоном Поллардом в 1975 г. Пусть n –
число, которое следует разложить. ρ-метод Полларда работает следующим
образом:

     1. Выбираем небольшое число x0 и строим последовательность чисел
       {xn }, n = 0, , 1, 2, ..., определяя каждое следующее xn+1 по формуле
       xn+1 = (x2n − 1) (mod n).

     2. Одновременно на каждом шаге i вычисляем Н.О.Д d числа n и
       всевозможных разностей |xi − xj |, где j < i.

     3. Когда будет найдем d =Н.О.Д.(n, |xi −xj |), отличный от 1, вычисление
       заканчивается. Найденное d является делителем n. Если n/d не
       является простым числом, то процедуру можно продолжить, взяв
       вместо n число n/d.

Страницы