Mirzo ulug’bek nomidagi

y = a^x mod n .
Bu funksiyaning y qiymatini x argumentning berilgan qiymati bo‘yicha hisoblash qiyinchilik tug‘dirmaydi. Ammo, y ning qiymatini bilgan holda, x ning qiymatini topish murakkab masala hisoblanadi. Umuman olganda,
a^x mod n= b
munosabatni qanoatlantiruvchi x noma’lumning butun qiymatlari har qanday n lar uchun ham mavjud bo‘lavermaydi. a, b, n -parametrlarning yetarli katta qiymatlarida bu yuqorida keltirilgan masalaning yechimi yana ham murakkablashadi.
Kriptografiyada nosimmetrik shifrlash algoritmlari asoslari bilan bog‘liq bo‘lgan quyidagi:

• 
  tub sonlar maydonida GF(p) diskret logarifimlash;
  
• 
  moduli asosi 2 bo‘lgan GF(2ⁿ) maydonda diskret logarifimlash;
  
• 
  elliptik egri chiziq nuqtalari ustida bajariladigan amallarni biror chekli F maydonda amalga oshirish kabi masalalarni yechishning murakkabligi bilan bog‘liq bo‘lgan muammolalar asosida ish ko‘riladi.
  

Kriptobardoshliligi diskret logarifimlash masalasining murakkabligiga asoslangan ko‘plab ochiq kalitli kriptoalgoritmlar mavjud.
Ilmiy tadqiq qilinayotgan obyektlar matematik modellarining sifati darajasi (adekvatligi) ular bilan bog‘liq bo‘lgan jarayonlarni qanchalik to‘liq va aniq ifodalashi bilan belgilanadi. Matematik model boshlang‘ich fikr va mulohazalar asosida o‘tkazilgan tajribalar natijalarini solishtirish hamda tadqiq qilinayotgan obyektning xususiyatlarini belgilovchi parametrlarning tabiiy bog‘liqligi, qonuniyatlarini ifodalovchi tenglik, tengsizlik va tegishlilik munosabatlari bilan aniqlanadi. Kriptologiya biror chekli sondagi alfavit belgilarining ketma-ketligi
bilan ifodalangan ma’lumotni va uning o‘zgarishlari (akslantirilishlari) bilan bog‘liq bo‘lgan jarayonlarni tadqiq qiladi. Kriptografik akslantirishlar matematikaning: to‘plamlar va funksiyalar nazariyasi, algebra, diskret matematika, sonlar nazariyasi, ehtimollar nazariyasi, haqiqiy va kompleks o‘zgaruvchili funksiyalar nazariyasi, murakkablik nazariyasi, axborotlar nazariyasi kabi bo‘limlariga tegishli bo‘lgan matematik modellardan iborat. Murakkablik nazariyasi kriptografik algoritmlarning hisoblash murakkabliklarini tahlil qilish uslubini beradi. Har xil kriptografik algoritmlarning hisoblash murakkabliklarini solishtirib, ularning ishonchlilik - bardoshlilik darajasi aniqlanadi.
Algoritmning murakkabligi. Algoritmning murakkabligi, shu algoritmni to‘la amalga oshirish uchun bajarilishi nazarda tutilgan barcha amallar soni bilan aniqlanadi. Algoritmning hisoblash murakkabligi odatda ikkita parametr bilan aniqlanadi: algoritmda ko‘rsatilgan amallarni bajarishga sarflanadigan vaqt bilan aniqlanadigan murakkablik T va hisoblash qurilmasida algoritm parametlari ustida amallar bajarishda kerak bo‘ladigan registrlarning soni bilan aniqlanadigan - hisoblash qurilmasi xotirasi hajmi bilan bog’liq bo’lgan murakkablik S. Bu T va S parametrlar algoritm xususiyatlaridan kelib chiqib, boshlang‘ich qiymatlarning n o‘lchoviga bog‘liq holda aniqlanadi, ya’ni biror: T=fn) va S funksiyalar bilan.
Algoritmning hisoblash murakkabligi odatda hisoblash murakkabligi qiymatini tartibini ko‘rsatuvchi “O katta” deb ataluvchi belgi bilan ifodalanadi hamda bu belgi n - parametr qiymatining ortishi bilan murakablik funksiyasi ifodasi hadlari ichida qiymati eng tez o‘sadigan hadni ifodalab, boshqa hadlarni hisobga olmaydi. Masalan, algoritmning vaqt bilan aniqlanadigan murakkabligi T=fn)=5n +6n+11 bo‘lsa, u holda uning n tartibli hisoblash murakkabligi O(n ) ko‘rinishda ifodalanadi. Hisoblash murakkabligi baholari boshlang‘ich qiymatlarni, algoritmning xususiyatlaridan kelib chiqqan holda, algoritmni amalga oshirish uchun sarflanadigan vaqt va hisoblash qurilmasi xotirasiga qo‘yadigan talablarini yaqqol namoyon etadi. Masalan, T=O(n)bo‘lsa, boshlang‘ich qiymat o‘lchovining ikki marta o‘sishi vaqtning ham ikki marta o‘sishiga olib keladi; agarda T=O(2ⁿ) bo‘lsa, boshlang‘ich qiymat o‘lchoviga bitta bitning qo‘shilishi
algoritmni amalga oshirish uchun sarflanadigan vaqtni ikki baravar oshishini bildiradi. Algoritmlar vaqt va hisoblash murakkabliklariga ko‘ra quyidagicha klassifikatsiyalanadi (sinflarga ajratiladi):

