logo

Kombinatorika va kriptografiya masalalari

Загружено в:

12.08.2023

Скачано:

0

Размер:

146.91015625 KB
Kombinatorika va kriptografiya masalalari  
MUNDARIJA
KIRISH ............................................................................................................ 2
I BOB. KOMBINATORIKA HAQIDA UMUMIY TUSHUNCHALAR. ..... 3
1.1. Kombinatorika predmeti va paydo bo’lish tarixi. ................................ 3
1.2. Kombinatorikada ko'p qo llaniladigan usul va qoidalar.ʻ ...................... 4
1.3. O'rin almashtirishlar. gruppalashlar ..................................................... 5
1.4. Paskal uchburchagi haqida umumiy ma'lumotlar. ................................ 6
II BOB.KRIPTOTIZIMLAR ......................................................................... 11
2.1. Kriptosistemalarga qo‘yiladigan talablar ............................................... 11
2.2. Kriptografik sistemalarning nazariy va amaliy bardoshliligi ................. 12
XULOSA ....................................................................................................... 16
ADABIYOTLAR RO’YXATI ...................................................................... 17
ILOVALAR ................................................................................................... 18
ILOVA 1. Siljitib shifrlash ........................................................................ 18
ILOVA 2. Xor yordamida shifrlash .......................................................... 19
ILOVA 3. Faktarialni topish. .................................................................... 20 KIRISH
Biz   bu   mavzuda   kombinatorika   predmeti   va   paydo   bo’lish   tarixi   va
kombinatorikada   ko'p   qo llaniladigan   usul   va   qoidalar   .   Bu   qoidalar   misol   o'rinʻ
almashtirishlar   va   gruppalashlar   yana   paskal   uchburchagi   haqida   umumiy
ma'lumotlar.   Keyin   2-bobda   esa   kriptosistemalarga   qo‘yiladigan   talablar,
kriptografik   sistemalarning   nazariy   va   amaliy   bardoshliligi   shu   kabi   ko’plab
qiziqarli bulgan ma’lumotlarga ega bo’lasiz. I BOB.  KOMBINATORIKA HAQIDA UMUMIY
TUSHUNCHALAR.
1.1.  Kombinatorika predmeti va paydo bo’lish tarixi.
Umuman olganda, kombinatorikaning dastlabki rivoji qimor o'yinlarini tahlil
qilish bilan bog liq. Ba'zi atoqli matematiklar, masalan, B. Paskal, Yakob Bernulli,ʻ
L.   Eyler,   P.   L.   Chebishey2   turli   o'yinlarda   (tanga   tashlash,   soqqa   tashlash,   qarta
o'yinlari   va   shu   kabilarda)   ilmiy   jihatdan   asoslangan   qaror   qabul   qilishda
kombinatorikani qo llashgan.	
ʻ
XVII   asrda   kombinatorika   matematikaning   alohida   bir   ilmiy   yo nalishi	
ʻ
sifatida   shakllana   boshladi.   B.   Paskal   o zining   «Arif-   metik   uchburchak   haqida	
ʻ
traktat»   va   «Sonli   tartiblar   haqida   traktat»   (1665-y.)   nomli   asarlarida   hozirgi
vaqtda   binomial   koeffitsiyentlar,   deb   ataluvchi   sonlar   haqidagi   ma'lumotlarni
keltirgan.   P.   Ferma'   esa   figurali   sonlar   bilan   birlashmalar   nazariyasi   orasida
bog'lanish borligini bilgan.
Figurali sonlar quyidagicha aniqlanadi. Birinchi tartibli figurali sonlar: 1, 2,
3, 4, 5,... (ya'ni natural sonlar); ikkinchi tartibli figurali sonlar: 1-si 1ga teng, 2-si
dastlabki   ikkita   natural   sonlar   yig'indisi   ,   3-si   dast-   labki   uchta   natural   sonlar
yig'indisi   va hokazo (1, 3, 6, 10, 15, ...); uchinchi tartibli figurali sonlar: 1-si 1ga
teng,   2-si   birinchi   ikkita   ikkinchi   tartibli   figurali   sonlar   yig'indisi   ,   3-si   birinchi
uchta ikkinchi tartibli figurali sonlar yig'indisi va hokazo (1, 4, 10, 20, 35, ...); va
hokazo.
1-misol.   Tekislikda   radiuslari   o'zaro   teng   bo'lgan   aylanalar   bir-   biriga
uringan   holda   yuqoridan   1-qatorda   bitta,   2-qatorda   ikkita,   3-qatorda   uchta   va
hokazo,   joylashtirilgan   bo'lsin.   Masalan,   ayla-   nalar   bunday   joylashuvining
dastlabki   to'rt   qatori   1-shaklda   tasvir-   langan.   Bu   yerda,   qatorlardagi   aylanalar
sonlari ketma-ketligi birinchi tartibli figurali sonlarni tashkil qiladi. Bu tuzilmadan
foy-   dalanib   ikkinchi   tartibli   figurali   sonlarni   quyidagicha   hosil   qilish   mumkin.
Dastlab   l-qatordagi   aylanalar   soni   (1),   keyin   dastlabki   ikkita   qatordagi   aylanalar
soni (3), undan keyin dastlabki uchta qatordagi aylanalar soni (6) va hokazo.
Gotfrid   Leybnis.«Kombinatorika»   iborasi   G.   Leybnisning?   «Kombinatorik
san'at  haqidagi  mulohazalar»nomli  asarida birinchi  bor  1665-yilda keltirilgan. Bu
asarda   birlashmalar   nazariyasi   ilmiy   jihatdan   ilk   bor   asoslangan.
O rinlashtirishlarni o'rganish bilan birinchi bo'lib Yakob Bernulli shug'ullangan va	
ʻ
bu haqdagi ma'lumotlarni 1713-yilda bosilib chiqqan «Ars conjectandi» (Bashorat
qilish   san'ati)   nomli   kitobining   ikkinchi   qismida   bayon   qilgan.   Hozirgi   vaqtda
kombinatorikada qo llanilayotgan belgilashlar XIX asrga kelib shakllandi.	
ʻ
Kombinatsiya   bu   kombinatorikaning   asosiy   tushunchasi.   Bu   tushuncha
yordamida ixtiyoriy to'plamning qandaydir sonda- gi elementlaridan tashkil topgan
tuzilmalar   ifodalanadi.   Kombinato-   rikada   bunday   tuzilmalarning   o rin	
ʻ
almashtirishlar, o rinlashtirishlar va guruhlashlar, deb ataluvchi asosiy ko'rinishlari	
ʻ
o rganiladi.	
ʻ 1.2. Kombinatorikada ko'p qo llaniladigan usul va qoidalar.ʻ  
Kombinatorika   va   graflar   nazariyasida   tasdiqlarni   isbotlashning   samarali
usullaridan   biri   bo'lgan   matematik   induksiya   usuli   ko'p   qo llaniladi.   Bu   usulning	
ʻ
ketma-ket   bajariladigan   ikkita   qismi   bo lib,   ular   quyidagi   umumiy   g'oyaga	
ʻ
asoslanadi.
Faraz   qilaylik,   isbotlanishi   kerak   bo'lgan   tasdiq   birorta   xususiy   n=n
0   qiymat
(masalan, n=1) uchun to'g'ri bo'lsin (usulning bu qismi baza yoki asos, deb ataladi).
Agar   bu   tasdiqning   istalgan   n=k>n
0   uchun   to'g'riligidan   uning   n=k+1   uchun
to'g'riligi kelib chiqsa, u holda tasdiq istalgan natural n≥n
0  son uchun to g ri bo'ladi	
ʻ ʻ
(induksion o tish).	
ʻ
Ixtiyoriy n natural son uchun
1²   +   2²   +   ...   +   n²   =n(n+1)(2n+1)/6   tenglikning   o'rinli   bo lishini   matematik	
ʻ
induksiya usuli yordamida isbotlaymiz.
Baza: n=1 bo'lsin, u holda yuqoridagi tenglik to g ri ekanligi	
ʻ ʻ
ravshan:
 1 2
=1*(1+1)*(2*1+1)/6 
Induksion o'tish: isbotlanish kerak bo'lgan tenglik n=k>1 uchun to'g'ri, ya'ni
1² + 2² + ... + k² =k(k+1)(2k+1)/6
tenglik   o'rinli   bo'lsin.   Bu   tenglikning   chap   va   o'ng   tomonlariga   (k+1)²   ifodani
qo'shib, uni
1² + 2² + ... + k²+(k+1)²  =k(k+1)(2k+1)/6+(k+1)²
ko'rinishda   yozamiz.   Oxirgi   tenglikning   o'ng   tomonida   quyidagicha
o zgartirishlarni bajaramiz:	
ʻ
(k(k + 1)(2k + 1))/6 + (k + 1) 2
 = (k + 1)[(k(2k + 1))/6 + (k + 1)] =  =((k + 1)(2k 2
 +
7k + 6))/6 = ((k + 1)(2k 2
 + 4k + 3k + 6))/6 =
= ((k + 1)[2k(k + 2) + 3(k + 2)])/6 = ((k + 1)[(k + 1) + 1][2(k + 1)+1])/6 .
Demak,
1 2
 +2 2
 +...+ k 2
 + (k + 1) 2
 = ((k + 1)[(k + 1) + 1][2(k + 1) + 1])/6 . Oxirgi munosabat
isbotlanishi kerak bo'lgan tenglikning bo lgan holidir.	
ʻ
Shuni ta'kidlash kerakki, biron tasdiqni isbotlash uchun matematik induksiya
usuli   qo'llanilganda,   bu   usulning   ikkala   qismini   ham   tekshirib   ko'rish   muhimdir,
ya'ni   baza   va   induksion   o tish,   albatta,   tekshirilishi   shart.   Ulardan   biri	
ʻ
tekshirilmasa noto'g'ri natijalar hosil bo lishi ham mumkin. Bundan tashqari, baza	
ʻ
birorta   xususiy   qiymatdan   boshqa   ko'p,   hattoki,   juda   ko'p   xususiy   hollar   uchun
tekshirilib,   ijobiy   natija   olinganda   ham,   bu   hollarni   umumlashtiruvchi   natijaviy
tasdiq   noto'g'ri   bo lib   chiqishi   mumkin.   Bu   mulohazalarning   o'rinli   ekanligini	
ʻ
quyida keltirilgan misollar ko rsatadi.	
ʻ
Misol:   Ixtiyoriy   n   natural   son   uchun   2n-1   son   2   ga   qoldiqsiz   bo linadi»,	
ʻ
degan   tasdiqni   tekshirishda   matematik   induksiya   usulining   baza   qismi   talabini
bajarmasdan faqat induksion o'tishni tekshiramiz.
Bu   tasdiq   n   =   k   >   1   uchun   to'g'ri   bo'lsin,   ya'ni   2k-1   son   2   ga   qoldiqsiz
bo linsin, deb faraz qilamiz. U holda (2k - 1) + 2 son ham, qo shiluvchilarining har	
ʻ ʻ biri   2   ga   qoldiqsiz   bo'linganligi   sababli,   2   ga   qoldiqsiz   bo'linadi.   Shuning   uchun
(2k - 1) + 2 = 2(k + 1) - 1 tenglik asosida (2k+1)-1 son 2 ga qoldiqsiz bo linadi,ʻ
degan xulosa kelib chiqadi. Demak, yuqoridagi tasdiq n = k + 1 uchun to'g'ri, ya'ni
induksion o'tish bajarildi, deb hisoblash mumkin.
Ikki nusxadagi kombinatsiyalar bilan ishlash. Ba’zan kirish massivida
takroriy elementlar bo’lishi mumkin.
Masalan, Kirish massivida n = {5, 2, 3, 1, 5} mavjud. Bu yerda biz 5 ning 2
marta mavjudligini ko’rishimiz mumkin. Endi, agar biz ushbu massiv uchun
kodni
ishga   tushirmoqchi   bo’lsak,   ba’zi   kombinatsiyalar   takrorlanadi.   Biz   {5,   2,
5},   {5,   2,   3}   va   hokazolarni   topamiz   yoki   5   ni   o’z   ichiga   olgan   har   qanday
kombinatsiya   takrorlanadi.   Biz   ushbu   ikkita   usuldan   foydalanishimiz   mumkin:
Kirish   massivini   tartiblang.   Saralash   O(nlog(n))   vaqt   oladi.   Keyin   i   qiymatini
oshiring,   i   qiymati   va   i+1   qiymati   bir   xil.   Kombinatsiya   funksiyasiga   asosan
quyidagi   ikkita   kod   qatorini   qo’ying.   Takroriy   kombinatsiyalarni   kuzatish   uchun
lug’at   yoki   tartibsiz   xaritadan   foydalanish   Shunday   qilib,   agar   biz   dublikatni
kuzatish   uchun   elementlarni   saralashni   istamasak,   biz   berilgan   qadamlarni
bajarishimiz mumkin.
1-qadam. Global lug’at yoki xashmapni e’lon qiling.
2-qadam. Yaratilgan kombinatsiyani xashmapga suring va qiymatni bittaga
oshiring. Kombinatsiya kalit bo’lib, ularning paydo bo’lishi qiymatdir.
3-qadam. Funktsiya ishga tushirilgandan so’ng, biz hashmap yoki lug’atdagi
barcha kalitlarni chop etamiz.
To plam,   element,   kombinatsiya,   o'rin   almashtirish,   betakror   o'rin	
ʻ
almashtirish,   o'rin   almashtirishlar   soni,   o'rinlashtirish,   o'rinlashtirishlar   soni,
gruppalash,   gruppalashlar   soni,   ko'paytirish   qoidasi,   matematik   induksiya   usuli,
faktorial.
1.3. O'rin almashtirishlar.  gruppalashlar
O'rin almashtirishlar.  Elementlari a,,a,,a,,.,a bo lgan to'plamni	
ʻ
qaraymiz.   Bu   to'plam   elementlarini   har   xil   tartibda   joylashtirib   (yozib),
tuzilmalar (kombinatsiyalar) hosil qilish mumkin, masalan:
           a
1, a
2, a
3,….,  a
n                 a
2, a
1, a
3,….,  a
n                      a
3, a
2, a
1,….,  a
n 
2-misol.Tuplamlar o’rtasida kombinatsiya.
Bu   tuzilmalarning   har   birida   berilgan   to'plamning   barcha   ele-   mentlari
ishtirok etgan holda ular bir-biridan faqat elementlarning joylashish o'rinlari bilan
farq   qiladilar.   Shu   usul   yordamida   hosil   qilingan   kombinatsiyalarning   har   biri
berilgan (a
1 ,a
2 ,a
3 ,…,a
n ) to'plam elementlarining o'rin almashtirishi, deb ataladi. Aslida   o rin   almashtirish»   iborasi   to'plam   elementlarining   o'rinlariniʻ
o zgartirish   harakatini   anglatsa-da,   bu   yerda   uni   shu   harakat   natijasidagi   hosil	
ʻ
bo lgan   tuzilma   sifatida   qo'llaymiz.   Bu   iboradan   uning   asl   ma'nosida   ham
ʻ
foydalanamiz.
n   ta   elementli   (a
1 ,a
2 ,a
3 ,…,a
n )to'plam   berilgan   bo'lsin.   Shu   to'plamning
ixtiyoriy   m   ta   elementidan   hosil   qilingan   tartiblangan   (a
i1 ,a
i2 ,a
i3 ,…,a
im )   tuzilmaga
(kombinatsiyaga) n ta elementdan m tadan o rinlashtirish, deb ataladi.	
ʻ
Bu ta'rifdan ko'rinib turibdiki, elementlari soni  bir  xil bo'lgan ikkita har  xil
o'rinlashtirishlar   bir-biridan   elementlari   bilan   yoki   bu   elementlarning   joylashish
tartibi   bilan   farq   qiladilar.   Bundan   tashqari,   n   ta   elementdan   m   tadan
o'rinlashtirishlar   uchun   m≤n   bo lishi   ham   ravshan.   Bu   yerda   qaralayotgan	
ʻ
o rinlashtirishlar tarkibidagi elementlarning takrorlanmasligini eslatib o'tamiz. Shu	
ʻ
sababli  bunday  o'rinlashtirishlarni  betakror  (takrorli  emas)  o'rin-  lashtirishlar, deb
ham atash mumkin.
Gruppalashlar.   (a
1 ,a
2 ,a
3 ,…,a
n )   to'plam   berilgan   bo'lsin.   Bu   n   elementli
to'plamning elementlaridan m ta elementga ega qism to'p- lamlarni shunday tashkil
etamizki, ular bir-biridan elementlarining joylashish tartibi bilan emas, faqat tarkibi
bilan farq qilsinlar. Bunday m ta elementli qism to'plamlarning har biriga n ta ele-
mentdan m tadan gruppalash, deb ataladi.
N ta elementdan tadan gruppalashlar sonini  C
nm
bilan belgilaymiz.
Gruppalashlar   sonini   (m/n)   yoki   (n/m)   shaklda   belgilashlar   ham   uchraydi.
Gruppalash   ta'rifidan   1≤m≤n   ekanligi   va   agar   biror   gruppalashda   qandaydir   usul
bilan elementlar o'rinlari almash- tirilsa,u (gruppalash sifatida) o'zgarmasligi kelib
chiqadi.
Bu   yerda   qaralayotgan   gruppalash   tarkibida   elementlarning
takrorlanmasligini   eslatib   o'tamiz.   Shu   sababli   bunday   gruppalashni   betakror
(takrorli emas) gruppalash, deb ham atash mumkin.
1.4. Paskal uchburchagi haqida umumiy ma'lumotlar.
Paskal   uchburchagi   haqida   umumiy   ma'lumotlar.   Berilgan   n   ta   elementdan
m tadan gruppalashlar soni 	
Cnm  uchun bir necha qatorlarni jadvaldagidek yozamiz:
 Bu jadvalda gruppalashlar sonining quyidagi xossalarini kuzatish mumkin:
1-jadval.  1-rasm.Guruppalashlar.
-   har   bir   qatorning   chetlarida   birlar   joylashgan   (bu   tasdiq   C
n0
= C
n0
=1   formula   bilan
ifodalanadi);
-   har   bir   qatordagi  Cnm   sonlar   qatorning   teng   o'rtasiga   nisbatan   simmetrik
joylashgan,   ya'ni   qatorning   boshidan   va   oxiridan   baravar   uzoqlikda   turgan   sonlar
o'zaro teng ( C
nm
 = C
nn − m
);
-   ikkinchi   qatordan   boshlab   har   bir   qatordagi   birlardan   tashqari   ixtiyoriy   son   bu
qatordan   yuqorida   joylashgan   qatordagi   biri   shu   son   ustida,   ikkinchisi   esa   undan
chapda joylashgan ikkita gruppalashlar sonining yig'indisiga teng (	
Cnm  =	Cnm + =	Cnm );
- har bir qatordagi  C
nm
 sonlar shu qator teng o rtasigacha o'sib, so'ng kamayadi.	
