” mavzusida tayyorlangan individual loyiha 1

II BOB. Kriptografiyada qo’llaniladigan asosiy matematik tushunchalar
2.1 Sodda matematik amallar
To‘plam matematikaning ko‘plab sohalarida boshlang‘ich fundamental tushuncha hisoblanib, belgisi, xususiyati yoki xossalari bir xil narsalarning majmui tushuniladi. To‘plamni tashkil etuvchi narsalar to‘plamning elementlari deb yuritiladi. Ushbu x  X ifoda x elementning X to‘plamga tegishli ekanligini bildiradi, aks holda x  X ifoda bilan belgilanadi. To‘plam odatda biror alifboning bosh harfi bilan, uning elementlari figurali qavslar ichiga olingan yoki talqini berilgan kichik harflar bilan belgilanadi. Muhim ahamiyatga molik to‘plamlar uchun standart belgilardan foydalaniladi. N, Z, Q, R belgilari mos tarzda natural, butun, rasional va haqiqiy sonlar to‘plamlarini belgilashda foydalaniladi. N – natural sonlar to‘plami: 1,2,… ko‘rinishidagi butun musbat sonlar. Z – butun sonlar to‘plami: n, -n va 0 ko‘rinishidagi sonlar, bu yerda n – natural son. Q - rasional sonlar to‘plami: p/q ko‘rinishidagi sonlar, bu yerda p va q - butun sonlar va 0 ≠ q. Rasional sonlar sinfi barcha Z butun sonlar to‘plamini, shu bilan birga o‘z navbatida barcha N natural sonlarni ham o‘z ichiga oladi. R – haqiqiy sonlar to‘plami: ushbu sinf rasional va barcha irrasional sonlarni o‘z ichiga oladi. Agar har ikkala to‘plam ham bir xil elementlardan tashkil topgan bo‘lsa, berilgan X va Y to‘plamlar teng deyiladi, aks holda teng emas deyiladi.
Misol uchun: X  0;0;0;0 0;0;0;0 Y , X  0;0;0;0 0;0;0 Y , ya’ni to‘plamlar elementlari soni teng emas. Elementlari soni chekli (cheksiz) bo‘lgan to‘plam chekli (cheksiz) to‘plam deyiladi. Har bir olingan x  X elementga bitta (x)Y element mos kelib, har bir olingan y Y elementga (x)  y tenglikni qanoatlantiruvchi x  X element mos kelsa, unda berilgan X va Y to‘plamlar o‘zaro bir qiymatli (biyektiv)  - moslikka ega deyiladi, Bunday biyektiv moslik  : X  Y ko‘rinishda ifodalanadi. Umuman olganda “ - akslantirish X - to‘plam elementlarini Y - to‘plam elementlariga akslantiradi” iborasi:  : X Y ko‘rinishda ifodalanadi. To‘plamlar bilan bog‘liq bo‘lgan tushunchalar, ta’rif va tasdiqlar juda keng tarqalgan bo‘lib, fan va texnikaning ko‘plab sohalariga tegishli bo‘lgan adabiyotlarda turli shakllarda keltirilganligi uchun, quyida ularni tartib raqamlarisiz keltiriladi. Agar berilgan X - cheksiz to‘plamning elementlarini nomerlab chiqish mumkin bo‘lsa, ya’ni X - to‘plam bilan N - natural sonlar to‘plami o‘zaro bir qiymatli moslikka ega bo‘lsa, bu cheksiz to‘plam sanoqli deyiladi. Boshqa cheksiz to‘plamlar sanoqsiz deyiladi. Misol uchun, isbot qilish mumkinki, barcha rasional sonlar to‘plami sanoqli, 0;1 - kesmadagi barcha haqiqiy sonlar to‘plami esa sanoqsizdir. Berilgan chekli to‘plam elementlari soni uning quvvatini aniqlaydi. Elementlari soni n ta bo‘lgan X -to‘plamning quvvati n ga teng bo‘lib, X  n, deb ifodalanadi. Sanoqsiz to‘plamlar “kontinium” quvvatga ega deb ham yuritiladi.
To‘plamni aniqlash uning elementlarini bevosita ko‘rsatish bilan amalga oshiriladi. Bundan tashqari, to‘plamni, uning elementlari xususiyatlarini so‘zlar orqali yoritish: M={iN: I –naturol son bo‘lib, 2 ga qoldiqsiz bo‘linadi} yoki formulalar bilan ifodalash (rekursiv usul): M  i  N : i  2k; k 1,2,... orqali aniqlash mumkin. Agarda Y - to‘plamning har bir elementi X - to‘plamning ham elementi bo‘lsa, u holda Y - to‘plam X -to‘plamga qism to‘plam bo‘ladi va Y  X ko‘rinishda ifodalanadi. Agarda Y  X bo‘lib, Y  X bo‘lsa, u holda Y  X ko‘rinishda ifodalanadi va Y -to‘plam X -to‘plamning xos qism to‘plami deyiladi. Agar Y  X va X  Y bo‘lsa, u holda Y  X bo‘ladi. Birorta ham elementga ega bo‘lmagan to‘plam bo‘sh to‘plam deyiladi va  belgi bilan ifodalanadi. Bo‘sh to‘plam  ixtiyoriy to‘plamga qism to‘plam bo‘ladi va uning quvvati nolga teng, ya’ni   0.
Har qanday X va Y - to‘plamlar juftligi uchun quyidagi amallar aniqlangan:1) yig‘indi X Y x : x X ёки xY; 2) kesishma (ko‘paytma) X Y: x X ва xY;3) ayirma X \Y x : x X ва xY.
Bu amallar quyidagi xossalarga ega: 1) kommutativlik: X Y  Y  X va X Y  Y  X ; 2) assosiativlik: X YZ  X Y Z va X YZ  X Y Z; 3) distributivlik: X Y  Z X YX  Z va X Y  Z X YX  Z;
4) X \YX Y X. Agar X U bo‘lsa, u holda X - to‘plamning U - to‘plamga
nisbatan to‘ldiruvchisi deb X =U \ X xU : x X U to‘plamga aytiladi. Quyidagi munosabatlar o‘rinli: X Y = X  Y i X Y = X  Y . Berilgan X1, X2,, Xm -to‘plamlarning Dekart ko‘paytmasi deb, ushbu X  X₁  X₂  Xm=x1, x₂,, x_m x X : x_i  X_i - to‘plamga aytiladi. Berilgan X - to‘plam  - munosabat bilan tartiblangan (chiziqli tartiblangan, to‘la tartiblangan) deyiladi, agarda a,b,c X – elementlar uchun quyidagi xossalar bajarilsa: 1) refleksivlik a  a ; 2) antisimmetriklik – agar a  b va b  a bo‘lsa, u holda a  b ; 3) tranzitivlik – agar a  b va b  c bo‘lsa, u holda a  c; 4) chiziqlilik – yoki a  b, yoki b  a. Agar a,b,c X - elementlar uchun (1)-(3) xossalar bajarilsa, berilgan X - to‘plam qisman tartiblangan to‘plam deyiladi. X - qisman tartiblangan to‘plamning diagrammasi (Xaas diagrammasi) deb, shu to‘plam elementlari juftliklarining a,b X yoy (yo‘naltirilgan kesma) bilan bog‘langan ifodasini tekislikdagi tasviriga aytiladi. Graflar ta’rifida, X - qisman tartiblangan to‘plam – bu yo‘nalishga ega bo‘lgan graf bo‘lib, uning uchlari X - to‘plamdan iborat ekanligi, a,b - juftlik faqat va faqat ushbu a  b va a  b - shartlar bilan birgalikda a va b elementlardan farqli bo‘lgan a  c  b shartni qanoatlantiruvchi с  X element mavjud bo‘lmagandagina yoy tashkil etishi ta’kidlanadi. Y - to‘plam berilgan X - qisman tartiblangan to‘plamning qism to‘plami bo‘lib, a  X bo‘lsin. U holda a  X bo‘lgan element Y – qism to‘plamning yuqori (quyi) chegarasi deyiladi, agarda barcha bY elementlar uchun b  a a  b shart bajarilsa. Y - to‘plamning yuqori chegarasi a uning aniq yuqori (quyi) chegarasi deyiladi, agarda Y - to‘plamning barcha s-yuqori (quyi) chegaralari uchun a  c c  a shart bajarilsa, a  supY (a  inf Y) deb belgilanadi. Agar a,b X elementlar uchun supa,b X hamda infa,b X bo‘lsa, qisman tartiblangan to‘plam X panjara deyiladi. To‘plamlarning xossalari bilan bog‘liq bo‘lgan kriptologiya masalalarini tahlil qilishda qo‘llaniladigan tushuncha va tasdiqlarni to‘plamlar nazariyasining amaliy tadbiqlari yoritilgan o‘quv qo‘llanmalaridan topish mumkin.
Istalgan ikkita X va Y to‘plam uchun barcha O  X Y qism to‘plamlar X va Y to‘plam o‘rtasidagi binar munosabat deb aytiladi. X ga nisbatan ~ binar munosabat ekvivelentlik munosabati deyiladi, agarda barcha x, x₁, x₂  X uchun quyidagi shartlar bajarilsa:
1. x~x (refleksivlik);
2. x~x₁ x₁~x (simmetriklik);
3. x~x₁, x₁~x₂ x₂~x (tranzitivlik).
Berilgan x ga ekvivalent bo‘lgan barcha elementlar qism to‘plami H={x'X|x'~x}X x ni o‘z ichiga olgan ekvivalentlik sinfi deyiladi. x~x (1-shart) bajarilsa, u holda x'H bo‘ladi. x'H ning istalgan elementi H sinfining vakili deyiladi. Teorema. X kesishmaydigan qismto‘plamlar birlashmasi bo‘lib, ~ munosabat bo‘yicha ekvivalentlik sinfi to‘plami uning tarkibiy qismi hisoblanadi. Isbot. xH dan X=Hi kelib chiqadi. So‘ngra ixtiyoriy vakili orqali H aniqlab olinadi, ya’ni Hi=Hj  xi~xj. Bir tomonga: xi~xj va xHi x~xix~xjxHjHi Hj bajariladi. Ammo xi~xjxj~xi bo‘lgani uchun HjHi bajariladi. Demak Hj=Hi ya’ni xH bo‘lsa, u holda Hi=HxHix~xi. Agar H j  Hi   va x  H j  Hi bo‘lsa, u holda x~xi va x~xj bo‘ladi, tranzitivlik shartidan xi~xj va Hj=Hi ga ega bo‘linadi.. Demak turli sinflar kesishmaydi. Teorema isbotlandi. Misol. To‘g‘riburchakli koordinatalar tizimida V=R2 – tekislik berilgan bo‘lsin. U holda ~ xossasidan kelib chiqib P, P'V nuqtalarning biror gorizontal to‘g‘ri chiziqqa tegishliligidan gorizontal to‘g‘ri chiziqlar sinfi bilan ekvivalentlik munosabati kelib chiqadi (2.1 a)-rasm).xy=p>0 shakldagi Gp giperbola V+ V sohada x>0, y>0 koordinatali P(x, y) nuqta bilan ekvivalentlik munosabatini aniqlaydi.

2.1- rasm. Ekvivalentlik munosabati