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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 3. Эллиптические кривые 94
1. Для каждого простого числа p < B
1
найдем наибольшую степень r
такую, что p
r
< B
1
. Выполним цикл for (j = 0; j < r; j + +) P = p · P ,
в результате которого точка P домножится на p
r
. Каждое умножение на p
выполняется с помощью алгоритма нахождения кратного точки, описанного
на с.84.
2. Продолжим вычисление до тех пор, пока не будут пройдены все
простые числа, меньшие B
1
, или не найдется шаг, на котором выполнится
условие Н.О.Д ( n, P ) = d > 1.
Если выполнится последнее условие, то искомый делитель n найден.
Иначе, либо увеличиваем B
1
и повторяем все заново, либо переходим
ко второй стадии алгоритма.
Вторая стадия алгоритма
На второй стадии алгоритма предполагается, что число точек #EC
на выбранной ЭК имеет лишь один делитель q , превышающий границу 1-й
стадии B
1
.
1. Выберем новую границу B
2
, и выпишем все простые числа из
интервала [B
1
; B
2
] : {q
1
, q
2
, ..., q
m
}.
2. Будем последовательно вычислять точки q
1
·P, q
2
·P, q
3
·P, ... пока
не дойдем до границы B
2
, либо не выполнится условие (5.56).
Как и в (p −1)–методе Полларда, чтобы вычислить очередную точку
q
i+1
P достаточно прибавить к ранее вычисленной точке q
i
P точку δ
i
P ,
где δ
i
= q
i+1
−q
i
. Поскольку простые числа расположены достаточно близко
друг к другу, различных точек вида δ
i
P будем немного. Их можно вычислить
заранее и расположить в некотором массиве. Тогда каждое новое вычисление
S
i
= q
i
P можно выполнить с помощью только одной операции сложения.
Однако, чтобы не пройти точки q
i
P = ∞, требуется вычислять Н.О.Д.(n,
Z
i
), где Z
i
есть Z –координата т.q
i
P для каждого i, а каждая операция
вычисления Н.О.Д. эквивалента нескольким операциям сложения. Поэтому
мы рекомендуем на 2-й стадии ввести переменную P rodZ , первоначально
равную 1, а потом на каждом шаге i выполнять вычисление P rodZ = P rodZ·
Глава 3. Эллиптические кривые                                                94

       1. Для каждого простого числа p < B1 найдем наибольшую степень r
такую, что pr < B1 . Выполним цикл for (j = 0; j < r; j + +)        P = p·P,
в результате которого точка P домножится на pr . Каждое умножение на p
выполняется с помощью алгоритма нахождения кратного точки, описанного
на с.84.
       2. Продолжим вычисление до тех пор, пока не будут пройдены все
простые числа, меньшие B1 , или не найдется шаг, на котором выполнится
условие Н.О.Д (n, P ) = d > 1.
       Если выполнится последнее условие, то искомый делитель n найден.
       Иначе, либо увеличиваем B1 и повторяем все заново, либо переходим
ко второй стадии алгоритма.

           Вторая стадия алгоритма

       На второй стадии алгоритма предполагается, что число точек #EC
на выбранной ЭК имеет лишь один делитель q , превышающий границу 1-й
стадии B1 .

       1. Выберем новую границу B2 , и выпишем все простые числа из
интервала [B1 ; B2 ] : {q1 , q2 , ..., qm }.

       2. Будем последовательно вычислять точки q1 · P, q2 · P, q3 · P, ... пока
не дойдем до границы B2 , либо не выполнится условие (5.56).

       Как и в (p − 1)–методе Полларда, чтобы вычислить очередную точку
qi+1 P достаточно прибавить к ранее вычисленной точке qi P точку δi P ,
где δi = qi+1 − qi . Поскольку простые числа расположены достаточно близко
друг к другу, различных точек вида δi P будем немного. Их можно вычислить
заранее и расположить в некотором массиве. Тогда каждое новое вычисление
Si = qi P можно выполнить с помощью только одной операции сложения.
Однако, чтобы не пройти точки qi P = ∞, требуется вычислять Н.О.Д.(n,
Zi ), где Zi есть Z –координата т.qi P для каждого i, а каждая операция
вычисления Н.О.Д. эквивалента нескольким операциям сложения. Поэтому
мы рекомендуем на 2-й стадии ввести переменную P rodZ , первоначально
равную 1, а потом на каждом шаге i выполнять вычисление P rodZ = P rodZ·

Страницы