ʻ
G arbda   Al-Koshiy   nomi   bilan   mashhur   samarqandlik   olim   Ali   Qushchi	
ʻ
butun   sonning   istalgan   natural   ko rsatkichli   arifmetik   ildizi   qiymatini   taqribiy	
ʻ
hisoblashda bu jadvaldan foydalana bilganligi haqida ma'lumotlar bor. Keyinchalik
G'arbiy   Yevropada   bu   sonlar   uchburchagi   haqida   M.   Shtifel   arifmetika   bo'yicha
qo'llanmalarida   yozgan   va   u   ham   butun   sondan   istalgan   natural   ko rsatkichli	
ʻ
arifmetik   ildizning   taqribiy   qiymatini   hisoblashda   bu   uchburchakdan   foydalana
bilgan. 1556-yilda bu sonlar jadvali bilan N. Tartalya, keyinroq logarifmik lineyka
ijodkori   U.   Otred   (1631-yil)   ham   shug'ullangan.   1654-yilga   kelib,   B.   Paskal
o'zining   «Arifmetik   uchburchak   haqidagi   traktat»   nomli   asarida   bu   sonlar   jadvali
haqidagi ma'lumotlarni e'lon qildi.
Paskal   uchburchagidagi   qatorlar   istalgancha   davom   ettirilishi   mumkin.
Shunisi   qiziqki,   Paskal   uchburchagi   yordamida   istalgan   n   ta   elementdan   m   tadan
gruppalashlar sonini faqat qo'shish amali yordamida hosil qilish mumkin.
2-rasm.Paskal uchburchagi. Bu amal
C
nm
 = C
