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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 4. Метод квадратичного решета 130
оценивается величиной
T (n) = e
c
√
ln n ln ln n
при c ∈ (1, 2). (4.113)
Обозначим через L(k, n) функцию
L
n
(α; c) = exp
(c + o(1))(ln n)
α
(ln ln n)
1−α
, (4.114)
тогда оценка производительности метода квадратичного решета перепишется
в виде
T (n) = L
n
(1/2; c) = exp
(c + o(1))(ln n)
1/2
(ln ln n)
1/2
, (4.115)
4.6. Пример факторизации методом квадратичного
решета
Рассмотрим следующий пример факторизации натурального числа.
Пусть n = 750513679, m ≈
√
n = 27396, a = n − m
2
= −27137. Полином
просеивания (4.95) получает вид:
q(x) = x
2
+ 54792x − 27137 (4.116)
Замечание. Для таких маленьких чисел n оценка (4.111) является
завышенной. Действительно, значение B равное exp
p
2 ln n ln ln n)
≈ 10
4
слишком велико для нашего примера. Установим значение B равным 100.
I. Инициализация
1. Определим B = 100. Число простых чисел, не превышающих B ,
равно 25. Для каждого такого такого p найдем остаток n
p
= n mod p и
вычислим символ Лежандра g = Leg(n
p
, p). Если g <> 1, выбросим p из
факторной базы. После выполнения такой фильтрации останется 14 простых
чисел
F B = {2, 3, 5, 11, 17, 23, 29, 43, 47, 53, 59, 61, 67, 83}.
2. Для каждого элемента p факторной базы найдем, пользуясь
алгоритм Шенкса, корень уравнения x
2
≡ n
p
(modp), где n
p
= n mod p,
Глава 4. Метод квадратичного решета                                           130

оценивается величиной
                     √
                    c ln n ln ln n
           T (n) = e                 при c ∈ (1, 2).                       (4.113)

         Обозначим через L(k, n) функцию

                  Ln (α; c) = exp (c + o(1))(ln n)α (ln ln n)1−α ,
                                                                
                                                                           (4.114)

тогда оценка производительности метода квадратичного решета перепишется
в виде
                                                                
                                                   1/2       1/2
         T (n) = Ln (1/2; c) = exp (c + o(1))(ln n) (ln ln n)      ,       (4.115)


4.6. Пример            факторизации                    методом   квадратичного
        решета
     Рассмотрим следующий пример факторизации натурального числа.
                        √
Пусть n = 750513679, m ≈ n = 27396, a = n − m2 = −27137. Полином
просеивания (4.95) получает вид:

                             q(x) = x2 + 54792x − 27137                    (4.116)

     Замечание. Для таких маленьких чисел n оценка
                                                 p    (4.111) является
                                                                  
завышенной. Действительно, значение B равное exp   2 ln n ln ln n) ≈ 104
слишком велико для нашего примера. Установим значение B равным 100.
         I. Инициализация
         1. Определим B = 100. Число простых чисел, не превышающих B ,
равно 25. Для каждого такого такого p найдем остаток np = n mod p и
вычислим символ Лежандра g = Leg(np , p). Если g <> 1, выбросим p из
факторной базы. После выполнения такой фильтрации останется 14 простых
чисел
            F B = {2, 3, 5, 11, 17, 23, 29, 43, 47, 53, 59, 61, 67, 83}.

         2. Для каждого элемента p факторной базы найдем, пользуясь
алгоритм Шенкса, корень уравнения x2 ≡ np (mod p), где np = n mod p,

Страницы