Файл: Zastosuvannya_teoriyi_chisel_u_kriptografiyi_metodi.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.06.2024
Просмотров: 54
Скачиваний: 0
алгоритмом Евкліда: |
|
|
|
|
|
|
|
|
||||||||
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 |
Для заповнення таблиці обчислимо чисельники підхідних дробів Pi і знаменники Qi .
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 ; |
||||
18
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 . |
|
Дріб 151 має такі підхідні дроби:
|
|
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 раціональний |
|
нескорочуваний дріб |
||
α= a завжди розміщений між δi−1 та δi , ближче до δi . b
Використовуючи властивості підхідних дробів, можна знайти розв’язок у цілих числах рівняння
19
ax + by = 1.
Дійсно, якщо розкласти на підхідні дроби раціональне число
a , то за властивістю 1. з останніх двох стовпчиків таблиці b
можна записати:
a ×Qn−1 - b ×Qn = (-1)n .
Якщо n – парне, то (-1)n = 1 . У цьому випадку розв’язок рівняння буде таким: x = Qn−1 , y = -Qn .
Якщо n – непарне, то (-1)n = -1. У цьому випадку x = -Qn−1 , y = Qn .
Приклад
Маємо неперервний дріб [2,1, 3, 4,1, 2] .
Побудувати відповідне найменше раціональне число a і b
знайти розв’язок рівняння ax + by = 1.
Розв’язання
1. Будуємо таблицю для обчислення підхідних дробів і згідно з схемою обчислюємо всі підхідні дроби.
і |
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 |
|
||
нескорочуваний дріб, якому відповідає даний в умові задачі неперервний дріб.
2. a = 163, b = 59, ax + by = 1.
20
З останніх двох стовпчиків таблиці, використовуючи властивість 1 підходящих дробів, можна записати
163× 21- 58 ×59 = (-1)6 = 1, або a × 21+ (-58) ×b = 1 .
Отже, розв’язком рівняння ax + by = 1 буде пара чисел x = 21, y = −58 .
ЗАВДАННЯ ДЛЯ ВИКОНАННЯ ІНДИВІДУАЛЬНИХ КОНТРОЛЬНИХ РОБІТ ЗА ТЕМОЮ 1
ЗАВДАННЯ 1
Використовуючи алгоритм Евкліда, знайти НСД та НСК двох чисел.
1. |
1232, 1672. |
2. |
1 329, 2 136. |
|
3. |
1 359, 8 211. |
|||||||
|
|
|
|
|
|
|
|
||||||
4. |
5 427, 32 877. |
5. |
5 894, 3 437. |
|
6. |
12 606, |
6494. |
||||||
|
|
|
|
|
|
|
|
||||||
7. |
29 719, 76 501. |
8. |
162 891, |
32 176. |
9. |
469 459, |
579 203. |
||||||
|
|
|
|
|
|
|
|||||||
10. |
738 089, |
11. |
179 370 199, |
12. |
3 327 449, |
|
|||||||
3 082 607. |
4 345 121. |
|
|
6 314 153. |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|||||
13. |
12 870, 7 650. |
14. |
41 382, |
103 |
818. |
15. |
3 640, |
14 300. |
|||||
|
|
|
|
|
|
|
|
||||||
16. |
24 700, 33 250. |
17. |
7 650, 25 245. |
18. |
56 595, |
82 |
467. |
||||||
|
|
|
|
|
|
|
|
|
|
||||
19. |
35 574, 192 423. |
20. |
25 245, |
129 |
591. |
21. |
10 140, |
92 |
274. |
||||
|
|
|
|
|
|
|
|
||||||
22. |
36 372, 147 220. |
23. |
46 550, |
37 730. |
24. |
1 403, |
1 058. |
||||||
|
|
|
|
|
|
|
|
||||||
25. |
213 239, |
26. |
138 285, |
|
27. |
72 348, |
5 632. |
||||||
512 525. |
356 405. |
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|||||
28. |
354 295, |
29. |
24 789, |
35 286. |
30. |
32 893, |
72 |
568. |
|||||
543 440. |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
21
