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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Простые алгоритмы факторизации 55
степеней так, чтобы M делилось на каждый сомножитель p
r
i
i
, входящий
в разложение (2.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
) =
Y
p
r
i
i
∈P
p
r
i
i
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.
Глава 2. Простые алгоритмы факторизации                                  55

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

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

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

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

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

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.

Страницы