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.