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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Простые алгоритмы факторизации 69
72
25
= 2 +
1
1 +
1
7 +
1
3
= [2, 1, 7, 3]
Величины δ
0
= q
0
, δ
1
= [q
0
, q
1
], . . . , δ
s
= [q
0
, q
1
, ..., q
s
], . . .
называются подходящими дробями. Для любых действительных α
существует последовательность подходящих дробей такая что α = lim
n→∞
δ
n
.
Пример 2. Приблизить α =
√
14 последовательностью
подходящих дробей
Решение. Обозначим через q
0
= [
√
14] = 3. Тогда
α = 3+(
√
14−3) = q
0
+
1
α
1
.
α
1
=
1
√
14 − 3
=
√
14 + 3
5
= 1+
√
14 − 2
5
, q
1
= 1.
α
2
=
5
√
14 − 2
=
√
14 + 2
2
= 2+
√
14 − 2
2
, q
2
= 2.
α
3
=
2
√
14 − 2
=
√
14 + 2
5
= 1+
√
14 − 3
5
, q
3
= 1.
α
4
=
5
√
14 − 3
=
√
14+3 = 6+(
√
14−3), q
4
= 6.
Последовательность подходящих дробей имеет вид:
δ
0
= 3, δ
1
= 3+1/1 = 4, δ
2
= 3+
1
1 + 1/2
≈ 3.667, δ
3
= 3+
1
1 +
1
2+1/2
≈ 3.75,
δ
4
= 3
20
27
≈ 3.741 ....
Можно видеть, что четные члены этой последовательности дают
значение
√
14 с недостатком, а нечетные–с избытком, а разности |δ
s+1
− δ
s
|
убывают и стремятся к нулю.
Глава 2. Простые алгоритмы факторизации                                             69



72         1
   = 2+                   = [2, 1, 7, 3]
25      1 + 7 +1      1
                      3


         Величины δ0 = q0 , δ1 = [q0 , q1 ], . . . , δs = [q0 , q1 , ..., qs ], . . .
называются       подходящими        дробями.      Для    любых    действительных        α
существует последовательность подходящих дробей такая что α = limn→∞ δn .

                                                        √
         Пример 2.           Приблизить α =                 14 последовательностью
подходящих дробей
                                        √
         Решение. Обозначим через q0 = [ 14] = 3. Тогда
        √             1
α = 3+( 14−3) = q0 + .
                      α1
                √             √
        1         14 + 3        14 − 2
α1 = √        =          = 1+          , q1 = 1.
       14 − 3      5             5
                √             √
        5         14 + 2        14 − 2
α2 = √        =          = 2+          , q2 = 2.
       14 − 2      2             2
                √             √
        2         14 + 2        14 − 3
α3 = √        =          = 1+          , q3 = 1.
       14 − 2      5             5
        5       √            √
α4 = √        = 14+3 = 6+( 14−3), q4 = 6.
       14 − 3
      Последовательность подходящих дробей имеет вид:
                                              1                         1
δ0 = 3, δ1 = 3+1/1 = 4, δ2 = 3+                    ≈ 3.667, δ3 = 3+       1   ≈ 3.75,
                                           1 + 1/2                  1 + 2+1/2

      20
δ4 = 3   ≈ 3.741 ....
      27
      Можно видеть, что четные члены этой последовательности дают
         √
значение 14 с недостатком, а нечетные–с избытком, а разности |δs+1 − δs |
убывают и стремятся к нулю.

Страницы