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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Простые алгоритмы факторизации 58
Если 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
}. (2.24)
При B
2
= cB
1
и k = 2 уравнения (2.24) приобретут вид:
p
B
1
< r < min{B
1
,
p
cB
1
}.
Поскольку значение границы B
2
обычно выбирается так, чтобы
выполнялось B
2
≤ B
2
1
, последнее уравнение эквивалентно
p
B
1
< r < c
1
p
B
1
, где c
1
=
√
c. (2.25)
Общая доля чисел, удовлетворяющих (2.25), невелика и значительно
меньше числа простых чисел из интервала (B
1
, B
2
), поэтому ими можно
пренебречь. Однако, если не пренебрегать этими числами и добавить в
алгоритм дополнительный цикл по элементам r, удовлетворяющим условию
(2.25), общее время алгоритма увеличится незначительно. Поскольку
размер наибольшей степени q
t
сильно зависит от степени гладкости числа
p − 1, поэтому эффективность (p − 1)–метода Полларда сильно зависит
от исходного числа n, изменяясь в широких пределах при различных
n одинаковой длины. Поэтому одной из рекомендаций метода RSA
является выбор n так, чтобы p − 1 имел хотя-бы один большой делитель,
превышающий размер границы B
2
, до которой возможно выполнение
реальных вычислений по (p −1)–методу Полларда.
Скажем несколько слов о выборе исходного значения параметра
a. Если p − 1 имеет большое число различных делителей, то
найдется много различных чисел a < n, для которых a
k
≡ 1 (modp)
Глава 2. Простые алгоритмы факторизации                                      58

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

                  rk−1 ≤ B,     B1 < rk < B2 ,

откуда
               1/k                          1/k
             B1      < p < min{B 1/(k−1) , B2 }.                         (2.24)
При B2 = cB1 и k = 2 уравнения (2.24) приобретут вид:
             p                   p
               B1 < r < min{B1 , cB1 }.

      Поскольку значение границы B2 обычно выбирается так, чтобы
выполнялось B2 ≤ B12 , последнее уравнение эквивалентно
           p              p             √
             B1 < r < c1 B1 , где c1 = c.                                (2.25)

      Общая доля чисел, удовлетворяющих (2.25), невелика и значительно
меньше числа простых чисел из интервала (B1 , B2 ), поэтому ими можно
пренебречь. Однако, если не пренебрегать этими числами и добавить в
алгоритм дополнительный цикл по элементам r , удовлетворяющим условию
(2.25), общее время алгоритма увеличится незначительно. Поскольку
размер наибольшей степени q t сильно зависит от степени гладкости числа
p − 1, поэтому эффективность (p − 1)–метода Полларда сильно зависит
от исходного числа n, изменяясь в широких пределах при различных
n одинаковой длины. Поэтому одной из рекомендаций метода RSA
является выбор n так, чтобы p − 1 имел хотя-бы один большой делитель,
превышающий размер границы B2 , до которой возможно выполнение
реальных вычислений по (p − 1)–методу Полларда.
      Скажем несколько слов о выборе исходного значения параметра
a.   Если   p − 1       имеет    большое    число   различных   делителей,   то
найдется много различных чисел a < n, для которых ak ≡ 1 (modp)

Страницы