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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 3. Эллиптические кривые 91
1. Для каждого простого числа p < B
1
найдем наибольшую степень r
такую, что p
r
< B
1
. Выполним цикл for (j = 0; j < r; j + +) P = p · P ,
в результате которого точка P домножится на p
r
. Каждое умножение на p
выполняется с помощью алгоритма нахождения кратного точки, описанного
на с.86.
2. Продолжим вычисление до тех пор, пока не будут пройдены все
простые числа, меньшие B
1
, или не найдется шаг, на котором выполнится
условие Н.О.Д (n, P ) = d > 1.
Если выполнится последнее условие, то искомый делитель n найден.
Иначе, либо увеличиваем B
1
и повторяем все заново, либо переходим
ко второй стадии алгоритма.
Вторая стадия алгоритма
На второй стадии алгоритма предполагается, что остался один большой
простой множитель q > B
1
такой, что домножение точки P , полученной в
конце первого этапа, приведет к выполнению условия (3.65).
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
, либо не выполнится условие (3.65).
Как и в (p −1)–методе Полларда, чтобы вычислить очередную точку
q
i+1
P достаточно прибавить к ранее вычисленной точке q
i
P точку δ
i
P ,
где δ
i
= q
i+1
−q
i
. Поскольку простые числа расположены достаточно близко
друг к другу, различных точек вида δ
i
P будем немного. Их можно вычислить
заранее и расположить в некотором массиве. Тогда каждое новое вычисление
q
i
P можно выполнить с помощью только одной операции сложения. Поэтому
вторая часть алгоритма выполняется очень быстро.
В наиболее простом варианте реализации второй стадии можно
вычислить только одну точку 2 P и прибавлять ее к точке q
1
P пока не
получим требуемое условие (3.65).
Глава 3. Эллиптические кривые                                                91

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

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

       На второй стадии алгоритма предполагается, что остался один большой
простой множитель q > B1 такой, что домножение точки P , полученной в
конце первого этапа, приведет к выполнению условия (3.65).

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

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

       Как и в (p − 1)–методе Полларда, чтобы вычислить очередную точку
qi+1 P достаточно прибавить к ранее вычисленной точке qi P точку δi P ,
где δi = qi+1 − qi . Поскольку простые числа расположены достаточно близко
друг к другу, различных точек вида δi P будем немного. Их можно вычислить
заранее и расположить в некотором массиве. Тогда каждое новое вычисление
qi P можно выполнить с помощью только одной операции сложения. Поэтому
вторая часть алгоритма выполняется очень быстро.
       В наиболее простом варианте реализации второй стадии можно
вычислить только одну точку 2 P и прибавлять ее к точке q1 P пока не
получим требуемое условие (3.65).

Страницы