1-amaliy mashg’ulot kriptografik masalalarni yechishda arifmetik hisoblashlarni o’rganish ishning maqsadi

1.3 Binar algoritm

Ushbu algoritm, shuningdek 2 ta sonning eng katta umumiy bo‘luvchisi uchun ham foydalaniladi va quyidagi to‘rtta tasdiqqa asoslanadi:

1) agar ikkita a va b son - juft bo‘lsa, unda: EKUB(a, b) = 2∙ EKUB(а/2, b/2);
2) agar a - juft, b – toq bo‘lsa, unda EKUB(a, b) =EKUB(а/2, b);
3) EKUB(a, b) =EKUB(b, a-b);
4) agar a va b – toq bo‘lsa, unda (a – b) - juft.
Misol: EKUB(1173, 323) = ?
(1173, 323) = (323, 850) = (323, 425) = (323, 102) = (323, 51) = (51, 272)
= (51, 136) = (51, 68) = (51, 34) = (51, 17) = (17, 34) = (17, 17) = 17
Natija: EKUB(1173, 323) = 17.


1.4 Tub sonlar

Musbat butun nolga teng bo‘lmagan son tub deb ataladi, agar u faqatgina o’ziga va birga bo‘linsa.

Misollar: 11 – oddiy, 29 – oddiy, 56 – murakkab (56= 7 ∙ 4 ∙ 2).
Ikkita m va n sonlar o‘zaro oddiy deyiladi, agarda ular birdan boshqa umumiy bo‘luvchiga ega bo‘lmasa, ya’ni eng katta umumiy bo‘luvchi EKUB (m, n) = 1.
1.5 Eyler funksiyasi

φ(n) (n ≥ 1) Eyler funksiyasi deb n dan kichik musbat butun sonlar va n bilan o‘zaro tub sonlarga aytiladi.

Misollar: φ(1) = 0; φ(2) = 1; φ(3) = 2; φ(4) = 2; φ(5) = 4; φ(6) = 2; φ(7) = 6; φ(8) = 4; φ(9) = 6; φ(11) = 10.
Agar n – tub son, unda φ(n)=n – 1.
Misol: φ(31)=30.
Agar n=p∙q, bu yerda p va q – tub sonlar, unda φ(n)= (p–1)∙(q–1).
Misol: φ(35) = φ(5) ∙ φ(7) = 4 ∙ 6 = 24
Ixtiyoriy n soni uchun Eyler funksiyasini hisoblashning umumlashtirilgan algoritmi.
Agar n ni muvofiq darajadagi tub sonlar ko‘paytmasi deb tasavvur qilsak:
n = (p₁, p₂, …, p_r - oddiylar),
unda
φ(n)=n∙(1-1/ p₁)∙(1-1/ p₂)∙…∙(1-1/ p_r).
Misol:
φ(2700) = ?
2700 ni 2²∙3³∙5² kabi tasavvur qilish mumkin.
Unda φ(2700) = 2700∙ (1-1/2)∙(1-1/3)∙(1-1/5)=720.