n − 1m − 1
 + C
n − 1m
 formulaga asoslanadi.
Paskal   uchburchagi   ko plab   ajoyib   xossalarga   ega.   B.   Paskal   yuqorida   zikrʻ
etilgan   traktatda:   «Bu   xossalarning   haqiqatan   ham   bitmas-tuganmasligi   naqadar
ajoyibdir» deb yozgan edi.
Nyuton   binomi   haqida   umumiy   ma'lumotlar.   O'rta   maktab   matematikasi
kursidan quyidagi ikkita qisqa ko'paytirish formula- larini eslaylik:
(a+b)²=a²+2ab+b² - yig'indining kvadrati;
(a+b)³=a³+3a2b+3ab2 +b - yig'indining kubi.
Yig'indining navbatdagi ikkita, ya'ni 4- va 5-darajalarini hisoblaymiz:
(a+b) 4
=(a+b)(a+b)³=(a+b)(a³+3a²b+3ab²+b³)=   =   a 4
+4a³b+6a 2
b 2
+4ab³+b 4
;
(a+b) 5
=(a+b)(a+b) 4
=a 5
+5a 4
b+b+10a³b 2
+10a 2
b 3
+5ab 4
+b 5
.
Shunday qilib, yig indining bikvadrati (ya'ni to'rtinchi darajasi)	
ʻ
(a+b) 4
= a 4
+4a³b+6a²b²+4ab³+b 4
 va yig indining beshinchi darajasi	
ʻ
(a+b) 5
=a 5
+5a 4
b+10a³b²+10a²b³+5ab 4
+b 5
.
formulalariga ega bo'lamiz. Yuqorida keltirilgan yig'indining kvadrati, kubi,
bikvadrati   va   beshinchi   darajasi   formulalari   o'ng   tomonlaridagi   ko phad	
ʻ
koeffitsiyentlari   Paskal   uchburchagining   mos   qatorlaridagi  	
Cnm     (n=2,3,4,5)   sonlar
ekanligini   payqash   qiyin   emas.   Barcha   haqiqiy   a   va   b   hamda   natural   n   sonlar
uchun
(a+b) n
 =a n
 + C
n1
 a n-1
 b+ C
n2
 a n-2
 b²+...+ C
nn − 1
  a b n-1
 +b n
 formula o'rinlidir.
Tarixiy ma'lumotlar:
Ba'zi  kombinatorik masalalarni  yechish bilan qadimgi  Xitoyda, keyinchalik
Rim   imperiyasi   davrida   ham   shug'ullanganlar.   Lekin   matematikaning   mustaqil
bo limi  sifatida  faqat  ehtimollar   nazariyasi  fani   rivoji  tufayli   Evropada  18  asrdan	
ʻ
boshlab tan olindi.
n   elementdan   k   ta   elementni   ularning   tartibini   hisobga   olmasdan   barcha
tanlashlar  soni  C, deb belgilanadi  va n elementdan  k tadan guruhlashlar  soni  deb
ataladi.	
Cnk
  belgi "p dan k bo'yicha se" deb o'qiladi. n elementdan k tadan
