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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Криптостойкость RSA. Алгоритмы факторизации 49
методом Ферма.
3.2. (p − 1)–метод Полларда
Этот метод был разработан английским математиком Джоном
Поллардом в 1974 г. и опубликован в [32].
Пусть n—факторизуемое число, а 1 < p < n– его простой делитель.
Согласно малой теореме Ферма, для любого a, 1 ≤ a < p, выполняется
условие a
p−1
≡ 1( mod p).
Это же сравнение выполнится, если вместо степени p − 1 взять
произвольное натуральное число M кратное p−1, т.к. если M = (p−1)·k , то
a
M
= (a
p−1
)
k
≡ 1
k
≡ 1( mod p). Последнее условие эквивалентно a
M
−1 = pr
для некоторого целого r. Отсюда, если p является делителем числа n, тогда
p является делителем наибольшего общего делителя Н.О.Д.(n, a
M
− 1) и
совпадет с Н.О.Д.(n, a
M
− 1), если a
M
− 1 < n. Пусть
p −1 = p
r
1
i
· p
r
2
2
· ... · p
r
t
t
. (3.22)
Идея (p − 1)–метод Полларда состоит в чтобы выбрать M в виде
произведения как можно большего числа простых сомножителей или их
степеней так, чтобы M делилось на каждый сомножитель p
r
i
i
, входящий
в разложение (3.22). Тогда, Н.О.Д.(n, a
M
− 1) даст искомый делитель.
Алгоритм состоит из двух стадий:
Первая стадия (p-1)–алгоритма Полларда
1. Сначала выберем границу B
1
.
2. Определим множество P , состоящее из простых чисел и их степеней,
меньших границы B
1
:
P = {p
r
1
1
, p
r
2
2
, ... p
r
k
k
}, p
r
i
i
< B
1
.
3. Вычислим произведение
M = M(B
1
) =
∏
p
r
i
i
∈P
p
r
i
i
Глава 2. Криптостойкость RSA. Алгоритмы факторизации                   49

методом Ферма.


3.2. (p − 1)–метод Полларда
       Этот метод был разработан английским математиком Джоном
Поллардом в 1974 г. и опубликован в [32].
      Пусть n—факторизуемое число, а 1 < p < n– его простой делитель.
Согласно малой теореме Ферма, для любого a, 1 ≤ a < p, выполняется
условие ap−1 ≡ 1( mod p).
      Это же сравнение выполнится, если вместо степени p − 1 взять
произвольное натуральное число M кратное p−1, т.к. если M = (p−1)·k , то
aM = (ap−1 )k ≡ 1k ≡ 1( mod p). Последнее условие эквивалентно aM − 1 = pr
для некоторого целого r . Отсюда, если p является делителем числа n, тогда
p является делителем наибольшего общего делителя Н.О.Д.(n, aM − 1) и
совпадет с Н.О.Д.(n, aM − 1), если aM − 1 < n. Пусть
                                                 t
             p − 1 = pri 1 · pr22 · ... · prt .                     (3.22)

      Идея (p − 1)–метод Полларда состоит в чтобы выбрать M в виде
произведения как можно большего числа простых сомножителей или их
степеней так, чтобы M делилось на каждый сомножитель pri i , входящий
в разложение (3.22). Тогда, Н.О.Д.(n, aM − 1) даст искомый делитель.
Алгоритм состоит из двух стадий:

      Первая стадия (p-1)–алгоритма Полларда

1. Сначала выберем границу B1 .
2. Определим множество P , состоящее из простых чисел и их степеней,
меньших границы B1 :

        P = {pr11 , pr22 , ... prkk }, pri i < B1 .

3. Вычислим произведение
                                    ∏
              M = M (B1 ) =                  pri i
                                    r
                                   pi i ∈P

Страницы