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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Простые алгоритмы факторизации 61
факторизуемого числа n, и выполнено разложение p + 1
p + 1 =
k
Y
i=1
q
a
i
i
.
Обозначим через B = max{q
a
i
i
|1 ≤ i ≤ k}. По-прежнему будем
называть натуральное число r B –степенно-гладким, если наибольшая
степень сомножителя p
a
i
i
в разложении r на простые множители, не
превышает B . Таким образом, определенное выше число B является
наименьшим числом, для которого p + 1 является B –степенно-гладким.
Отметим, что поскольку p не известно, то и B так же не известно.
Алгоритм Вильямса заключается в следующем:
1. Выбираем некоторое число B , являющее верхней границей для
рассматриваемых простых чисел и их степеней.
2. Строим последовательность простых чисел 2 < 3 < 5 < ... < p
m
,
меньших B и последовательность степеней a
i
такую, что p
a
i
i
< B .
3. Полагаем число R =
Q
m
i=1
q
a
i
i
. Если p является B –степенно-гладким,
то R делится на p.
4. Выбираем случайным образом числа P и Q и строим
последовательность чисел Люка, пока не вычислим u
R
.
5. Далее вычислим Н.О.Д.(n, u
R
) = d. Если 1 < d < n, то задача решена.
Доказано, что если Q взаимно просто с p и
P
2
− 4Q
p
= −1,
то свойства последовательности Люка обеспечивают нахождение
нетривиального делителя числа n.
2.4. ρ-метод Полларда
Этот метод был разработан Джоном Поллардом в 1975 г. Пусть n –
число, которое следует разложить. ρ-метод Полларда работает следующим
образом:
Глава 2. Простые алгоритмы факторизации                                            61

факторизуемого числа n, и выполнено разложение p + 1
                                            k
                                            Y
                                 p+1=             qiai .
                                            i=1

Обозначим через B        =   max{qiai |1     ≤      i      ≤   k}. По-прежнему будем
называть натуральное число r B –степенно-гладким, если наибольшая
степень сомножителя pai i в разложении r на простые множители, не
превышает B . Таким образом, определенное выше число B является
наименьшим числом, для которого p + 1 является B –степенно-гладким.
Отметим, что поскольку p не известно, то и B так же не известно.
        Алгоритм Вильямса заключается в следующем:
     1. Выбираем некоторое число B , являющее верхней границей для
       рассматриваемых простых чисел и их степеней.

     2. Строим последовательность простых чисел 2 < 3 < 5 < ... < pm ,
       меньших B и последовательность степеней ai такую, что pai i < B .
                             Qm      ai
     3. Полагаем число R =      i=1 qi .   Если p является B –степенно-гладким,
       то R делится на p.

     4. Выбираем    случайным     образом          числа       P   и   Q   и   строим
       последовательность чисел Люка, пока не вычислим uR .

     5. Далее вычислим Н.О.Д.(n, uR ) = d. Если 1 < d < n, то задача решена.
Доказано, что если Q взаимно просто с p и
                           2       
                            P − 4Q
                                       = −1,
                               p
то     свойства    последовательности        Люка          обеспечивают    нахождение
нетривиального делителя числа n.


2.4. ρ-метод Полларда
        Этот метод был разработан Джоном Поллардом в 1975 г. Пусть n –
число, которое следует разложить. ρ-метод Полларда работает следующим
образом:

Страницы