guruhlashlar soni uchun
C
nk
=n!/(k!(n-k)!)
1-formula.Guruhlashlar sonini topuvchi formula.
formula o'rinli.
Kundalik   hayotda   bizning   oldimizga   bitta   emas,   yechishning   bir   nechta
varianti   mavjud   bo lgan   muammolar   paydo   bo'ladi.   To'g'ri   tanlashni   amalga	
ʻ
oshirish   uchun   ulardan   hech   birini   qo'ldan   chiqarmaslik   lozim.   Buning   uchun
barcha   mumkin   bo lgan   variantlarni   tanlashni   amalga   oshirish   lozim.   Bunday
ʻ
masalalar ham kombinatorik masalalarga kiradi.
Ko'pgina o'yinlarda o'yin kubigidan foydalaniladi. Kubikda 6 ta yoq bo'lib,
har bir yoqqa 1 dan 6 gacha sonda bo lgan nuqtalar belgilangan. O'yinchi kubikni	
ʻ
tashlaydi va tushgan yoqda (kubikning yuqorida joylashgan yoqidagi) nechta nuqta
borligiga   qaraydi.   Ko'pincha   kubikning   yoqlaridagi   nuqtalar   mos   raqamlar   bilan almashtiriladi   va   1,2,...,6   raqamlarning   tushgani   haqida   gapirishadi.   Kubikni
tashlashni tajriba, eksperiment, sinov (hatto o'yin ham deb), olingan natijani sinov,
tajriba   yoki   elementar   hodisa   deb   hisoblash   mumkin.   Odamlarga   u   yoki   bu
hodisani   ro y   berishini   topish,   uning   natijasini   bashorat   qilish   qiziqarli.   O'yinʻ
kubigini tashlaganda ular qanday bashoratlar qilishi mumkin? Masalan, bunday: 4
hodisa 1,2,3,4,5 yoki  6 raqami  tushishi;  B hodisa -7, 8 yoki  9 raqami tushishi;  C
hodisa-1 raqami tushishi.
Birinchi   holda   bashorat   qilingan   A   hodisa   albatta   ro'y   beradi.   Berilgan
tajribada albatta ro'y beradigan hodisa ishonchli hodisa deyiladi. Masalan, suv to la	
ʻ
stakan to'nkarilsa, u holda suv to'kiladi.
Ikkinchi   holda   bashorat   qilingan   B   hodisa   hech   qachon   ro'y   bermaydi,   bu
mumkin emas. Berilgan tajribada ro'y berishi mumkin bo lmagan hodisa mumkin	
ʻ
bo lmagan hodisa deb ataladi.	
ʻ
Uchinchi holda bashorat qilingan C hodisa haqida nima deyishimiz mumkin,
ro'y   beradimi   yoki   ro'y   bermaydimi?   Bu   savolga   to'la   ishonch   bilan   javob   bera
olmaymiz,   chunki   1   raqami   tushishi   ham,   tushmasligi   ham   mumkin.   Berilgan
tajribada ro'y berishi ham, ro y bermasligi ham mumkin bo lgan hodisaga tasodifiy	
ʻ ʻ
hodisa deyiladi. Masalan, kishi ko'chada tanishlarini uchratdi.
Hodisalar - kuzatish yoki tajriba natijasi.
Birinchi   p   ta   natural   son   ko'paytmasi   n!   deb   belgilanadi   va   "EN
FAKTORIAL"   deb   ataladi:   n!-1*2*3*   (n-2)   (n-1)n.   (inglizchasiga   <<factor>>>
so'zining ma'nolaridan biri, tarjimasi ko'paytuvchi). 0!=1 deb hisoblanadi.
Faktorialni topish ilovalar bo’limidagi
#include <iostream>
using namespace std;
int factorial(int n) {
    if (n == 0 | n == 1) 
{
        return 1;
    } else 
{
        return n * factorial(n-1);
    }
}
int main() {
    int n;
    cout << "Musbat butun son kiriting: ";
    cin >> n;
    cout << n << " ning faktoriali hisoblanadi " << factorial(n) << endl;
    return 0; }
Mana bu dasturimiz ham faktorialni topib beradi.
Bu   faktorial   funksiyasi   sonning   faktorialini   hisoblaydigan   rekursiv
funksiyadir. U n butun sonini kiritadi va uning faktorialini qaytaradi. Agar n 0 yoki
1 bo lsa, u 1ni qaytaradi. Aks holda, u nni n-1 faktorialiga ko paytiradi.ʻ ʻ
main funksiyasi  foydalanuvchidan musbat  butun son kiritishni  taklif  qiladi,
kiritilgan   ma'lumotlarni   o'qiydi   va   keyin   faktorialni   hisoblash   uchun   faktorial
funksiyasini chaqiradi. Nihoyat, u natijani konsolda ko'rsatadi.
Buni rekursiv qilmasdan ham ishlash mumkin 
#include <iostream>
using namespace std;
int main() {
    int n,i;
    cout << "Musbat butun son kiriting: "; cin >> n;
    long long S=1;
    for(i=1;i<=n;i++)
     S*=i;
    cout << n << " ning faktoriali hisoblanadi " << S << endl;
    return 0;
}
Mana bunda esa for sikldan foydalanib ishladik. II BOB. KRIPTOTIZIMLAR
2.1.  Kriptosistemalarga qo‘yiladigan talablar
Ma’lumotlarni   muhofazalashning   muhim   masalalari   bilan   bevosita
munosabatda   bo‘lmagan   kishilar   axborotlar   tizimida   muhim   ma’lumotlar
muhofazasi   qoidalarining   buzilishi   mumkin   bo‘lgan   sabablarni   son   va   sifat
jihatidan serqirraligini, tabiiyki, ma’lum bir qolipda tasavvur qila olmaydi. Quyida
keltiriladigan   ma’limotlar   ko‘p   uchraydigan   va   nisbatan   yaqolroq   his   qilish
mumkin bo‘lgan ba’zi muhofazalash qoidalarining buzilish sabablari keltirilgan.
Ma’lumotlarni   muhofazalash   qoidalarini   buzuvchining   maqsadi   va   uni
amalga oshirish uslublari:
1)  Ruxsat etilmagan ma’lumotlarni beruxsat olish va unga ega bo‘lish, ya’ni
ma’lumotlarning maxfiy saqlanish qoidalarini buzish.
2)   Maxfiy   axborotlar   tizimida   foydalanuvchilarning   biror   ma’lumot
yuzasidan   o‘zini   javobgarlikdan   (mas’ullikdan)   xalos   etish   uchun   o‘zini   boshqa
foydalanuvchi   sifatida   ifodalash   yoki   boshqa     foydalanuvchining   vakolatidan
foydalanish maqsadida:
a) yolgon ma’lumotlarni tashkillashtirish;
b) haqiqiy (qonuniy) ma’lumotlarii o‘zgartirish;
v)   ruxsat   etilmagan   ma’lumotni   olish   uchun   o‘zinning   shu   ma’lumotni   olishga
vakolati bo‘lgan shaxs sifatida ifodalash;
g)  yolg‘on ma’lumotlarni axborotlar  tizimiga tushinishiga yo‘l  qo‘yib berish yoki
yolg‘on ma’lumotlarni tasdiqlash;
3) Mavjud bo‘lgan ma’lumotlarni tashkillashtirishni rad etish.
4) qoidabuzar tomonidan yolgon maьlumotlar tashkillashtirilib, shu yolg‘on
ma’lumotlarni   axborotlar   tizimining   boshqa   bir   foydalanuvchisi   tomonidan
tashkillashtirilgan, deb ifodalash.
5)   Biror   aniq   ko‘rsatilgan   vaqtda   ma’lumotni   oluvchiga   yuborilmagan
ma’lumotni   yuborilgan,   deb   ifodalash   yoki   yuborilgan   ma’lumotni   yuborilgan
vaqtini yolg‘on ko‘rsatish.
6)     Haqiqatan   ham,   olingan   ma’lumotlarni   olinganligini   rad   etish   yoki
ma’lumotlarning haqiqiy olingan vaqtini soxtalashtirish.
7)   Axborotlar   tizimidan   foydalanuvchilarning   o‘zlariga   berilgan
vakolatlarini   -   ma’lumotlarni   tashkillashtirish,   uzatish,   tarqatish   va   boshqa
yo‘nalishlarda ruxsat etilmagan holda kengaytirish.
8) Ruxsat etilmagan holda foydalanuvchilarning vakolatlarini o‘zgartirish.
9)   Maxfiy   bo‘lgan   ma’lumotni   maxfiy   bo‘lmagan   ma’lumotlar   kabi
ifodalash.
10) Aloqa tizimi foydalanuvchilarining o‘zaro aloqa shaxobchalariga ruxsat
etilmagan   holda   bog‘lanib   olib,   shu   shaxobchadan   olingan   ma’lumotlarni   boshqa
aloqa tizimlariga doimiy ravishda tarqatib turish. 11)   Aloqa   kanalidagi   ma’lumotlar   oqimini   tahlil   qilib,   ma’lumotlar
jamg‘armasining   tuzilish   tartibiga   qarab,   programmalash   ta’minoti   va   boshqa
xosliklarga   ko‘ra,   foydalanuvchilardan   kim   qanday   ma’lutmotlarni   qachon   olish
vakolatiga egaligini o‘rganish.
12)   Protokol   (ma’lum   tartib   hamda   qoida)   bo‘yicha   har   qanday   xolda   ham
maxfiy qolishi kerak bo‘lgan ma’lumotni maxfiyligiga putur etkazgan holda ushbu
protokol ma’lumotlarning sofligini ta’minlashiga shubha bilan qarash.
13)   Biror   yaqqol   sezilmaydigan   yo‘l   (protsedura)   bilan   ma’lumotlarni
muhofazalash algoritmi dasturiga o‘zgartirish kiritish.
14)   Yolg‘on   ma’lumotlar   asosida   boshqa   foydalanuvchilarni   muhofaza
protokolni buzishga undash.
15)   Ochiqdan   ochiq   protokolni   buzishi   bilai   ushbu   muhofaza   protokoliga
ishonchni yo‘qotishga olib keladigan hatti-harakatlar.
16)   Axborotlar   tizimining   boshqa   foydalanuvchilariga   ma’lumotlarni   sifatli
uzatilishiga   xalaqit   berish,   xususan,   uzatilayotgan   ma’lumotga   yaqqol
sezilmaydigan   texnik,   dasturiy   va   boshqa   uslublar   bilan   xalaqit   berib,   uzatilgan
ma’lumotning   haqiqiyligini   (autentifikatsiyasini)   rad   etishga   olib   keladigan   hatti-
harakatlar.
Bu   yuqorida   keltirilgan   ma’lumot   ixtiyoriy   munosabat   (ayniqsa
kelishmovchilik) muammolarini sabablarini mantiqan tahlil qilishda ham asos qilib
olish mumkin.
Messi  o‘zining "Hozirga zamon kriptologiya faniga kirish", deb nomlangan
ilmiy   maqolasida   qanchalik   ishonchli   kriptobardoshli   uslub   yaratilmasin   bari-bir
o‘z echimini kutayotgan boshqa kriptografik masalalar kelib chiqishi mumkinligini
ta’kidlab, foydalano‘vchilarga protokol bo‘yicha o‘z vazifalarini bajarishlari uchun
maxfiy kalitni qandan uzatish va olingan ma’lumotlarni haqiqiyligiga ishonch hosil
qilish   masalalari   to‘g‘risida   to‘xtaladi.   Mana   shunday   masalaning   qo‘yilishi,
xususan,   kalitlarni   axborotlar   tizimi   foydalanuvchilariga   taqsimlashda   kelib
chiqadigan   muammolarni   hal   etuvchi,   ochiq   kalitli   kriptografiya   yo‘nalishining
vujudga   kelishiga   sabab   bo‘ldi.   Bundan   tashqari,   tizim   foydalanuvchilarining   har
biri   butun   tizim   protokoli   ichida   o‘zlarining   qism   protokoli   bo‘yicha   faoliyat
ko‘rsatayotganligiga   hamda   boshqa   foydalanuvchilarning   ham   umumiy   tizim
protokolini   buzmagan   holda   faoliyat   ko‘rsatayotganligiga   ishonch   hosil   qilinishi,
ya’ni  umumiy tizim  protokolining bardoshlilik darajasiga ishonch masalalari  ham
muhim ahamiyat kasb etadi. Sodda qilib ifodalaganda, axborotlar tizimidagi har bir
foydalanuvchining shaxsiy kalitning muhofazasini ta’minlash dolzarb masaladir.
2.2.  Kriptografik sistemalarning nazariy va amaliy bardoshliligi
Kriptografiya nima?
Kriptografiya,   keng   ma'noda,   maxfiy   kalitlar   yoki   protseduralar   bilan
kodlangan xabarlarni yaratish san'ati va texnikasi shuning uchun uni parolini ochib
bo'lmaydi, faqat unga murojaat qilingan yoki kalitni ushlab turgan odamgina. Bu   so'z   yunoncha   termrυπτός   (kryptos)   atamasidan   hosil   bo'lib,   «yashirin»
degan   ma'noni   anglatadi   va   -grafiya,   «yozish»   ma'nosini   anglatuvchi
qo'shimchadir.
Kriptografiyaning   maqsadi   shu   yuborilgan   ma'lumotni   himoya   qiling,
shunda faqat qabul  qiluvchi yoki  kalitga ega bo'lgan odamlar xabarni  to'g'ri  o'qiy
olishadi.   Buning   uchun   faqat   vakolatli   shaxslarga   ma'lum   bo'lgan   shifrlash
tizimlari ishlab chiqilgan.
Kriptografiya qadimgi davrlarda, urushlar natijasida, qarama-qarshi guruhlar
o'zlarining   xabarlarini   o'qish   yoki   ularni   dushmanlari   tomonidan   ochib
bo'lmasligidan   kelib   chiqqan   holda   paydo   bo'lgan.   Demak,   ular   buning   uchun
kodlar yoki kalitlarni yaratdilar.
Shifrlash texnikasini o'rganish va tadqiq qilish uchun mas'ul bo'lgan intizom
deyiladi kriptologiya. O'z navbatida, ular kriptograflar matematikadan foydalanish
orqali   shifrlash   texnikasini   o'rganish   va   rivojlantirish   bilan   shug'ullanadiganlar.
Kriptanaliz   ularni   buzish   maqsadida   kriptografik   tizimlarni   o'rganishga
bag'ishlangan bo'lsa.
Zamonaviy   davrda   kriptografiya   asosan   Internet   orqali   tarqatiladigan   aloqa
va   axborot   xavfsizligini   ta'minlash   maqsadida   kompyuterga   nisbatan   ancha
rivojlandi.2 ta asosiy kriptografiyalar bor bular:
1-Hisoblashda kriptografiya.
Hisoblashda kriptografiya shaxsiy ma'lumot uzatilishini himoya qilish uchun
shifrlangan   kodlar   va   yozish   tizimlarining   texnikasini   nazarda   tutadi,   shuning
uchun   kalitga   ega   bo'lmaganlar   uchun   uni   o'qib   bo'lmaydigan   yoki   amalda
imkonsiz.   Kriptografiya   vebning   yaxlitligini   himoya   qilish   bilan   bir   qatorda
foydalanuvchilar   xavfsizligi,   aloqa   va   Internet   orqali   amalga   oshiriladigan
operatsiyalarni  saqlashga  imkon beradi. Shunda kriptografiyaning asosiy  maqsadi
tarmoq orqali almashiladigan ma'lumotlarning maxfiyligini kafolatlashdir.
2-Simmetrik kriptografiya.
Xabarlarni   shifrlash   va   parolini   hal   qilish   uchun   bir   xil   kalitdan
foydalaniladigan   usul,   shuning   uchun   ikkala   tomon   ham,   jo'natuvchi   ham,   qabul
qiluvchida   ham   bitta   kalit   bo'lishi   kerak.   Masalan:   GSM   mobil   telefonining
autentifikatsiyasi.
Bu   ikkita   kalit   ishlatilgan   usul,   ulardan   biri   ochiq   va   ikkinchisi   shaxsiy.
Shaxsiy kalitdan faqat egasi foydalanish huquqiga ega bo'lgan holda, har kim ochiq
kalitdan foydalanishi mumkin.
Qisqa   qilib   aytganda   kriptografiya   uchinchi   shaxslar   ishtirokida   xavfsiz
muloqot   qilish   amaliyotidir.   U   ma'lumotlarning   maxfiyligi,   yaxlitligi   va
haqiqiyligini ta'minlash uchun shifrlash, parolni hal qilish va raqamli imzolar kabi
usullarni   o'z   ichiga   oladi.   Kriptografiya   qadimgi   tsivilizatsiyalarga   borib
taqaladigan uzoq va qiziqarli tarixga ega bo'lib, u erda odamlar xabarlarni kodlash
uchun oddiy almashtirish shifrlaridan foydalanganlar. Bugungi kunda kriptografiya
zamonaviy   jamiyatda   xavfsiz   onlayn   tranzaktsiyalarni   amalga   oshirish,   maxfiy
ma'lumotlarni   himoya   qilish   va   milliy   xavfsizlikni   himoya   qilish   imkonini
beruvchi   hal   qiluvchi   rol   o'ynaydi.   Qizig‘i   shundaki,   “kriptologiya”   atamasi yunoncha “kryptos” (yashirin)  va “logos”  (so‘z)  so‘zlaridan kelib chiqqan bo‘lib,
so‘zma-so‘z “yashirin so‘zlarni o‘rganish” degan ma’noni anglatadi.
Yana   bir   narsa   xeshlash   va   xesh   funksiya   tushunchasi   bu   nima   uzi?
deyishingiz mumkin.
Xeshlash – bu ixtiyoriy uzunlikdagi kirish ma'lumotlari majmuasini ma'lum
bir   algoritm   tomonidan   bajarilgan,   belgilangan   o'lchamdagi   chiqish   massiviga
aylantirish jarayoni. Bunday algoritmni amalga oshiruvchi funksiya xesh funksiya,
transformatsiya   natijasi   xesh   yoki   xesh   yig'indisi   deyiladi.   Xesh   funksiyasi
quyidagi xususiyatlarga ega: - bir xil ma'lumotlar bir xil xeshni  beradi; - "deyarli
har   doim"   turli   xil   ma'lumotlar   boshqacha   xesh   beradi.   Ikkinchi   xususiyatdagi
"deyarli har doim" izohi xeshlarning aniq o'lchamiga ega bo'lishidan kelib chiqadi,
shu   bilan   birga   kirish   ma'lumotlari   bu   bilan   cheklanmaydi.   Natijada,   biz   xesh
funktsiyasi  kirish ma'lumotlari to'plamidan xeshlar to'plamiga xaritalashni  amalga
oshiramiz, bu esa ularning kardinalligi ancha past bo'ladi. Dirixle prinsipiga ko'ra,
har   bir   xesh   uchun   bir   nechta   turli   xil   ma'lumotlar   to'plamlari   bo'ladi.   Bunday
moslik   kolliziya   deb   ataladi.   Agar   biron   bir   muammoni   hal   qilishda   kirish
ma'lumotlari   cheklangan   bo'lsa,   siz   bunday   xeshlar   to'plamini   tanlashingiz
mumkin,   shunda   uning   aniqligi   kirish   ma'lumotlari   to'plamining   muhimligidan
oshib   ketadi.   Bunday   holda,   biz   inyeksion   xaritalashni   aniqlaydigan   xesh
funksiyasini   qurishimiz   mumkin   (mukammal   xeshlash).   Biroq,   umuman   olganda,
kolliziya   muqarrar.   Kolliziya   ehtimoli   xesh   funksiyasi   sifatini   baholash   uchun
ishlatiladi.  Yaxshi   xesh  funksiyasi  quyidagicha  ishlaydi:   -  mavjud bo'lgan  barcha
xesh   oralig'i   maksimal   darajada   ishlatiladi;   -   kirish   ma'lumotlarining   ozgina
o'zgarishi   ham   mutlaqo   boshqacha   xeshni   berishi   kerak,   to'qnashuvlar   faqat
butunlay boshqacha ma'lumotlar uchun ro'y berishi  kerak. Xeshlash o'zi obyektga
tasodifiy o'zgaruvchini xaritalashga o'xshaydi. Birinchi xususiyat natijasida xeshlar
o'zlarini bir tekis taqsimlangan tasodifiy o'zgaruvchilar kabi tutishi kerak, bu butun
diapazondan foydalanishni ta'minlaydi, bu foydali bo'lishi mumkin, masalan, xesh
jadvalini tuzishda.
"Kriptografiya   va   kriptovalyutalar"   kitobi   muallifi   R.   H.   Ayupov.   U
kriptografiya   asoslarini   qamrab   oladi   va   kriptovalyutalar   kontekstida   uning
ilovalarini   o'rganadi.   Kitobda   kriptografiya   tarixi   va   evolyutsiyasi,   shuningdek,
uning turli texnika va algoritmlari haqida umumiy ma’lumot berilgan. Shuningdek,
u kriptovalyutalarning paydo bo'lishi va kriptografiyaning ushbu raqamli aktivlarni
himoya   qilishdagi   rolini   muhokama   qiladi.   Umuman   olganda,   kitob   kriptografiya
va   kriptovalyutalarning   kesishishi   haqida   bilishga   qiziqqan   har   bir   kishi   uchun
foydali manbadir.
Kodlash   -   ma'lumotni   (xabarlarni)   kod   shaklida   taqdim   etish   jarayoni.
Kodlash   uchun   ishlatiladigan   belgilarning   butun   to'plami   kodlash   alifbosi   deb
ataladi. Masalan, kompyuter xotirasida har qanday ma'lumot faqat ikkita belgidan
iborat   ikkilik   alifbo   yordamida   kodlanadi:   0   va   1.   Dekodlash   -   kodni   asl   belgilar
tizimi   shakliga   qaytarish   jarayoni,   ya'ni.   asl   xabarni   oling.   Masalan:   Morze
alifbosidan   rus   tilidagi   yozma   matnga   tarjima.   Kengroq   ma'noda   dekodlash   -   bu
kodlangan xabar mazmunini tiklash jarayoni. Kodlash   -   bu   matn   faylini   ASCII   yoki   Unicode   formatiga   kodlash   kabi
ma'lumotlarni  bir   format  yoki  tildan  boshqasiga  aylantirish  jarayoni.  Dekodlash   -
bu   kodlangan   ma'lumotni   asl   shakliga   yoki   tiliga   tarjima   qilishning   teskari
jarayoni.   Bu   odatda   kompyuter   tizimlari   va   kommunikatsiya   texnologiyalarida
ma lumotlarning   turli   qurilmalar   va   dasturiy   ta minot   dasturlari   tomonidanʼ ʼ
uzatilishi va to g ri tushunilishini ta minlash uchun qo llaniladi.	
ʻ ʻ ʼ ʻ
Qadim   zamonlarda   kodlash   bilan   shug'ullangan   odamlarga   o'z   xabarlarini
shifrlash   uchun  almashtirish   shifridan  foydalangan  Yuliy  Sezar  va  o'z   xabarlarini
shifrlash   uchun   scytale   deb   nomlangan   transpozitsiya   shifridan   foydalangan
spartaliklar   kiradi.   Samuel   Morze   esa   telegraf   orqali   xabarlarni   uzatishda
foydalanilgan   Morze   kodini   ixtiro   qilgani   bilan   mashhur.   Ushbu   qadimiy   va
zamonaviy kodlash usullari xavfsiz aloqa uchun maxfiy kodlarni ishlab chiqish va
dekodlash   bilan   bog‘liq   bo‘lgan   kriptografiya   sohasini   shakllantirishga   yordam
berdi.
Kodlash   xabarlarni   signalga   aylantirishdir,   ya'ni.   xabarlarni   kod
birikmalariga   aylantirish.   Kod   -   xabar   elementlari   va   kod   birikmalari   o'rtasidagi
yozishmalar   tizimi.   kodlovchi   -   kodlashni   amalga   oshiradigan
qurilma.   Dekoder   -   teskari   operatsiyani   bajaradigan   qurilma,   ya'ni.   kod   so'zini
xabarga   aylantirish.   Alifbo   -   mumkin   bo'lgan   kod   elementlari   to'plami,   ya'ni.
elementar belgilar (kod belgilari)   X = (x   i   },   qayerda   i = 1, 2,..., m.   Kod elementlari
soni   -   m   uni   chaqirdi   asos   .   Ikkilik   kod   uchun   x   i   =   {0,   1}   Va   m   =   2.   Berilgan
alifbodagi   belgilarning   chekli   ketma-ketligi   deyiladi   kod   birikmasi   (kod   so'zi).
Kod kombinatsiyasidagi elementlar soni -   n   chaqirdi   ahamiyati   (kombinatsiyaning
uzunligi).   Turli   xil   kod   birikmalarining   soni   (   N=m   n )   deyiladi   hajmi   yoki   kod
kuchi.
Matnni   kodlashning   uchta   asosiy   usuli   mavjud: grafik -   maxsus   chizmalar
yoki piktogrammalar yordamida;
raqamli - raqamlardan foydalanish
ramziy - asl matn bilan bir xil alifbodagi belgilardan foydalanish.
Texnologiyani rivojlantirish uchun eng muhimi, faqat ikkita belgidan iborat
kod   yordamida   ma'lumotni   taqdim   etish   usuli   edi:   0   va   1.Bunday   alifbodan
foydalanish   qulayligi   uchun   biz   uning   har   qanday   belgilarini   chaqirishga   rozi
bo'ldik   "bit"   ( ingliz tilidan " bi   nary digi t   » -ikkilik belgisi ).
Ilovalardagi siljitib shifrlash   kodini kuraylik
for (int i = 0; i < xabar.length(); i++) {
        char c = xabar[i];
        if (isalpha(c))
{ 
c = toupper(c); 
            c = ((c - 'A') + siljish) % 26 + 'A'; 
}
Bu qism  kodning asosiy  qismi  bo’lib bunda xabar  nomli  so’zimizni  har bir
harfini 4taga suradi. XULOSA
Kombinatorika   matematikaning   berilgan   to plamdagi   ma lum   miqdordagiʻ ʼ
elementlardan   tashkil   topgan   tuzilmalarni   o rganish   bilan   shug ullanuvchi
ʻ ʻ
bo limidir. U 17-asrda paydo bo lgan va Paskal, Bernulli, Eyler va Chebishev kabi	
ʻ ʻ
matematiklar   tomonidan   qimor   o yinlarida   qaror   qabul   qilishda   foydalanilgan.	
ʻ
Kombinatsiya   tushunchasi   kombinatorika   uchun   asos   bo'lib,   u   almashtirishlar,
kombinatsiyalar   va   guruhlarni   o'rganadi.   "Kombinatorika"   atamasi   birinchi   marta
Leybnits   tomonidan   1665   yilda   o'zining   "Kombinatorlik   san'ati   haqida
mulohazalar"   nomli   asarida   eslatib   o'tilgan   va   u   erda   assotsiatsiyalar   nazariyasini
ilmiy asoslagan. Jeykob Bernulli birinchi bo lib joylashtirishlarni o rgangan va bu	
ʻ ʻ
haqda 1713-yilda o zining “Ars conjectandi” (“Bashorat san ati”) kitobida yozgan.	
ʻ ʼ
Kombinatorikada   qo llanilgan   belgilashlar   19-asrda   shakllangan.Bundan   kelib	
ʻ
chiqadike   Qadim   zamonlardan   beri   kombinatorika   rivojlanib   kelmoqda   bu   esa
insonyatga ayrim qiziqarli sirlarni ochmoqda.
Shennon   nazariy   va   amaliy   bag'rikenglikni   ko'rib   chiqdi   va   ochiq   kalitli
kriptotizimlar amaliy jihatdan mustahkam  va nazariy jihatdan mustahkam  bo'lishi
shart   emasligini   ta'kidladi.   Shennon   mutlaq   maxfiylik   kontseptsiyasini   aniqladi,
ya'ni   ochiq   matn   va   kriptogramma   statistik   jihatdan   mustaqildir   va   kriptoanalitik
hatto   barcha   shifrlash   vositalari   va   cheksiz   vaqt   bilan   ham   ochiq   matnni
baholashning   to'g'riligini   to'liq   baholay   olmaydi.   U,   shuningdek,   L   qo'shish
operatsiya   moduliga   asoslangan   maxsus   shifrlash   jarayoniga   ega   tasodifiy
bo'lmagan   shifrlangan   matndan   foydalangan   holda   mutlaqo   maxfiy   kriptografik
tizimlar mavjudligini ko'rsatdi. ADABIYOTLAR RO’YXATI
1. Kombinatorika va graflar nazariyasi.Mualliflar:H.To’rayev,I.Azizov, 
S.Otaqulov
2. Kombinatorika elementlari.Muallif:Xalxo’jayev A.M.
3. Kriptografiyaning matematik asoslari.Muallif: Akbarov Davlatali 
Yegitaliyevich.
4. Kriptografiya va kriptovalyutalar.Muallif: Ayupov R. H.
5. https://tami.uz/matnga_qarang.php?id=337   
6. https://uz.warbletoncouncil.org/criptografia-4155   
7. https://bumotors.ru/uz/referat-sovremennye-sposoby-kodirovaniya-
informacii-v-vychislitelnoi.html. ILOVALAR
ILOVA 1.  Siljitib shifrlash
#include <iostream>
#include <string>
using namespace std;
string shifrlash(string xabar, int siljish) {
    string natija = "";
    for (int i = 0; i < xabar.length(); i++) {
        char c = xabar[i];
        if (isalpha(c))
{  // belgi harf ekanligini tekshiring            
c = toupper(c);  // bosh harfga aylantiring
            c = ((c - 'A') + siljish) % 26 + 'A';  // siljish qiymati bo'yicha belgini
siljitish
        }
        natija += c;
    }
    return natija;
}
int main() {
    string xabar = "ABCD";
    int siljish = 4;
    string shifrlangan = shifrlash(xabar, siljish);
    cout << "Shifrlangan xabar:" << shifrlangan << endl;
    return 0;
}
Bu   kodda   siljish   necha   bulsa   shuncha   harfga   siljitiladi   ya’ni   4   bulsa   A→E
bo’ladi. ILOVA 2.  Xor yordamida shifrlash  
#include <iostream>
#include <string>
using namespace std;
string encrypt(string message, string key) {
    string result = "";
    for (int i = 0; i < message.length(); i++) {
        char c = message[i] ^ key[i % key.length()]; // XOR tegishli kalit belgisi bilan
belgi
        result += c;
    }
    return result;
}
int main() {
    string message = "HELLO WORLD";
    string key = "SECRET";
    string encrypted = encrypt(message, key);
    cout << "Encrypted message: " << encrypted << endl;
    return 0;
}
Ushbu  kod  kirish  sifatida  xabar  va   kalitni  oladi  va   shifrlangan  xabarni  qaytaradi.
XOR   operatori   (^)   xabarning   har   bir   belgisini   kalitning   tegishli   belgisi   bilan
birlashtirish   uchun   ishlatiladi.   Shuni   esda   tutingki,   bu   ilova   faqat   ASCII   belgilar
uchun   ishlaydi,   lekin   siz   uni   boshqa   belgilar   to plamini   boshqarish   uchun   hamʻ
o zgartirishingiz mumkin.	
ʻ ILOVA 3.  Faktarialni topish.
#include <iostream>
using namespace std;
int factorial(int n) {
    if (n == 0 | n == 1) 
{
        return 1;
    } else 
{
        return n * factorial(n-1);
    }
}
int main() {
    int n;
    cout << "Musbat butun son kiriting: ";
    cin >> n;
    cout << n << " ning faktoriali hisoblanadi " << factorial(n) << endl;
    return 0;
}

Kombinatorika va kriptografiya masalalari MUNDARIJA KIRISH ............................................................................................................ 2 I BOB. KOMBINATORIKA HAQIDA UMUMIY TUSHUNCHALAR. ..... 3 1.1. Kombinatorika predmeti va paydo bo’lish tarixi. ................................ 3 1.2. Kombinatorikada ko'p qo llaniladigan usul va qoidalar.ʻ ...................... 4 1.3. O'rin almashtirishlar. gruppalashlar ..................................................... 5 1.4. Paskal uchburchagi haqida umumiy ma'lumotlar. ................................ 6 II BOB.KRIPTOTIZIMLAR ......................................................................... 11 2.1. Kriptosistemalarga qo‘yiladigan talablar ............................................... 11 2.2. Kriptografik sistemalarning nazariy va amaliy bardoshliligi ................. 12 XULOSA ....................................................................................................... 16 ADABIYOTLAR RO’YXATI ...................................................................... 17 ILOVALAR ................................................................................................... 18 ILOVA 1. Siljitib shifrlash ........................................................................ 18 ILOVA 2. Xor yordamida shifrlash .......................................................... 19 ILOVA 3. Faktarialni topish. .................................................................... 20

KIRISH Biz bu mavzuda kombinatorika predmeti va paydo bo’lish tarixi va kombinatorikada ko'p qo llaniladigan usul va qoidalar . Bu qoidalar misol o'rinʻ almashtirishlar va gruppalashlar yana paskal uchburchagi haqida umumiy ma'lumotlar. Keyin 2-bobda esa kriptosistemalarga qo‘yiladigan talablar, kriptografik sistemalarning nazariy va amaliy bardoshliligi shu kabi ko’plab qiziqarli bulgan ma’lumotlarga ega bo’lasiz.

I BOB. KOMBINATORIKA HAQIDA UMUMIY TUSHUNCHALAR. 1.1. Kombinatorika predmeti va paydo bo’lish tarixi. Umuman olganda, kombinatorikaning dastlabki rivoji qimor o'yinlarini tahlil qilish bilan bog liq. Ba'zi atoqli matematiklar, masalan, B. Paskal, Yakob Bernulli,ʻ L. Eyler, P. L. Chebishey2 turli o'yinlarda (tanga tashlash, soqqa tashlash, qarta o'yinlari va shu kabilarda) ilmiy jihatdan asoslangan qaror qabul qilishda kombinatorikani qo llashgan. ʻ XVII asrda kombinatorika matematikaning alohida bir ilmiy yo nalishi ʻ sifatida shakllana boshladi. B. Paskal o zining «Arif- metik uchburchak haqida ʻ traktat» va «Sonli tartiblar haqida traktat» (1665-y.) nomli asarlarida hozirgi vaqtda binomial koeffitsiyentlar, deb ataluvchi sonlar haqidagi ma'lumotlarni keltirgan. P. Ferma' esa figurali sonlar bilan birlashmalar nazariyasi orasida bog'lanish borligini bilgan. Figurali sonlar quyidagicha aniqlanadi. Birinchi tartibli figurali sonlar: 1, 2, 3, 4, 5,... (ya'ni natural sonlar); ikkinchi tartibli figurali sonlar: 1-si 1ga teng, 2-si dastlabki ikkita natural sonlar yig'indisi , 3-si dast- labki uchta natural sonlar yig'indisi va hokazo (1, 3, 6, 10, 15, ...); uchinchi tartibli figurali sonlar: 1-si 1ga teng, 2-si birinchi ikkita ikkinchi tartibli figurali sonlar yig'indisi , 3-si birinchi uchta ikkinchi tartibli figurali sonlar yig'indisi va hokazo (1, 4, 10, 20, 35, ...); va hokazo. 1-misol. Tekislikda radiuslari o'zaro teng bo'lgan aylanalar bir- biriga uringan holda yuqoridan 1-qatorda bitta, 2-qatorda ikkita, 3-qatorda uchta va hokazo, joylashtirilgan bo'lsin. Masalan, ayla- nalar bunday joylashuvining dastlabki to'rt qatori 1-shaklda tasvir- langan. Bu yerda, qatorlardagi aylanalar sonlari ketma-ketligi birinchi tartibli figurali sonlarni tashkil qiladi. Bu tuzilmadan foy- dalanib ikkinchi tartibli figurali sonlarni quyidagicha hosil qilish mumkin. Dastlab l-qatordagi aylanalar soni (1), keyin dastlabki ikkita qatordagi aylanalar soni (3), undan keyin dastlabki uchta qatordagi aylanalar soni (6) va hokazo. Gotfrid Leybnis.«Kombinatorika» iborasi G. Leybnisning? «Kombinatorik san'at haqidagi mulohazalar»nomli asarida birinchi bor 1665-yilda keltirilgan. Bu asarda birlashmalar nazariyasi ilmiy jihatdan ilk bor asoslangan. O rinlashtirishlarni o'rganish bilan birinchi bo'lib Yakob Bernulli shug'ullangan va ʻ bu haqdagi ma'lumotlarni 1713-yilda bosilib chiqqan «Ars conjectandi» (Bashorat qilish san'ati) nomli kitobining ikkinchi qismida bayon qilgan. Hozirgi vaqtda kombinatorikada qo llanilayotgan belgilashlar XIX asrga kelib shakllandi. ʻ Kombinatsiya bu kombinatorikaning asosiy tushunchasi. Bu tushuncha yordamida ixtiyoriy to'plamning qandaydir sonda- gi elementlaridan tashkil topgan tuzilmalar ifodalanadi. Kombinato- rikada bunday tuzilmalarning o rin ʻ almashtirishlar, o rinlashtirishlar va guruhlashlar, deb ataluvchi asosiy ko'rinishlari ʻ o rganiladi. ʻ

