Материал: Zastosuvannya_teoriyi_chisel_u_kriptografiyi_metodi

a

= [q , q

,..., q

, q

].

b

1

2

n

n+1

Зробимо позначення:

δ

= q ;

δ

= q +

1

;

δ

= q +

1

;...;

1

2

3

1

1

q2

1

+

1

q2

q3

δs

= q1 +

1

q2 +

1

q3 + ...

M

...... +

1

qs−1 +

1

qs

Такі дроби мають назву підхідні дроби. Кожний з цих

дробів є наближенням до раціонального числа

a

.

b

Щоб скласти алгоритм обчислення будь-якого підхідного

дробу δ

, позначимо P = 1,

Q = 0 та

a

=

Ps

. Зауважимо, що у

i

0

0

b

Qs

δs

кожному підхідному

дробі

достатньо

qs−1

замінити

на

qs−1

+

1

. Тоді

qs

q

P

1

q × q +1

Pq

2

+ P P × q

2

+ P

P

δ

1

=

1

=

1

; δ

2

= q +

=

1

2

=

1

0

=

1

0

=

2

;

1

Q1

1

q2

q2

1× q2 + 0 Q1 × q2 + Q0

Q2

q

+

1

P + P

q

q q P + P + P q

2

1

0

δ3

=

3

=

2 3 1

1

0 3

=

1

q2 q3Q1 + Q1 + Q0 q3

q2

+

Q1 + Q0

q3

=

q

( Pq + P ) + P

=

q P + P

3

1 2 0 1

3 2 1 .

q3

(Q1q2 + Q0 ) + Q1

q3Q2 + Q1

δs

=

qs × Ps−1 + Ps−2

=

Ps

Qs

qs ×Qs−1 + Qs−2

Отже, для обчислення будь-якого

δi , i > 1

нам необхідно

обчислити

Pi = qi × Pi−1 + Pi−2 та

Qi = qi ×Qi−1 + Qi−2 .

Тоді підходящий дріб δi

=

Pi

Qi

Для обчислення зручно застосувати схему:

і

0

1

2

....

і-2

і-1

і

...

n-1

n

qi

q1

q2

....

qi−2

qi−1

qi

....

qi−1

qn

1

q1

P2

....

Pi−2

Pi−1

Pi

....

Pn−1

a

Qi

0

1

Q2

....

Qi−2

Qi−1

Qi

....

Qn−1

b

алгоритмом Евкліда:

151 = 13×11+ 8,

q1 = 11,

13 = 8 ×1+ 5,

q2 = 1,

8 = 5 ×1+ 3,

q3 = 1,

5 = 3×1+ 2,

q4 = 1,

3 = 2 ×1+1,

q5 = 1,

2 = 1× 2,

q6

= 2,

Отже,

151

= 11+

1

1

13

1+

1

1+

1

1+

1

1+

2

+ 0

151

= [11,1,1,1,1, 2].

13

i

0

1

2

3

4

5

6

qi

11

1

1

1

1

2

Pi

1

11

12

23

35

58

151

Qi

0

1

1

2

3

5

13

q = 11;

P = q = 11;

1

1

1

q

2

= 1;

P = q

2

× P + P = 1×11+1 = 12 ;

2

1

0

q = 1;

P = q × P + P = 1×12 +11 = 23 ;

3

3

3

2

1

q4

= 1;

P4

= q4 × P3 + P2 = 1× 23 +12 = 35 ;

q5 = 1;

P5 = q5 × P4 + P3 = 1×35 + 23 = 58 ;

q6

= 2;

P6

= q6 × P5 + P4 = 2 ×58 + 35 = 151 .

q1 = 11;

Q1 = 1;

q2 = 1;

Q2

= q2 ×Q1 + Q0 = 1×1+ 0 = 1;

q3 = 1

Q3 = q3 ×Q2 + Q1 = 1×1+1 = 2 ;

q4

= 1;

Q4

= q4 ×Q3 + Q2 = 1× 2 +1 = 3 ;

q5

= 1;

Q5 = q5 ×Q4 + Q3 = 1×3 + 2 = 5 ;

q6

= 2;

Q6 = q6 ×Q5 + Q4 = 2 ×5 + 3 = 13 .

13

δ1

P

δ2 =

P

δ3 =

P

23

1

=

1

= 11;

2

= 12;

3

=

= 11

;

Q1

Q3

2

Q2

2

δ4

=

P4

=

35

= 11

2

; δ5

=

P5

=

58

= 11

3

.

Q4

Q5

3

3

5

5

Аналіз таблиці показує,

що дріб

a

завжди розташований

b

Властивості схеми розкладання.

1.

Для усіх i > 0 маємо: PQ

- Q P

= (-1)i .

i i−1

i i−1

2.

Для усіх i > 1 маємо δi -δi−1

=

(-1)i

.

QiQi−1

3.

Для усіх 1 < i < n раціональний

нескорочуваний дріб

і

0

1

2

3

4

5

6

qi

2

1

3

4

1

2

1

2

3

11

47

58

163

Qi

0

1

1

4

17

21

59

Останній стовпчик таблиці дасть

P6

=

a

=

163

_

Q6

b 59