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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Простые алгоритмы факторизации 57
Поскольку все значения b
δ
i
mod n заранее вычислены, то для
вычисления очередного значения c
i+1
достаточно одной операции
умножения и вычисления остатка по модулю n. Поэтому вторая стадия
алгоритма Полларда выполняется очень быстро.
Оценка эффективности (p − 1)–метода Полларда
Сделаем расчет времени работы алгоритма при условии, что параметры
B
1
и B
2
выбраны. Время выполнения первой стадии зависит от числа
простых чисел и их степеней на интервале [2; B]. Число простых чисел
оценивается величиной π(B
1
), приближенно равной по теореме Чебышева
числу B
1
/ ln B
1
. Для каждой степени p
r
, меньшей B , производится r
возведений в степень по модулю по алгоритму, описанному на стр. 13, и
требует log
2
p ≤ log
2
B
1
операций возведения в квадрат и умножений по
модулю числа n. Поэтому общее число операций можно оценить величиной
O(B
1
log B
1
log
2
N). Метод очень быстро находит простые факторы малой
и средней величины (до 20-25 десятичных цифр). Текущим рекордом для
(p −1)–метода является простой делитель числа 960
119
−1, состоящий из 66
десятичных цифр, установленный Т. Нохара (T. Nohara) в 2006 г.
Использование второй стадии позволяет увеличить эффективность
метода. По оценке Монтгомери, вторая стадия алгоритма требует
O(log
2
B
2
) + O(log q
π(B
1
)
) + 2(π(B
2
) − π(B
1
))
умножений по модулю n и вычислений Н.О.Д. с n. Отбрасывая слагаемые
меньшего порядка, получим оценку O(π(B
2
)).
Условие сходимости (p − 1)–метода Полларда
Пусть p–наименьший из делителей n и q
t
–наибольшая степень
простого числа, входящего в разложение p−1. Иначе говоря, q
t
максимально
среди всех степеней q
t
i
i
|p − 1. Отметим, что оценка сложности (p − 1)–
алгоритма определяется не размером факторизуемого числа n, а размером
сомножителя q
t
чисел p − 1 для p |n.
Глава 2. Простые алгоритмы факторизации                                     57

      Поскольку все значения bδi mod n заранее вычислены, то для
вычисления    очередного    значения     ci+1   достаточно    одной   операции
умножения и вычисления остатка по модулю n. Поэтому вторая стадия
алгоритма Полларда выполняется очень быстро.

Оценка эффективности (p − 1)–метода Полларда

     Сделаем расчет времени работы алгоритма при условии, что параметры
B1 и B2 выбраны. Время выполнения первой стадии зависит от числа
простых чисел и их степеней на интервале [2; B]. Число простых чисел
оценивается величиной π(B1 ), приближенно равной по теореме Чебышева
числу B1 / ln B1 . Для каждой степени pr , меньшей B , производится r
возведений в степень по модулю по алгоритму, описанному на стр. 13, и
требует log2 p ≤ log2 B1 операций возведения в квадрат и умножений по
модулю числа n. Поэтому общее число операций можно оценить величиной
O(B1 log B1 log2 N ). Метод очень быстро находит простые факторы малой
и средней величины (до 20-25 десятичных цифр). Текущим рекордом для
(p − 1)–метода является простой делитель числа 960119 − 1, состоящий из 66
десятичных цифр, установленный Т. Нохара (T. Nohara) в 2006 г.
      Использование второй стадии позволяет увеличить эффективность
метода. По оценке Монтгомери, вторая стадия алгоритма требует

               O(log2 B2 ) + O(log qπ(B1 ) ) + 2(π(B2 ) − π(B1 ))

умножений по модулю n и вычислений Н.О.Д. с n. Отбрасывая слагаемые
меньшего порядка, получим оценку O(π(B2 )).

Условие сходимости (p − 1)–метода Полларда

      Пусть p–наименьший из делителей n и q t –наибольшая степень
простого числа, входящего в разложение p−1. Иначе говоря, q t максимально
среди всех степеней qiti | p − 1. Отметим, что оценка сложности (p − 1)–
алгоритма определяется не размером факторизуемого числа n, а размером
сомножителя q t чисел p − 1 для p | n.

Страницы