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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Простые алгоритмы факторизации 74
для квадратного корня
√
n по формулам:
P
k
=
0, если k = 0
b
√
nc, если k = 1
r
k−1
· Q
k−1
− P
k−1
, если k ≥ 2.
(2.44)
Q
k
=
0, если k = 0
n − r
2
0
, если k = 1
Q
k−2
+ r
k−1
· (P
k−1
− P
k
), если k ≥ 2.
(2.45)
r
k
=
(
b
√
nc, если k = 0
b
r
0
+P
k
Q
k
c, если k ≥ 2.
(2.46)
p
k
=
r
0
, если k = 0
1 + r
0
· r
1
, если k = 1
r
k
· p
k−1
+ p
k−2
, если k ≥ 2.
(2.47)
q
k
=
1, если k = 0
r
1
, если k = 1
r
k
· q
k−1
+ q
k−2
, если k ≥ 2.
(2.48)
Процесс продолжается до тех пор, пока выражение
S
i
= p
2
i
− q
2
i
· n
не окажется равным полному квадрату S
i
= B
2
. Тогда, q
2
i
· n = p
2
i
− B
2
=
(p
i
+B)(p
i
−B), и с большой долей вероятности n будем иметь нетривиальный
общий делитель либо c (p
i
+B), либо с (p
i
−B). Этот делитель можно найти,
вычисляя Н.О.Д.(n, p
i
±B ). Если же нам не повезет, то следует продолжить
поиск следующего квадрата Q
i
, По теореме 2.2 такое решение когда-нибудь
появится.
Приведем теперь пример разложения числа n = 11111 с
использованием метода непрерывных дробей:
Глава 2. Простые алгоритмы факторизации                                      74
                       √
для квадратного корня n по               формулам:
        
         0,√                             если k = 0
        
        
   Pk =    b nc,                          если k = 1                    (2.44)
        
         rk−1 · Qk−1 − Pk−1 ,
        
                                          если k ≥ 2.

          
           0,                                 если k = 0
          
          
  Qk =      n − r02 ,                          если k = 1               (2.45)
          
           Qk−2 + rk−1 · (Pk−1 − Pk ),
          
                                               если k ≥ 2.
          ( √
           b nc,           если k = 0
  rk =                                                                  (2.46)
            b r0Q+P
                  k
                    k
                      c,   если k ≥ 2.

          
           r0 ,                      если k = 0
          
          
   pk =     1 + r0 · r1 ,             если k = 1                        (2.47)
          
           rk · pk−1 + pk−2 ,
          
                                      если k ≥ 2.

          
           1,                        если k = 0
          
          
   qk =     r1 ,                      если k = 1                        (2.48)
          
           rk · qk−1 + qk−2 ,
          
                                      если k ≥ 2.

      Процесс продолжается до тех пор, пока выражение

                 Si = p2i − qi2 · n

не окажется равным полному квадрату Si = B 2 . Тогда, qi2 · n = p2i − B 2 =
(pi +B)(pi −B), и с большой долей вероятности n будем иметь нетривиальный
общий делитель либо c (pi +B), либо с (pi −B). Этот делитель можно найти,
вычисляя Н.О.Д.(n, pi ± B ). Если же нам не повезет, то следует продолжить
поиск следующего квадрата Qi , По теореме 2.2 такое решение когда-нибудь
появится.
      Приведем теперь пример разложения числа                n   =   11111    с
использованием метода непрерывных дробей:

Страницы