Namangan davlat universiteti fizika-matematika fakulteti amaliy matematika kafedrasi

f(x) dan foydalanib x ning qiymatini aniqlash faqat kriptoanalitik uchun qiyin. Bu ma`lumotlarni rasmiy qabul qiluvchi esa qayta shifrlash uchun yangi kalit ishlab chiqish yo`lini biladi va osongina bu kalit yordamida shifrlangan ma`lumotni qayta shifrlaydi.
Funktsiya qiyin hisoblanadi deb ataladi, agar uni polinomial ish vaqtida hal qilish algoritmi mavjud bo`lmasa.
Agar shunday algoritm mavjud bo`lsa, funktsiyani hisoblanadigan deb ataladi.
NP-to`liq masalalari qiyin hisoblanadigan masalalar sarasiga kiradi.
f(x) funktsiyani bir tomonlama deb ataladi, agar x dan f(x) ga osongina o`tilib, f(x) dan x ga o`tish qiyin hisoblanadigan bo`lsa.
Biz ma’lumotarni shifrlash va qayta shifralshda algebraik elementlardan foydalanish jarayonini ochib berish jarayonni ryukzak algoritmi misolida ko`rib chiqamiz. Chunki, ryukzak algoritmi yardamida ma’lumotlarni shifrlashda algebraic apparat yaqqol ko’rinadi va tahlil qilish uchun oson bo’ladi. Masala: (Ryukzak masalasi) N ta o`zaro turli hildagi musbat butun A=(a<sub>1</sub>, a<sub>2</sub>, …, a<sub>N</sub>) sonlar va yana bitta k musbat butun soni berilgan bo`lsin. Agar iloji bo`lsa, shunday a<sub>i</sub> larni topish kerakki, ularning yig’indisi k ga teng bo`lsin.
Eng oddiy holda k soni ryukzakning hajmini, a_i larning xar biri esa ryukzakka solinishi mumkin bo`lgan buyum o`lchamini anglatadi. Demak, shunday buyumlar turini aniqlash kerakki, ularning umumiy o`lchami ryukzak o`lchamiga teng bo`lsin.
Misol tariqasida 3231 va 10 ta sonlar to`plami (43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523) ni ko`raylik.
3231 = 129 + 473 + 903 + 561 + 1165 .
SHunday qilib, biz masala echimini topdik. Bunday masalalarni echishda odatda perebor (hamma imkoniyatlarni ko`rib chiqish) usulidan foydalaniladi. Bizning misolimizda 2¹⁰ = 1024 ta qism to`plamlarni ko`rib chiqish etarli. Buni bajarish muammol emas. Ammo, berilgan to`plam elementlari bir necha yuzta bo`lsa-chi? Aniqlik uchun 300 deylik. Bu o`rinda shuni alohida ta`kidlash joizki, murakkabligi hamma imkoniyatlarni ko`rib chiqish algoritmiga nisbatan pastroq bo`lgan algoritmlar ma`lum emas. Amaliy jihatdan 2<sup>300</sup> ta qism to`plamni ko`rib chiqishning iloji yo`q. SHuning uchun ryukzak haqidagi masala NP-to`liq masalalar sirasiga kiradi.
A to`plamining n-qism to`plami f(x) funktsiyani quyidagicha aniqlaydi. 0≤x≤2<sup>n</sup>-1 intervaldagi ihtiyoriy sonni p razryadli ikkilik sanoq sistemasidagi sonlar bilan ifodalash mumkin. Zarur bo`lganda uni oldindan 0 lar bilan to`ldirilishi mumkin. Masalan, 1, 2 va 3 larni 0...01, 0...010, 0...011 tarzida yozilishi mumkin. 2<sup>n</sup>-1 esa 1...111 bo`ladi. f(x) funktsiyani x soniga teng ikkilik sanoq sistemasidagi sonning birlariga mos a_i sonlarning yig’indisi shaklida aniqlaymiz, ya`ni
f(1)=f(0….01)=a<sub>n</sub>
f(2)=f(0….010)=a<sub>n-1</sub>
f(3)=f(0….011)=a<sub>n</sub>+a<sub>n-1</sub>
Bu funktsiyani vektor ko`paytma orqali ifodalasak, f(x)=AB_x bo`ladi. Bu erda B<sub>x</sub> – x – sonining ikkilik sanoq sistemasidagi ko`rinishining vektor-ustuni.
Masalan, 364 soni uchun bu ifodani
f(364) = f(0101101100) = 129 + 473 + 903 + 561 + 1165 = 3231 .
tarzida yozish mumkin. Funktsiyaning yana ayrim qiymatlarini ko`raylik.
f(73) = f(0001001001) = 473 + 561 + 1523 = 2557,
f(617) = f(1001101001) = 43 + 473 + 903 + 561 +1523 = 3503,
f(32) = f(1000110100) = 43+903+302+1165=2413,
f(672) = f(1010100000) = 43 + 215 + 903=1161,