1.2. Kombinatorikada ko'p qo llaniladigan usul va qoidalar.ʻ Kombinatorika va graflar nazariyasida tasdiqlarni isbotlashning samarali usullaridan biri bo'lgan matematik induksiya usuli ko'p qo llaniladi. Bu usulning ʻ ketma-ket bajariladigan ikkita qismi bo lib, ular quyidagi umumiy g'oyaga ʻ asoslanadi. Faraz qilaylik, isbotlanishi kerak bo'lgan tasdiq birorta xususiy n=n 0 qiymat (masalan, n=1) uchun to'g'ri bo'lsin (usulning bu qismi baza yoki asos, deb ataladi). Agar bu tasdiqning istalgan n=k>n 0 uchun to'g'riligidan uning n=k+1 uchun to'g'riligi kelib chiqsa, u holda tasdiq istalgan natural n≥n 0 son uchun to g ri bo'ladi ʻ ʻ (induksion o tish). ʻ Ixtiyoriy n natural son uchun 1² + 2² + ... + n² =n(n+1)(2n+1)/6 tenglikning o'rinli bo lishini matematik ʻ induksiya usuli yordamida isbotlaymiz. Baza: n=1 bo'lsin, u holda yuqoridagi tenglik to g ri ekanligi ʻ ʻ ravshan: 1 2 =1*(1+1)*(2*1+1)/6 Induksion o'tish: isbotlanish kerak bo'lgan tenglik n=k>1 uchun to'g'ri, ya'ni 1² + 2² + ... + k² =k(k+1)(2k+1)/6 tenglik o'rinli bo'lsin. Bu tenglikning chap va o'ng tomonlariga (k+1)² ifodani qo'shib, uni 1² + 2² + ... + k²+(k+1)² =k(k+1)(2k+1)/6+(k+1)² ko'rinishda yozamiz. Oxirgi tenglikning o'ng tomonida quyidagicha o zgartirishlarni bajaramiz: ʻ (k(k + 1)(2k + 1))/6 + (k + 1) 2 = (k + 1)[(k(2k + 1))/6 + (k + 1)] = =((k + 1)(2k 2 + 7k + 6))/6 = ((k + 1)(2k 2 + 4k + 3k + 6))/6 = = ((k + 1)[2k(k + 2) + 3(k + 2)])/6 = ((k + 1)[(k + 1) + 1][2(k + 1)+1])/6 . Demak, 1 2 +2 2 +...+ k 2 + (k + 1) 2 = ((k + 1)[(k + 1) + 1][2(k + 1) + 1])/6 . Oxirgi munosabat isbotlanishi kerak bo'lgan tenglikning bo lgan holidir. ʻ Shuni ta'kidlash kerakki, biron tasdiqni isbotlash uchun matematik induksiya usuli qo'llanilganda, bu usulning ikkala qismini ham tekshirib ko'rish muhimdir, ya'ni baza va induksion o tish, albatta, tekshirilishi shart. Ulardan biri ʻ tekshirilmasa noto'g'ri natijalar hosil bo lishi ham mumkin. Bundan tashqari, baza ʻ birorta xususiy qiymatdan boshqa ko'p, hattoki, juda ko'p xususiy hollar uchun tekshirilib, ijobiy natija olinganda ham, bu hollarni umumlashtiruvchi natijaviy tasdiq noto'g'ri bo lib chiqishi mumkin. Bu mulohazalarning o'rinli ekanligini ʻ quyida keltirilgan misollar ko rsatadi. ʻ Misol: Ixtiyoriy n natural son uchun 2n-1 son 2 ga qoldiqsiz bo linadi», ʻ degan tasdiqni tekshirishda matematik induksiya usulining baza qismi talabini bajarmasdan faqat induksion o'tishni tekshiramiz. Bu tasdiq n = k > 1 uchun to'g'ri bo'lsin, ya'ni 2k-1 son 2 ga qoldiqsiz bo linsin, deb faraz qilamiz. U holda (2k - 1) + 2 son ham, qo shiluvchilarining har ʻ ʻ

