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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Простые алгоритмы факторизации 71
где P
0
= rQ − P , Q
0
= (D − (r ·Q −P )
2
)/Q = (D − (P
0
)
2
)/Q.
Это дает нам реккурентные формулы для вычисления
последовательностей {P
n
}, {Q
n
} и {q
n
}:
P
0
= −B, Q
0
= 2B, r
0
=
"
P
0
+
√
D
Q
0
#
,
P
j+1
= r
j
· Q
j
− P
j
, Q
j+1
= (D − P
2
j+1
)/Q
j
, r
j+1
=
"
P
j+1
+
√
D
Q
j+1
#
.
(2.41)
Теперь подходящие дроби для корня α можно вычислить по формулам:
δ
0
= r
0
, δ
1
= r
0
+
1
r
1
=
1 + r
0
· r
1
r
1
,
δ
j+1
=
p
j+1
q
j+1
=
r
j+1
· p
j
+ p
j−1
r
j+1
· q
j
+ q
j−1
(2.42)
Отметим, что для частного случая α =
√
n, следует взять D = n, P
0
= 0,
Q
0
= 1. Можно также для сокращения выкладок на один шаг, взять сразу
P
0
= [
√
D], Q
0
= D . Для вычисления целой части r
j+1
в формулах (2.42)
необходимо брать приближение
√
D ≈ m = [
√
D] при Q
j
> 0, и
√
D ≈ m+1
при Q
j
< 0.
Замечание. Поскольку, все члены последовательностей {P
j
} и {P
j
}
ограничены сверху [
√
D], то число различных пар (P
j
, Q
j
)–конечно, и
найдется номер k такой, что (P
0
, Q
0
) = (P
k
, Q
k
). Наименьшее из таких k
называется периодом последовательности непрерывных дробей.
2.7. Уравнение Пелла
Уравнением Пелла называется диофантово уравнение
x
2
− ny
2
= ±1 (2.43)
Решение этого уравнения из-за ошибки Эйлера приписывается англичанину
Джону Пеллу (J. Pell 1611-1685), хотя общее решение этого уравнения
было впервые найдено в Европе другим англичанином, лордом Вильямсом
Браункером (Williams Brouncker 1620–1684), который использовал это
Глава 2. Простые алгоритмы факторизации                                            71

где P 0 = rQ − P , Q0 = (D − (r · Q − P )2 )/Q = (D − (P 0 )2 )/Q.
       Это       дает    нам      реккурентные          формулы     для   вычисления
последовательностей {Pn }, {Qn } и {qn }:
                          "     √ #
                            P0 + D
P0 = −B, Q0 = 2B, r0 =                ,
                               Q0
                                                              "     √ #
                                   2                          Pj+1 + D
Pj+1 = rj · Qj − Pj , Qj+1 = (D − Pj+1 )/Qj , rj+1          =           .
                                                                 Qj+1
                                                                                (2.41)
Теперь подходящие дроби для корня α можно вычислить по формулам:
                             1    1 + r0 · r1
  δ0 = r0 ,      δ1 = r0 +      =             ,
                             r1       r1
              pj+1   rj+1 · pj + pj−1
   δj+1 =          =                                                            (2.42)
              qj+1   rj+1 · qj + qj−1
                                                  √
Отметим, что для частного случая α =                  n, следует взять D = n, P0 = 0,
Q0 = 1. Можно также для сокращения выкладок на один шаг, взять сразу
      √
P0 = [ D], Q0 = D . Для вычисления целой части rj+1 в формулах (2.42)
                            √          √                 √
необходимо брать приближение D ≈ m = [ D] при Qj > 0, и D ≈ m + 1
при Qj < 0.
      Замечание. Поскольку, все члены последовательностей {Pj } и {Pj }
                   √
ограничены сверху [ D], то число различных пар (Pj , Qj )–конечно, и
найдется номер k такой, что (P0 , Q0 ) = (Pk , Qk ). Наименьшее из таких k
называется периодом последовательности непрерывных дробей.


2.7. Уравнение Пелла
      Уравнением Пелла называется диофантово уравнение

                      x2 − ny 2 = ±1                                            (2.43)

Решение этого уравнения из-за ошибки Эйлера приписывается англичанину
Джону Пеллу (J. Pell 1611-1685), хотя общее решение этого уравнения
было впервые найдено в Европе другим англичанином, лордом Вильямсом
Браункером (Williams Brouncker 1620–1684), который использовал это

Страницы