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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Криптостойкость RSA. Алгоритмы факторизации 51
просеивание, отсеяв числа, кратные небольшим простым числам. Это ускорит
общую работу алгоритма.
Если искомый множитель p −1 равен q
i
, то для нахождения делителя
n, необходимо вычислить c
i
= b
q
i
mod n, и найти Н.О.Д.(n, с
i
− 1).
Поскольку, значение q неизвестно, мы должны выполнить последние
две операции с каждым числом q
i
из интервала [B
1
; B
2
]. Поллард
предложил следующий вариант организации этой процедуры. Обозначим
через δ
i
разность между соседними простыми числами δ
i
= q
i+1
− q
i
.
Возможные значения, принимаемые d
i
, лежат в небольшом множестве
D = {2, 4, ..., 2t}. Можно заранее вычислить все значения b
δ
mod n для
δ ∈ D и сохранить полученные числа в массиве. Вторая стадия алгоритма
выполняется следующим образом:
1. Вычислим сначала c
0
= b
q
0
mod n, и найдем d =Н.О.Д.(n, с
0
− 1).
2. Если d = 1, то вычислим следующее c
1
= b
q
1
mod n и
d =Н.О.Д.(n, с
1
− 1) и т.д.
3. Каждое последующее значение c
i+1
вычисляется по формуле
b
q
i+1
mod n = b
q
i
+δ
i
mod n = b
q
i
· b
δ
i
mod n = c
i
· b
δ
i
mod n. (3.23)
Поскольку все значения b
δ
i
mod n заранее вычислены, то для
вычисления очередного значения c
i+1
достаточно одной операции
умножения и вычисления остатка по модулю n. Поэтому вторая стадия
алгоритма Полларда выполняется очень быстро.
Оценка эффективности (p − 1)–метода Полларда
Сделаем расчет времени работы алгоритма при условии, что параметры
B
1
и B
2
выбраны. Время выполнения первой стадии зависит от числа
простых чисел и их степеней на интервале [2; B]. Число простых чисел
оценивается величиной π(B
1
), приближенно равной по теореме Чебышева
числу B
1
/ ln B
1
. Для каждой степени p
r
, меньшей B , производится r
возведений в степень по модулю по алгоритму, описанному на с. 26, и
требует log
2
p ≤ log
2
B
1
операций возведения в квадрат и умножений по
Глава 2. Криптостойкость RSA. Алгоритмы факторизации                          51

просеивание, отсеяв числа, кратные небольшим простым числам. Это ускорит
общую работу алгоритма.
      Если искомый множитель p − 1 равен qi , то для нахождения делителя
n, необходимо вычислить ci = bqi mod n, и найти Н.О.Д.(n, сi − 1).
Поскольку, значение q неизвестно, мы должны выполнить последние
две операции с каждым числом qi из интервала [B1 ; B2 ]. Поллард
предложил следующий вариант организации этой процедуры. Обозначим
через δi разность между соседними простыми числами δi = qi+1 − qi .
Возможные значения, принимаемые di , лежат в небольшом множестве
D = {2, 4, ..., 2t}. Можно заранее вычислить все значения bδ mod n для
δ ∈ D и сохранить полученные числа в массиве. Вторая стадия алгоритма
выполняется следующим образом:

      1. Вычислим сначала c0 = bq0 mod n, и найдем d =Н.О.Д.(n, с0 − 1).
      2. Если d = 1, то вычислим следующее c1                   = bq1 mod n и
d =Н.О.Д.(n, с1 − 1) и т.д.
      3. Каждое последующее значение ci+1 вычисляется по формуле

  bqi+1 mod n = bqi +δi mod n = bqi · bδi mod n = ci · bδi mod n.          (3.23)

      Поскольку все значения bδi mod n заранее вычислены, то для
вычисления     очередного     значения    ci+1   достаточно     одной   операции
умножения и вычисления остатка по модулю n. Поэтому вторая стадия
алгоритма Полларда выполняется очень быстро.

Оценка эффективности (p − 1)–метода Полларда

     Сделаем расчет времени работы алгоритма при условии, что параметры
B1 и B2 выбраны. Время выполнения первой стадии зависит от числа
простых чисел и их степеней на интервале [2; B]. Число простых чисел
оценивается величиной π(B1 ), приближенно равной по теореме Чебышева
числу B1 / ln B1 . Для каждой степени pr , меньшей B , производится r
возведений в степень по модулю по алгоритму, описанному на с. 26, и
требует log2 p ≤ log2 B1 операций возведения в квадрат и умножений по

Страницы