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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Криптостойкость RSA. Алгоритмы факторизации 52
модулю числа n. Поэтому общее число операций можно оценить величиной
O(B
1
log B
1
log
2
N). Метод очень быстро находит простые факторы малой
и средней величины (до 20-25 десятичных цифр). Текущим рекордом для
(p −1)–метода является простой делитель числа 960
119
−1, состоящий из 66
десятичных цифр, установленный Т. Нохара (T. Nohara) в 2006 г.
Использование второй стадии позволяет увеличить эффективность
метода. По оценке Монтгомери, вторая стадия алгоритма требует
O(log
2
B
2
) + O(log q
π(B
1
)
) + 2(π(B
2
) − π(B
1
))
умножений по модулю n и вычислений Н.О.Д. с n. Отбрасывая слагаемые
меньшего порядка, получим оценку O(π(B
2
)).
Условие сходимости (p − 1)–метода Полларда
Пусть p–наименьший из делителей n и q
t
–наибольшая степень
простого числа, входящего в разложение p−1. Иначе говоря, q
t
максимально
среди всех степеней q
t
i
i
|p − 1. Отметим, что оценка сложности (p − 1)–
алгоритма определяется не размером факторизуемого числа n, а размером
сомножителя q
t
чисел p − 1 для p |n.
Если q
t
≤ B
1
, тогда вычисление закончится на первом этапе
алгоритма. Иначе, для успеха алгоритма необходимо, чтобы выполнилось
q
t
≤ B
2
, а все степени простых делителей (p − 1) вида q
r
кроме последнего
были меньше B
1
. Кроме того необходимо, чтобы среди делителей p − 1 не
нашлось множителей вида r
k
при k ≥ 2, находящегося между B
1
и B
2
. Для
таких r
k
имеем два неравенства:
r
k−1
≤ B, B
1
< r
k
< B
2
,
откуда
B
1/k
1
< p < min{B
1/(k−1)
, B
1/k
2
}. (3.24)
При B
2
= cB
1
и k = 2 уравнения (3.24) приобретут вид:
√
B
1
< r < min{B
1
,
√
cB
1
}.
Глава 2. Криптостойкость RSA. Алгоритмы факторизации                     52

модулю числа n. Поэтому общее число операций можно оценить величиной
O(B1 log B1 log2 N ). Метод очень быстро находит простые факторы малой
и средней величины (до 20-25 десятичных цифр). Текущим рекордом для
(p − 1)–метода является простой делитель числа 960119 − 1, состоящий из 66
десятичных цифр, установленный Т. Нохара (T. Nohara) в 2006 г.
      Использование второй стадии позволяет увеличить эффективность
метода. По оценке Монтгомери, вторая стадия алгоритма требует

                O(log2 B2 ) + O(log qπ(B1 ) ) + 2(π(B2 ) − π(B1 ))

умножений по модулю n и вычислений Н.О.Д. с n. Отбрасывая слагаемые
меньшего порядка, получим оценку O(π(B2 )).

Условие сходимости (p − 1)–метода Полларда

         Пусть p–наименьший из делителей n и q t –наибольшая степень
простого числа, входящего в разложение p−1. Иначе говоря, q t максимально
среди всех степеней qiti | p − 1. Отметим, что оценка сложности (p − 1)–
алгоритма определяется не размером факторизуемого числа n, а размером
сомножителя q t чисел p − 1 для p | n.
      Если q t ≤ B1 , тогда вычисление закончится на первом этапе
алгоритма. Иначе, для успеха алгоритма необходимо, чтобы выполнилось
q t ≤ B2 , а все степени простых делителей (p − 1) вида q r кроме последнего
были меньше B1 . Кроме того необходимо, чтобы среди делителей p − 1 не
нашлось множителей вида rk при k ≥ 2, находящегося между B1 и B2 . Для
таких rk имеем два неравенства:

                   rk−1 ≤ B,   B 1 < r k < B2 ,

откуда
               1/k                           1/k
              B1     < p < min{B 1/(k−1) , B2 }.                      (3.24)

При B2 = cB1 и k = 2 уравнения (3.24) приобретут вид:
               √                 √
                B1 < r < min{B1 , cB1 }.

Страницы