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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Простые алгоритмы факторизации 72
уравнение для получения приближения числа π непрерывными дробями.
Однако, гораздо ранее это уравнение уже решалось индийским математиком
и астрономом Брахмагуптой (Brahmagupta 598–668).
Решения уравнения Пелла при 1 в правой части определяются
следующей теоремой:
Теорема 2.2. Пусть n > 0–натуральное число, не являющееся полным
квадратом. Уравнение Пелла x
2
− ny
2
= 1 всегда имеет множество
решений (x, y), наименьшее из которое является подходящей дробью
{x
k
/y
k
}, сходящихся к действительному числу
√
n, где номер k –период
последовательности непрерывных дробей. Любое другое решение уравнения
является степенью наименьшего решения: x
t
+ y
t
√
n = (x
0
+ y
0
·
√
n)
t
,
t = 0, 1, 2, ... .
Пример 3. Решить уравнение x
2
− ny
2
= 1 при n = 14.
(1)
√
14 = 3+(
√
14−3), (2)
1
√
14 − 3
=
3 +
√
14
5
= 1+
√
14 − 2
5
,
(3)
5
√
14 − 2
=
2 +
√
14
2
= 2+
√
14 − 2
2
, (4)
2
√
14 − 2
=
2 +
√
14
5
= 1+
√
14 − 3
5
,
(5)
5
√
14 − 3
= 3+
√
14 = 6+(
√
14−3).
Период последовательности непрерывных дробей равен 4. Найдем
теперь подходящую дробь для k = 4 (последнее вычисление не учитывается):
3 +
1
1 +
1
2 +
1
1
= 3 +
1
1 +
1
3
= 3 +
3
4
=
15
4
.
Отсюда x
1
= 15, y
1
= 4 – наименьшее решение уравнения. Проверим
решение
15
2
− 14 · 4
2
= 225 − 224 = 1. Все решения можно найти, возводя в
степень t двучлен (x
0
+ y
0
√
n), t = 0, 1 2, 3 ... . Например, при t = 2
получим (15 + 4
√
14)
2
= 449 + 120
√
14, т.е. (x
2
, y
2
) = (449, 120).
Отметим, что для вычисления подходящей дроби мы использовали
последовательность целых частей дробей α
i
{r
i
} = {3, 1, 2, 1, 6 ... }. Эта
Глава 2. Простые алгоритмы факторизации                                  72

уравнение для получения приближения числа π непрерывными дробями.
Однако, гораздо ранее это уравнение уже решалось индийским математиком
и астрономом Брахмагуптой (Brahmagupta 598–668).
        Решения уравнения Пелла при 1 в правой части определяются
следующей теоремой:

Теорема 2.2. Пусть n > 0–натуральное число, не являющееся полным
квадратом. Уравнение Пелла x2 − ny 2 = 1 всегда имеет множество
решений (x, y), наименьшее из которое является подходящей дробью
                                             √
{xk /yk }, сходящихся к действительному числу n, где номер k –период
последовательности непрерывных дробей. Любое другое решение уравнения
                                               √                √
является степенью наименьшего решения: xt + yt n = (x0 + y0 · n)t ,
t = 0, 1, 2, ... .

      Пример 3. Решить уравнение x2 − ny 2 = 1 при n = 14.
                                                  √        √
    √          √                      1       3 + 14         14 − 2
(1) 14 = 3+( 14−3),          (2) √         =          = 1+          ,
                                    14 − 3       5            5
                   √       √                            √          √
       5       2 + 14        14 − 2          2       2 + 14           14 − 3
(3) √        =        = 2+          , (4) √        =         = 1+            ,
      14 − 2      2           2             14 − 2      5              5
       5          √       √
(5) √        = 3+ 14 = 6+( 14−3).
      14 − 3
      Период последовательности непрерывных дробей равен 4. Найдем
теперь подходящую дробь для k = 4 (последнее вычисление не учитывается):
                 1                    1              3 15
     3 +              1       =3 +        1   =3 +     = .
            1+       2+   1          1+   3
                                                     4  4
                          1


        Отсюда x1 = 15, y1 = 4 – наименьшее решение уравнения. Проверим
решение
152 − 14 · 42 = 225 − 224 = 1. Все решения можно найти, возводя в
                           √
степень t двучлен (x0 + y0 n), t = 0, 1 2, 3 ... . Например, при t = 2
               √                √
получим (15 + 4 14)2 = 449 + 120 14, т.е. (x2 , y2 ) = (449, 120).
        Отметим, что для вычисления подходящей дроби мы использовали
последовательность целых частей дробей αi {ri } = {3, 1, 2, 1, 6 ... }. Эта

Страницы