Kriptografik usullar

4-topshiriq. Berilgan matnni Kalit so’z yordamida (25 ta belgidan kam bo’lmagan matnni talaba o’zi tuzadi) shifrlang.
5-topshiriq. Berilgan matnni(matnni talaba o’zi tuzadi) Sehrli kvadrat usulida shifrlang. Guruh jurnalidagi tartibi k=1..13 bo’lganlar uchun jadval o’lchami 5*5(belgilar soni 25 tagacha(22 tadan kam emas) bo’lgan matnni talaba o’zi tuzadi), k=14..26 bo’lganlar uchun jadval o’lchami 6*6 (belgilar soni 36 tagacha(32 tadan kam emas) bo’lgan matnni talaba o’zi tuzadi, k=27..39 bo’lganlar uchun jadval o’lchami 7*7 (belgilar soni 49 tagacha(45 tadan kam emas) bo’lgan matnni talaba o’zi tuzadi deb olinadi.

27	29	2	4	13	36
9	11	20	22	31	18
32	25	7	3	21	23
14	16	34	30	12	5
28	6	15	17	26	19
1	24	33	35	8	1

Sehrli kvadrat(6*6)

4	29	12	37	20	45	28
35	11	36	19	44	27	3
10	42	18	43	26	2	34
41	17	49	25	1	33	9
16	48	24	7	32	8	40
47	23	6	31	14	39	15
22	5	30	13	38	21	46

Sehrli kvadrat(7*7)

3	16	9	22	15
20	8	21	14	2
7	25	13	1	19
24	12	5	18	6
11	4	17	10	23

Amaliy mashg’ulot 5
5-mavzu. Katta sonlarni ko’paytuvchilarga ajratish algoritmlari.
Reja:
5.1. Taqqoslama tushunchasi va uning xossalari.
5.2. Chegirmalar sinfi.
5.3. Katta sonlarni berilgan songa bo’lgandagi qoldiqni hisoblash


5.1. Taqqoslama tushunchasi va uning xossalari. a va b butun sonlarni butun musbat m soniga bo’lganda bir xil qoldiq qoladigan, ya’ni
a = mq₁ + r va b = mq₂ + r,
bo’lsa, a va b sonlar teng qoldiqdli yoki m modul bo’yicha o’zaro taqqoslanadigan sonlar deyiladi va quyidagicha yoziladi:
a b (mod m)
“a son b bilan m modul bo’yicha taqqoslanadi” deb o’qiladi.
Agar a b (mod m) bo’lsa, u holda a – b ayirma m ga qoldiqsiz bo’linadi, va
aksincha, agar a va b sonlarning ayirmasi m ga bo’linsa, u holda a b (mod m) o’rinli
bo’ladi (taqqoslamaning ma’nosi haqidagi teorema).
Har qanday butun son m modul bo’yicha o’zining qoldig’i bilan taqqoslanadi,
ya’ni, agar a = mq + r bo’lsa, u holda a r (mod m) bo’ladi.
Xususiy holda, agar r = 0 bo’lsa, u holda a 0 (mod m) bo’ladi; bu taqqoslama
m | a ekanligini, ya’ni m soni a ning bo’luvchisi ekanligini bildiradi, aksincha ham
o’rinli, agar m a bo’lsa, u holda a 0 (mod m) deb yoziladi.
Taqqoslamalarning asosiy xossalari (tengliklarning xossalariga o’xshash)
1. Agar a c (mod m) va b c (mod m) bo’lsa, u holda a b (mod m) bo’ladi.
2. Agar a b (mod m) va c d (mod m) bo’lsa, u holda a c bd (mod m) bo’ladi.
3. Agar a + b c (mod m) bo’lsa, u holda a c - b (mod m) bo’ladi.
4. Agar a b (mod m) bo’lsa, u holda a mk b (mod m), yoki a b mk(mod m) bo’ladi.
5. Agar a b (mod m) va c d (mod m) bo’lsa, u holda ac bd (mod m)bo’ladi.
6. Agar a b (mod m) bo’lsa, u holda aⁿ bⁿ (mod m) (n∈N) bo’ladi.
7. Agar a b (mod m) bo’lsa, u holda ixtioriy k butun son uchun a^k b^k (mod m) bo’ladi.
8. Agar a^k b^k (mod m) va (k,m) = 1 bo’lsa, u holda a b (mod m) bo’ladi.
9. Agar f(x) = a₀ xⁿ + a₁ x^n-1 + ... + a_n (a_i ∈Z) va x x₁ (mod m) bo’lsa, u holda f(x) f(x₁) (mod m) bo’ladi.
Taqqoslamalarninng maxsus xossalari
1. Agar a ≡ b (mod m) bo’lsa, u holda k∈N uchun ak ≡ bk (mod mk) bo’ladi.
2. Agar a ≡ b (mod m) va a = a₁ d, b = b₁ d, m = m₁ d bo’lsa, u holda a₁ ≡ b₁ (mod m₁) bo’ladi.
3. Agar a ≡ b (mod m₁), a ≡ b (mod m₂), ..., a ( b (mod m_k) bo’lsa, u holda a ≡ b (mod M) bo’ladi, bu yerda M = [m₁, m₂,..., m_k].
4. Agar taqqoslama m modul bo’yicha o’rinli bo’lsa, u holda bu taqqoslama m ning ixtiyoriy bo’luvchisi bo’lgan d modul bo’yicha ham o’rinli bo’ladi.
5. Agar taqqoslamaning bir tomoni biror songa bo’linsa, u holda uning ikkinchi tomoni va moduli ham shu songa bo’linadi.
5.1.1.Eyler funksiyasi.
Teorema(Fermaning kichik teoremasi). Agar p tub, a butun son bo’lsa, u holda quyida munosabat o’rinli:

Ta’rif. Har bir m>1 natural son uchun m dan katta bo’lmagan va m bilan o’zaro tub bo’lgan natural sonlar soni Eyler funksiyasi ϕ(m) bilan aniqlanadi.

m	2	3	4	5	6	7	8	9	10	11	12	13	14	15
ϕ(m)	1	2	2	4	2	6	4	6	4	10	4	12

Teorema. Eyler funksiyasi uchun quyidagi amallar o’rinli:
1) ϕ(p)=p-1, agar p tub son bo’lsa;
2) ϕ(p^s)=p^s-1-1, agar p tub son bo’lsa;
3) agar (m,n)=1 bo’lsa, u holda ϕ(mn)= ϕ(m) ϕ(n);
4)Agar ifoda m sonini kanonik ko’rinishda bo’luvchilarga ajratilgan ko’paytmasi bo’lsa, u holda
Misol. ϕ(48) ni aniqlang.
m=48=2⁴∙3 bo’lgani uchun, ϕ(48)= 2^4-1∙(2-1)∙3^1-1∙(3-1)=16.
Teorema(Takomillashgan Eyler ). Agar m>1 natural, a butun son bo’lsa, u holda (m,a)=1 ekanligidan a^φ(m)1(mod m) munosabat o’rinli.
5.1.1-Misol. Quyidagi shartlarni taqqoslamalar yordamida yozing:
a) 219 va 128 sonlarni 7 ga bo’lganda bir xil qoldiq qoladi;
b) (-352) sonini 31 ga bo’linganida qoldiq 20 ga teng bo’ladi ;
c) 487 - 7 ayirma 12 ga bo’linadi; d) 20 – soni 389 ni 41 ga bo’lgandagi qoldiqdan iborat; e) N soni juft; f) N soni toq; g) N sonining ko’rinishi 4k + 1 dan iborat;
h) N sonining ko’rinishi 10k + 3 dan iborat; i) N sonining ko’rinishi 8k –3 dan iborat.
Yechilishi. Taqqoslamaning ma’nosi haqidagi teoremaga asosan:
a) 219 ≡128 (mod 7); b) –352 ≡20 (mod 31); c) 487 ≡7 (mod 12);
d) 389 ≡20 (mod 41); e) N ≡0 (mod 2); f) N ≡1 yoki -1 (mod 2);
g) N ≡1 (mod 4); h) N ≡3(mod 10); i) N ≡-3 (mod 8).
5.1.2-Misol. Quyidagi shartni qanoatlantiradigan m ning qiymatlarini toping:
20 ≡8 (mod m).
Yechilishi. m ning qiymatlari (taqqoslamaning ma’nosi haqidagi teoremaga asosan) 20 – 8 = 12 ning bo’luvchilaridan iborat, ya’ni: 1; 2; 3; 4; 6; 12.
5.1.3-Misol. 2⁵ⁿ – 1 ning 31 ga bo’linishini isbotlang (n ЄN).
Yechilishi. 2⁵ – 1 = 31 bo’lganligi uchun 2⁵ ≡1 (mod 31). Bu taqqoslamaning ikkala tomonini (6-xossaga asosan) n darajaga ko’tarib, 2⁵ⁿ ≡1 (mod 31) ni hosil qilamiz, bu esa 31 (2⁵ⁿ – 1) ni anglatadi.
5.1.4-Misol. 2¹⁰⁰ sonining oxirgi ikkita raqamini toping.
Yechilishi. Berilgan sonning oxirgi ikki raqami bu sonni 100 ga bo’lganda hosil bo’ladigan qoldiqdan iborat. Demak, quyidagi taqqoslamani qanoatlantiradigan x sonini topish talab qilinadi:
2¹⁰⁰ ≡x (mod 100).
Ikkining kichik darajalaridan boshlab, 100 ga bo’lganda hosil bo’ladigan qoldiqlarni ketma-ket ajratamiz:
2¹⁰⁰ = (2¹⁰)¹⁰ = (1024)¹⁰; (1024)¹⁰ ≡ (24)¹⁰ (mod 100).
(24)¹⁰ = (576)⁵ ≡76 ⁵ ≡(76)⁴⋅76 = (5776)²⋅76 ≡(76)²⋅76 = 5776⋅76 ≡76² ≡5776 ≡76
(mod 100).
Shunday qilib, 2¹⁰⁰ sonining oxirgi ikki raqami 7 va 6 dan iborat.