Файл: Zastosuvannya_teoriyi_chisel_u_kriptografiyi_metodi.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.06.2024
Просмотров: 48
Скачиваний: 0
x ≡ c1 |
(mod m1 ) , |
|
||
x ≡ c |
(mod m |
), |
(2) |
|
|
2 |
2 |
|
|
K K K K |
). |
|
||
x ≡ c |
(mod m |
|
||
|
k |
k |
|
|
Отже, розв’язавши систему (2), ми тим самим знайдемо розв’язок системи (1).
Відповідь про існування та структуру розв’язку системи (2)
дає Китайська теорема про остачі:
Нехай дані k попарно простих чисел m1 , m2 ,..., mk та чисел
c1, c2 ,..., ck , таких, що 0 ≤ ci ≤ mi − 1, i = |
1, k |
. Тоді |
існує таке |
єдине ціле число α , у якого остача від ділення на mi |
становить |
||
ci (тобто α ≡ ci (mod mi )). |
|
||
Доведення
Доводити будемо побудовою числа α . Позначимо через M НСК усіх модулів. Оскільки вони попарно прості, то M = m1m2 ...mk . Далі побудуємо систему чисел
|
|
= |
M |
= |
m1m2 ...mi ...mk |
= m m ...m m |
...m , i = |
|
. |
|
M |
i |
1, k |
||||||||
|
|
|||||||||
|
|
mi |
|
|
1 2 i−1 i+1 |
k |
||||
|
|
|
|
mi |
|
|
|
|||
Кожне M i є взаємно простим з числом mi , тому для нього існує обернений елемент
M |
i |
−1 |
≡ M |
ϕ(mi )−1 mod(m ). |
|
|
|
|
|
|
|
|||||
|
|
|
i |
|
|
|
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
k |
|
|
|
|
|
|
|
Побудуємо число α = ∑ M i M i −1ci . |
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
i=1 |
|
|
|
|
|
|
|
Тоді розв’язком системи (2) буде клас лишків, що |
||||||||||||||||
задовольняє конгруенції: |
|
|
|
|
|
|
|
|
||||||||
x ≡ α(mod M ) . |
|
|
|
|
|
|
|
|
|
|
||||||
Дійсно, підставимо α у першу конгруенцію системи (2): |
||||||||||||||||
M |
1 |
M |
−1c + M |
2 |
M |
−1c |
2 |
+ ... + M |
k |
M |
k |
−1c |
k |
≡ c |
(mod m ). |
|
|
|
1 1 |
|
|
2 |
|
|
|
1 |
1 |
||||||
56
|
Усі доданки, починаючи з другого, діляться на m1 , оскільки |
||||||||
|
|
i = |
|
|
як множник. Тому всі ці |
||||
цей модуль наявний у |
Mi , |
2,k |
|||||||
доданки |
конгруентні |
0 |
за |
модулем m1 . Добуток |
|||||
M |
M |
−1 ≡ 1(mod m ) за |
побудовою, |
(M |
, m ) = 1 . Залишається |
||||
1 |
|
1 |
1 |
|
|
|
|
1 |
1 |
тотожна конгруенція c1 ≡ c1 (mod m1 ).
У другому рівнянні неконгруентним 0 за модулем m2 буде
тільки доданок M 2 M 2 −1c2 . Отже, α є розв’язком для другої
конгруенції і т. д.
Розв’язок підійде до кожної конгруенції через свою структуру.
Висновок
Розв’язок системи (2) існує, і це є клас чисел x = α + Mt, t Z .
Наведемо приклад практичного розв’язання систем з невеликою кількістю конгруенцій.
Приклад
Розв’язати систему конгруенцій
743x ≡ 16 (mod13),≡ ( )59x 128 mod 5 ,
136x ≡ 82 (mod 3).
Розв’язок
Маємо систему з трьох конгруенцій за простими модулями. КРОК 1. Спрощуємо систему. Замінимо числа в кожній
конгруенції на найменші лишки за відповідними модулями.
2x ≡ 3(mod13),≡ ( )4x 3 mod 5 ,
x ≡ 1(mod 3).
Зведемо систему до вигляду (2):
57
2x º 3 +13 |
(mod13) 2x º 16 (mod13) |
x º 8(mod13) , |
||
|
|
|
|
(2,13)=1 |
4x º 3 + 5(mod 5) 4x º 8(mod 5) |
x º 2 (mod 5), |
|||
|
|
|
(4,5)=1 |
|
x º 1(mod 3). |
|
|
||
Отримали зведену систему |
|
|
||
x º 8(mod13) , |
|
|
||
|
º 2 (mod 5), |
|
|
|
x |
|
|
||
|
º 1(mod 3). |
|
|
|
x |
|
|
||
Розв’язок для такої системи конгруенцій за Китайською |
||||
теоремою існує і єдиний. |
|
x º 8(mod13) Таку |
||
Розглянемо |
першу конгруенцію |
|||
конгруенцію можна записати через рівність: |
||||
|
|
x = 8 +13t1 . |
|
(*) |
Оскільки x є розв’язком для кожної конгруенції, підставимо |
||||
його до другої конгруенції системи і визначимо значення t1 : |
||||
8 +13t1 = 2 (mod 5) 13t1 º -6 (mod 5)3t1 º -6 + 5 ×3(mod 5) 3t1 º 9 (mod 5) .
Оскільки (3,5) =1 поділимо обидві частини конгруенції на 3:
t1 º 3(mod 5) , а оскільки t1 = 3 + 5t2 . |
|
Підставимо t1 до (*): |
|
x = 8 +13(3 + 5t2 ) = 8 + 39 +13 ×5t2 = 47 +13 ×5t2 |
а оскільки |
x º 47(mod13×5). |
|
x = 47 +13×5t2 . |
(**) |
Отриманий x підставимо у третю конгруенцію: |
|
47+13×5t2 º 1(mod 3) 65t2 º -46 (mod 3)
-t2 º -1(mod 3) t2 º1(mod 3) t2 =1+ 3t3 .
Підставимо t2 у (**):
58
x = 47 +13 ×5(1 + 3t3 ) = 47 + 65 +13 ×5 ×3t3 =112 +13 ×5 ×3t3 .
Отже, можна записати розв’язок:
x º112(mod13×5 ×3), а оскільки x º112(mod195).
Відповідь
x º112(mod195).
Перевірка
|
|
|
2 ×112 = 224 = 13×17 + 3 2 ×112 º 3(mod13) , |
|
|||||||||
|
|
|
|
×112 = 448 |
º 3(mod 5), |
|
|
|
|
||||
|
|
|
4 |
|
|
|
|
||||||
|
|
|
112 = 3×37 +1 112 º 1(mod 3). |
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Система розв’язана правильно. |
|
|
|
|||||||
Зауваження |
|
|
|
|
|
|
|
|
|||||
|
|
1. |
Якщо |
у |
системі |
(1) |
для |
будь-якої |
конгруенції |
||||
ai x º bi (mod mi ), |
|
(ai , mi ) = d > 1, d | bi |
, |
то |
скорочуючи |
||||||||
конгруенцію |
|
на |
d , |
переходимо |
до |
конгруенції |
|||||||
|
a |
i |
|
b |
|
m |
|
|
|
|
|
|
|
|
|
x º |
i |
mod |
i |
|
і вже |
цю |
конгруенцію |
підставляємо до |
|||
|
|
|
|
|
|||||||||
|
d |
d |
d |
|
|
|
|
|
|
|
|||
системи.
Якщо для нової системи збереглася попарна простота модулів, то вона має єдиний розв’язок, згідно з китайською теоремою про остачі. Але в цьому випадку i - та конгруенція має
d |
розв’язків: |
x º c + t |
|
mi |
(mod m ), t |
|
= |
0, (d -1), |
отже, |
||||
|
|
|
|||||||||||
|
|
|
i |
j d |
i |
|
j |
|
|
|
|
||
необхідно розглянути відповідно d |
систем, у кожній з яких на |
||||||||||||
i − му місці буде стояти відповідний розв’язок конгруенції. |
|||||||||||||
2. |
Система |
з двох рівнянь виду |
x º c1 |
(mod m1 ), |
у разі |
||||||||
x º c |
(mod m ). |
||||||||||||
(m1 , m2 ) = d > 1 |
|
|
|
|
|
|
|
|
2 |
2 |
|
||
буде |
мати |
|
розв’язок |
тільки за умови, що |
|||||||||
d | c2 - c1 . В іншому |
разі |
система |
не |
сумісна. Якщо |
умова |
||||||||
59
виконана і розв’язок є, він буде знайдений за модулем, який дорівнює НСК m1 та m2 .
3. Якщо система складається з k > 2 конгруенцій з модулями, що мають НСД>1, то перевірку необхідно проводити поступово. У разі, коли хоча б одна з отриманих конгруенцій у ході розв’язання не має розв’язку, то і вся система несумісна. Якщо розв’язок є, то це буде конгруенція за НСК усіх модулів.
ЗАВДАННЯ ДЛЯ ВИКОНАННЯ ІНДИВІДУАЛЬНИХ КОНТРОЛЬНИХ РОБІТ ЗА ТЕМОЮ 4.
Завдання 8
Знайти обернений елемент для числа a за модулем m .
1. |
2. |
3. |
4. |
5. |
6. |
a = 142, |
a = 137, |
a = 95, |
a = 37, |
a = 37, |
a = 113, |
m = 439 |
m = 932 |
m = 308 |
m = 107 |
m = 217 |
m = 311 |
|
|
|
|
|
|
7. |
8. |
9. |
10. |
11. |
12. |
a = 221, |
a = 41, |
a = 31, |
a = 93, |
a = 23, |
a = 137, |
m = 367 |
m = 101 |
m = 142 |
m = 133 |
m = 691 |
m = 323 |
|
|
|
|
|
|
13. |
14. |
15. |
16. |
17. |
18. |
a = 97, |
a = 101, |
a = 103, |
a = 91, |
a = 137, |
a = 59, |
m = 323 |
m = 931 |
m = 1031 |
m = 323 |
m = 837 |
m = 311 |
|
|
|
|
|
|
19. |
20. |
21. |
22. |
23. |
24. |
a = 97, |
a = 113, |
a = 89, |
a = 47, |
a = 67, |
a = 64, |
m = 433 |
m = 923 |
m = 323 |
m = 311 |
m = 691 |
m = 531 |
|
|
|
|
|
|
25. |
26. |
27. |
28. |
29. |
30. |
a = 64, |
a = 71, |
a = 83, |
a = 93, |
a = 128, |
a = 29, |
m = 743 |
m = 531 |
m = 323 |
m = 531 |
m = 1025 |
m = 531 |
|
|
|
|
|
|
Завдання
Розв’язати систему конгруенцій, попередньо спростивши її.
60
