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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Криптостойкость RSA. Алгоритмы факторизации 50
4. Выберем произвольное число a, например 2, и вычислим a
M
mod n.
5. Вычислим Н.О.Д.(n, a
M
−1), который, если повезет даст искомый делитель
числа n.
Пример. Факторизовать n = 10 001. Выберем B = 10, тогда,
M(B
1
) = 2
3
· 3
2
· 5 · 7 = 2520. Вычислим, 2
2520
mod 10 001 = 3579. Найдем,
Н.О.Д.(n, a
M
− 1) = Н.О.Д.(10 001, 3578) = 73.
Заметим, что при большом значении B
1
число M(B
1
) может оказаться
чрезвычайно большим (оно сравнимо с B
1
!). В таких случаях лучше разбить
полное произведение M(B
1
) на l блоков, состоящих из примерно одинакового
числа сомножителей, и вычислив числа M
i
как произведение элементов
блока i, представить M(B) в виде M
1
· M
2
· ... · M
l
. Затем, можно
вычислить a
M(B)
как предел последовательности {a
i
}, где a
1
= a
M
1
(mod
n), а последующие a
i
вычисляются по формуле:
a
i+1
= a
M
i+1
i
mod n, i < l.
В этом случае, все вычисления будут выполняться с числами, сравнимыми
по модулю с числом n.
Вторая стадия (p-1)–алгоритма Полларда
Если в результате первого этапа алгоритм не выдает требуемого
делителя, то можно либо увеличить границу B
1
, либо начать вторую стадию
работы алгоритма.
Вторая стадия алгоритма предполагает, что существует только один
простой множитель q числа p − 1, значение которого больше границы B
1
.
Выберем новую границу B
2
≫ B
1
, например, B
2
= B
2
1
. Обозначим через b
число a
M(B)
mod n, вычисленное на первой стадии работы алгоритма.
Выпишем последовательность q
0
< q
1
< ... < q
s
всех простых
чисел на интервале [B; B
2
]. Для построения этого множества можно
воспользоваться решетом Эратосфена, либо решетом Аткина (см.гл.1).
Поскольку наличие в последовательности {q
i
} нескольких составных
чисел не испортит работы алгоритма, можно выполнить только частичное
Глава 2. Криптостойкость RSA. Алгоритмы факторизации                     50

4. Выберем произвольное число a, например 2, и вычислим aM mod n.
5. Вычислим Н.О.Д.(n, aM −1), который, если повезет даст искомый делитель
числа n.

      Пример. Факторизовать n = 10 001. Выберем B = 10, тогда,
M (B1 ) = 23 · 32 · 5 · 7 = 2520. Вычислим, 22520 mod 10 001 = 3579. Найдем,
Н.О.Д.(n, aM − 1) = Н.О.Д.(10 001, 3578) = 73.

      Заметим, что при большом значении B1 число M (B1 ) может оказаться
чрезвычайно большим (оно сравнимо с B1 !). В таких случаях лучше разбить
полное произведение M (B1 ) на l блоков, состоящих из примерно одинакового
числа сомножителей, и вычислив числа Mi как произведение элементов
блока i, представить M (B) в виде M1 · M2 · ... · Ml . Затем, можно
вычислить aM (B) как предел последовательности {ai }, где a1 = aM1 (mod
n), а последующие ai вычисляются по формуле:
                   Mi+1
           ai+1 = ai      mod n, i < l.

В этом случае, все вычисления будут выполняться с числами, сравнимыми
по модулю с числом n.

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

      Если в результате первого этапа алгоритм не выдает требуемого
делителя, то можно либо увеличить границу B1 , либо начать вторую стадию
работы алгоритма.
      Вторая стадия алгоритма предполагает, что существует только один
простой множитель q числа p − 1, значение которого больше границы B1 .
Выберем новую границу B2 ≫ B1 , например, B2 = B12 . Обозначим через b
число aM (B) mod n, вычисленное на первой стадии работы алгоритма.
      Выпишем последовательность q0 < q1 < ... < qs всех простых
чисел на интервале [B; B2 ]. Для построения этого множества можно
воспользоваться решетом Эратосфена, либо решетом Аткина (см.гл.1).
      Поскольку наличие в последовательности {qi } нескольких составных
чисел не испортит работы алгоритма, можно выполнить только частичное

Страницы