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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Простые алгоритмы факторизации 80
3. Определим исходные значения параметров P, Q, r:
P
0
= 0, Q
0
= 1, r
0
= P
1
= b
√
nc, Q
1
= n−r
2
0
, r
1
= b2r
0
/Q
1
c.
II. Первый цикл. Последующие значения параметров P и Q будем вычислять
по формулам формулами (2.44)-(2.46) вычисления частичных дробей в методе
факторизации непрерывных дробей CFRAC (раздел 2.6):
P
k
= r
k−1
·Q
k−1
−P
k−1
, Q
k
= Q
k−2
+(P
k−1
−P
k
)·r
k−1
, r
k
=
P
k
+ b
√
nc
Q
k
, k ≥ 2.
(2.56)
Продолжим вычисления коэффициентов P
k
, Q
k
и r
k
, k = 2, 3, ... до тех пор,
пока не найдем Q
k
, являющееся полным квадратом. Это должно произойти
при некотором четном k. Пусть Q
k
= d
2
для целого d > 0. Перейдем к
следующему циклу.
III. Второй цикл.
Начнем цикл вычислений новых параметров P
0
j
, Q
0
j
, r
0
j
, j = 0, 1, 2, ....
Формулы для реализации второго цикла останутся такими же, как раньше.
Изменятся только начальные значения параметров P
0
, Q
0
и r
0
:
P
0
0
= −P
k
, Q
0
0
= d, r
0
0
=
P
0
0
+ b
√
nc
Q
0
0
, P
0
1
= r
0
0
·Q
0
0
−P
0
0
, Q
0
1
= (N−P
0
2
1
)/Q
0
0
.
P
0
j
= r
0
j−1
·Q
0
j−1
−P
0
j−1
, Q
0
j
= Q
0
j−2
+(P
0
j−1
−P
0
j
)·r
0
j−1
, r
0
j
=
$
P
0
j
+ b
√
nc
Q
0
j
%
, j ≥ 2.
Вычисление следует продолжать, пока два подряд идущих значения
P
0
j
и P
0
j+1
не окажутся равными. Тогда, значение Q
j
даст искомый делитель
числа n.
Описание алгоритма Шенкса закончено.
Пример факторизации по методу Шенкса
Выполним факторизацию нашего примера из предыдущего раздела
n = 11 111.
Инициализация. Найдем n mod 4 = 3, r
0
= b
√
nc = 105.
Глава 2. Простые алгоритмы факторизации                                               80

   3. Определим исходные значения параметров P, Q, r :
                                 √
      P0 = 0, Q0 = 1, r0 = P1 = b nc, Q1 = n−r02 , r1 = b2r0 /Q1 c.


II. Первый цикл. Последующие значения параметров P и Q будем вычислять
по формулам формулами (2.44)-(2.46) вычисления частичных дробей в методе
факторизации непрерывных дробей CFRAC (раздел 2.6):
                                                                  √ 
                                                             Pk + b nc
Pk = rk−1 ·Qk−1 −Pk−1 , Qk = Qk−2 +(Pk−1 −Pk )·rk−1 , rk =             , k ≥ 2.
                                                                 Qk
                                                                        (2.56)
Продолжим вычисления коэффициентов Pk , Qk и rk , k = 2, 3, ... до тех пор,
пока не найдем Qk , являющееся полным квадратом. Это должно произойти
при некотором четном k . Пусть Qk = d2 для целого d > 0. Перейдем к
следующему циклу.

III. Второй цикл.

Начнем цикл вычислений новых параметров Pj0 , Q0j , rj0 , j = 0, 1, 2, ....
Формулы для реализации второго цикла останутся такими же, как раньше.
Изменятся только начальные значения параметров P 0 , Q0 и r0 :
                               0       √ 
                               P   + b   nc                                       0
P00 = −Pk , Q00 = d, r00 =       0
                                      0      , P10 = r00 ·Q00 −P00 , Q01 = (N −P12 )/Q00 .
                                    Q0
                                                                 $
                                                                      0
                                                                            √ %
                                                                    P j + b  nc
Pj0 = rj−1
       0
           ·Q0j−1 −Pj−1
                    0
                        , Q0j = Q0j−2 +(Pj−1
                                          0
                                             −Pj0 )·rj−1
                                                     0
                                                         , rj0 =                , j ≥ 2.
                                                                         Q0j
       Вычисление следует продолжать, пока два подряд идущих значения
Pj0 и Pj+1
       0
           не окажутся равными. Тогда, значение Qj даст искомый делитель
числа n.
       Описание алгоритма Шенкса закончено.

Пример факторизации по методу Шенкса

       Выполним факторизацию нашего примера из предыдущего раздела
n = 11 111.
                                         √
Инициализация. Найдем n mod 4 = 3, r0 = b nc = 105.

Страницы