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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Простые алгоритмы факторизации 70
Вычисление подходящих дробей для квадратных
иррациональностей
Квадратными иррациональностями будем называться уравнения вида
Ax
2
+ Bx + C = 0, где A, B, C ∈ Z, и D = B
2
− 4AC > 0. (2.34)
Корни уравнения (2.34) вычисляются по формуле
α =
−B ±
√
D
2A
. (2.35)
Вводя обозначения P = −B , Q = 2A и рассматривая только больший
корень, придем к выражению
α =
P +
√
D
Q
(2.36)
Обозначим через m = [
√
D]. Тогда первая подходящая дробь для
корня α имеет вид:
δ
0
=
P + m
Q
(2.37)
Найдем вторую подходящую дробь для корня α. Для этого выделим
целую часть r = [P +
√
D/Q] из (2.35). Дробь, обратная к остатку, будет
иметь вид:
α
1
=
1
α − q
0
=
Q
P +
√
D −r · Q)
=
Q
√
D −(r · Q − P )
(2.38)
Домножим числитель и знаменатель последней дроби на выражение,
сопряженное к знаменателю. Получим:
α
1
=
Q · (
√
D + (r · Q − P ))
D −(r · Q − P )
2
(2.39)
Поскольку Q|(D − P
2
), то знаменатель делится на Q, и после
сокращения получим:
α
1
=
√
D + (r · Q − P )
Q
0
=
P
0
+
√
D
Q
0
(2.40)
Глава 2. Простые алгоритмы факторизации                              70

     Вычисление        подходящих          дробей   для      квадратных
иррациональностей

     Квадратными иррациональностями будем называться уравнения вида

   Ax2 + Bx + C = 0, где A, B, C ∈ Z, и D = B 2 − 4AC > 0.        (2.34)

      Корни уравнения (2.34) вычисляются по формуле
                     √
               −B ± D
           α=            .                                        (2.35)
                  2A
      Вводя обозначения P = −B , Q = 2A и рассматривая только больший
корень, придем к выражению
                     √
                 P+ D
             α=                                                   (2.36)
                    Q
                           √
      Обозначим через m = [ D]. Тогда первая подходящая дробь для
корня α имеет вид:
                     P +m
              δ0 =                                                (2.37)
                       Q
     Найдем вторую подходящую дробь для корня α . Для этого выделим
                    √
целую часть r = [P + D/Q] из (2.35). Дробь, обратная к остатку, будет
иметь вид:
             1           Q                 Q
    α1 =          =    √           =√                             (2.38)
           α − q0   P + D − r · Q)    D − (r · Q − P )
      Домножим числитель и знаменатель последней дроби на выражение,
сопряженное к знаменателю. Получим:
                      √
                 Q · ( D + (r · Q − P ))
           α1 =                                                   (2.39)
                    D − (r · Q − P )2

      Поскольку Q|(D − P 2 ), то знаменатель делится на Q, и после
сокращения получим:
           √                       √
             D + (r · Q − P ) P 0 + D
      α1 =                   =                                    (2.40)
                  Q0              Q0

Страницы