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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Простые алгоритмы факторизации 56
Вторая стадия (p-1)–алгоритма Полларда
Если в результате первого этапа алгоритм не выдает требуемого
делителя, то можно либо увеличить границу B
1
, либо начать вторую стадию
работы алгоритма.
Вторая стадия алгоритма предполагает, что существует только один
простой множитель q числа p − 1, значение которого больше границы B
1
.
Выберем новую границу B
2
B
1
, например, B
2
= B
2
. Обозначим через b
число a
M(B)
mod n, вычисленное на первой стадии работы алгоритма.
Выпишем последовательность q
0
< q
1
< ... < q
s
всех простых
чисел на интервале [B; B
2
]. Для построения этого множества можно
воспользоваться решетом Эратосфена, либо решетом Аткина (см.гл.1).
Поскольку наличие в последовательности {q
i
} нескольких составных
чисел не испортит работы алгоритма, можно выполнить только частичное
просеивание, отсеяв числа, кратные небольшим простым числам. Это ускорит
общую работу алгоритма.
Если искомый множитель 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. (2.23)
Глава 2. Простые алгоритмы факторизации                                    56

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

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

Страницы