biri 2 ga qoldiqsiz bo'linganligi sababli, 2 ga qoldiqsiz bo'linadi. Shuning uchun (2k - 1) + 2 = 2(k + 1) - 1 tenglik asosida (2k+1)-1 son 2 ga qoldiqsiz bo linadi,ʻ degan xulosa kelib chiqadi. Demak, yuqoridagi tasdiq n = k + 1 uchun to'g'ri, ya'ni induksion o'tish bajarildi, deb hisoblash mumkin. Ikki nusxadagi kombinatsiyalar bilan ishlash. Ba’zan kirish massivida takroriy elementlar bo’lishi mumkin. Masalan, Kirish massivida n = {5, 2, 3, 1, 5} mavjud. Bu yerda biz 5 ning 2 marta mavjudligini ko’rishimiz mumkin. Endi, agar biz ushbu massiv uchun kodni ishga tushirmoqchi bo’lsak, ba’zi kombinatsiyalar takrorlanadi. Biz {5, 2, 5}, {5, 2, 3} va hokazolarni topamiz yoki 5 ni o’z ichiga olgan har qanday kombinatsiya takrorlanadi. Biz ushbu ikkita usuldan foydalanishimiz mumkin: Kirish massivini tartiblang. Saralash O(nlog(n)) vaqt oladi. Keyin i qiymatini oshiring, i qiymati va i+1 qiymati bir xil. Kombinatsiya funksiyasiga asosan quyidagi ikkita kod qatorini qo’ying. Takroriy kombinatsiyalarni kuzatish uchun lug’at yoki tartibsiz xaritadan foydalanish Shunday qilib, agar biz dublikatni kuzatish uchun elementlarni saralashni istamasak, biz berilgan qadamlarni bajarishimiz mumkin. 1-qadam. Global lug’at yoki xashmapni e’lon qiling. 2-qadam. Yaratilgan kombinatsiyani xashmapga suring va qiymatni bittaga oshiring. Kombinatsiya kalit bo’lib, ularning paydo bo’lishi qiymatdir. 3-qadam. Funktsiya ishga tushirilgandan so’ng, biz hashmap yoki lug’atdagi barcha kalitlarni chop etamiz. To plam, element, kombinatsiya, o'rin almashtirish, betakror o'rin ʻ almashtirish, o'rin almashtirishlar soni, o'rinlashtirish, o'rinlashtirishlar soni, gruppalash, gruppalashlar soni, ko'paytirish qoidasi, matematik induksiya usuli, faktorial. 1.3. O'rin almashtirishlar. gruppalashlar O'rin almashtirishlar. Elementlari a,,a,,a,,.,a bo lgan to'plamni ʻ qaraymiz. Bu to'plam elementlarini har xil tartibda joylashtirib (yozib), tuzilmalar (kombinatsiyalar) hosil qilish mumkin, masalan: a 1, a 2, a 3,…., a n a 2, a 1, a 3,…., a n a 3, a 2, a 1,…., a n 2-misol.Tuplamlar o’rtasida kombinatsiya. Bu tuzilmalarning har birida berilgan to'plamning barcha ele- mentlari ishtirok etgan holda ular bir-biridan faqat elementlarning joylashish o'rinlari bilan farq qiladilar. Shu usul yordamida hosil qilingan kombinatsiyalarning har biri berilgan (a 1 ,a 2 ,a 3 ,…,a n ) to'plam elementlarining o'rin almashtirishi, deb ataladi.