1. 
   Algoritm doimiy deyiladi, agarda uning murakkabligi qiymati boshlang‘ich qiymat o‘lchoviga bog‘liq bo‘lmasa, ya’ni 0(1);
   
2. 
   Algoritm chiziqli deyiladi, agarda uning murakkabligi qiymatining tartibi 0(n)
   

bo‘lsa;

3. 
   Algoritm polinomial deyiladi, agarda uning murakkabligi qiymatining tartibi
   

0(n^m) (bu yerda m>1) bo‘lsa;

4. 
   Algoritm eksponensial deyiladi, agarda uning murakkabligi qiymatining tartibi 0(^fn)) (bu yerda const=t>1 va fn) - boshlang‘ich qiymat o‘lchovi n ga nisbatan polinomial funksiya) bo‘lsa;
   
5. 
   Murakkabligi qiymatining tartibi 0(^fn)) bo‘lgan eksponensial algoritmlar to‘plamiga qism to‘plam bo‘ladigan algoritmlar superpolinomial deyiladi, agarda fn) - polinomial funksiya t o‘zgarmasga nisbatan tezroq, lekin chiziqli funksiyaga nisbatan sekinroq o‘ssa.
   

Shu yerda ta’kidlash joizki, kriptoalgoritmlarning natijasiga ko‘ra uning noma’lum parametrlarini topishning mavjud algoritmlari superpolinomial murakkablikka ega bo‘lib, noma’lum parametrlarini topishning polinomial murakkablikka ega bo‘lgan algoritmlarini topish mumkin emasligi isbot qilinmagan. Ya’ni biror algoritmning noma’lum parametrini polinomial murakkablikka ega bo‘lgan algoritmlarini topish mumkinligi uning kriptobardoshsiz bo‘lib qolganligini bildiradi.
Sonning teskarisini topishga oid misol: a=21, n=41 6y^ca, a^-1mod n=?
Avvalo, 21 va 41 sonlari o‘zaro tubligini tekshiramiz: (21,41)=1, demak teskarisi mavjud. n=41 - tub son. Eyler funksiyasi F(n) 1-formulaga asosan n-1 ga teng, F(n)=40. Eyler teoremasiga asosan 21 sonining teskarisini topamiz:
21~¹ mod 41 = 21⁴⁰¹ mod 41 = 21³⁹ mod 41 = ^21³ mod 41^ mod 41 = (9261mod4l)¹³ mod 41 =
= 36¹³ mod 41 = (36 • 36¹²) mod 41 = ^36 -(36³ mod41)⁴ j mod 41 = ^36 •(46656
mod 41)⁴ ) mod 41 = = (36 • 39⁴ ) mod 41 = (36 • 2313441) mod41 = (36 16)
mod41 = 576mod41 = 2
Tekshirish: ( 2 • 2 1 )mod4 1 = 4 2mod4 1 = 1. Demak, 21 sonining 41 modul bo‘yicha teskarisi 2 ga teng.