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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Простые алгоритмы факторизации 68
2.6. Факторизация с использованием непрерывных
дробей
Один из методов факторизации основан на использовании непрерывных
дробей. Рассмотрим это важное понятие.
Пусть α — вещественное положительное число. Обозначим буквой q
0
наибольшее целое число, не превосходящее α. При нецелом α имеем α =
q
0
+
1
α
1
, α
1
> 1. Точно так же при нецелых α
1
, . . . , α
s−1
имеем
α
1
= q
1
+
1
α
2
, α
2
> 1,
. . .
α
s−1
= q
s−1
+
1
α
s
, α
s
> 1.
Эта процедура даем нам разложение α в непрерывную дробь:
α = q
0
+
1
q
1
+
1
q
2
+ . . . +
1
q
s−1
+
1
α
s
. (2.33)
Будем использовать запись α = [q
0
, q
1
, q
2
, ... q
s−1
] для сокращенного
обозначения формулы (2.33).
Если α — иррациональное, то и всякое α
s
— иррациональное, и
указанный процесс может быть неограниченно продолжен. Если же число α
— рационально, то процесс будет конечен и может быть выполнен с помощью
алгоритма Евклида.
Пример 1. Разложить дробь α =
72
25
.
A B A mod B q
i
= bA/Bc
72 25 22 2
25 22 3 1
22 3 1 7
3 1 0 3
Глава 2. Простые алгоритмы факторизации                                                            68

2.6. Факторизация                       с       использованием                           непрерывных
         дробей
        Один из методов факторизации основан на использовании непрерывных
дробей. Рассмотрим это важное понятие.
         Пусть α — вещественное положительное число. Обозначим буквой q0
наибольшее целое число, не превосходящее α . При нецелом α имеем α =
       1
q0 +   α1 ,   α1 > 1. Точно так же при нецелых α1 , . . . , αs−1 имеем
                                                    1
                                  α1 = q 1 +        α2 ,   α2 > 1,
                                  ...
                                                           1
                                  αs−1 = qs−1 +            αs ,   αs > 1.
Эта процедура даем нам разложение α в непрерывную дробь:

                                                             1
                              α = q0 +                                               .          (2.33)
                                                                   1
                                            q1 +
                                                                          1
                                                   q2 + . . . +
                                                                                1
                                                                       qs−1 +
                                                                                αs
Будем использовать запись α = [q0 , q1 , q2 , ... qs−1 ] для сокращенного
обозначения формулы (2.33).
         Если α — иррациональное, то и всякое αs — иррациональное, и
указанный процесс может быть неограниченно продолжен. Если же число α
— рационально, то процесс будет конечен и может быть выполнен с помощью
алгоритма Евклида.

                                                                  72
       Пример 1. Разложить дробь α =                              25

.
              A    B A mod B qi = bA/Bc
              72 25      22                 2
              25 22      3                  1
              22   3     1                  7
              3    1     0                  3

Страницы