|
Yuqoridagi algoritmni amalga oshirish dasturi C++ tilida quyidagicha bo’ladi:
#include
#include
int Binsearch(int a[], int N, int key, int *t)
{
int l=0, r=N-1, mid=(l+r)/2;
while (l<=r)
{ *t+=1;
if (a[mid]==key) return mid;
if (a[mid]>key) r=mid-1;
else l=mid+1;
mid=(l+r)/2;
}
a[N]=key;
return N;
}
main ()
{
int i, N, mas[1000], key, P, t=0;
cout<cin>>N;
cout<<"Massiv elementlarini kiriting!"<for (i=0; icin>>mas[i];
cout<<"Qidiruv elementini kiriting!"<cin>>key;
P=Binsearch(mas,N,key, &t);
if (P==N) cout<<"Bunday elementni massivga qo'shis lozim"<<" "<
else cout<<"Bunday element bor"<<" "<
getch();
return 0;
}
Agar key = 101 bo’lsa, kerakli yozuv 3 marta taqqoslashlarda aniqlanadi (ketma-ket qidiruvda taqqoslashlar soni 7 ta bo’lar edi).
Agar S – taqqoslashlar soni va n – jadvaldagi elementlar soni bo’lsa, u holda
S = log2n.
Masalan, n = 1024.
Ketma-ket qidiruvda S = 512, binar qidiruvda S = 10.
Agar katta xajmdagi ma’lumotlar ichida qidiruv amalga oshirilayotgan bo’lsa, u holda binar va indeksli ketma-ket qidiruvni umumlashtirib olib borish mumkin. Sababi, har ikkala qidiruv ham tartiblangan massivda amalga oshiriladi.
Hash funktsiyasi O'zboshimchalik uzunligi qatori uchun ba'zi bir butun sonni yoki boshqa uzunlikdagi boshqa qatorni hisoblaydigan matematik yoki boshqa funktsiya deyiladi. Matematik jihatdan buni quyidagicha yozish mumkin:
bu erda M asl xabar bo'lib, ba'zan chaqiriladi prototipi, va h - hash funktsiyasining qiymati deb nomlangan natija (va shuningdek.) hash kodi yoki postlarni hazm qilish (ingliz tilidan xabar hazm)).
Hash funktsiyasining ma'nosi teskari rasmning xarakterli xususiyatini - hash funktsiyasining qiymatini aniqlashdir. Ushbu qiymat odatda ma'lum bir o'lchamga ega, masalan, 64 yoki 128 bit. Muammoni hal qilish uchun hash kodni yana tahlil qilish mumkin. Masalan, ma'lumotni taqqoslash uchun hashing usulidan foydalanish mumkin: agar ikkita ma'lumotlar qatorida hash kodlari turlicha bo'lsa, massivlar farqlanishi kafolatlanadi; agar ular bir xil bo'lsa, massivlar, ehtimol, bir xil. Umumiy holda, manba ma'lumotlari va xesh kodlari o'rtasida bir xil aniq yozishmalar mavjud emas, chunki hash funktsiyalari soni har doim ham kirish ma'lumotlari parametrlaridan kamroq bo'ladi. Shunday qilib, bir xil hash kodlarni beradigan ko'plab kirish xabarlari mavjud (bunday holatlar chaqiriladi) to'qnashuvlar) To'qnashuvlar ehtimoli xesh funktsiyalarini baholashda muhim rol o'ynaydi.
Hash funktsiyalari zamonaviy kriptografiyada keng qo'llaniladi.
Eng oddiy xesh funktsiyani "sum modulo 2" operatsiyasi yordamida quyidagicha tuzish mumkin: biz kirish satrini olamiz, modulo 2 baytini qo'shamiz va xesh funktsiyasining qiymati sifatida bayt natijani qaytaramiz. Hash funktsiyasi qiymatining uzunligi, kirish xabarining hajmidan qat'iy nazar, 8 bitni tashkil qiladi.
Masalan, raqamli holatga keltirilgan asl xabar quyidagicha edi (olti qirrali formatda):
Biz xabarni ikkilik shaklda tarjima qilamiz, baytlarni bir-birining ostiga yozamiz va 2-modulning har bir ustuniga bit qo'shamiz:
0011 1110 0101 0100 1010 0000 0001 1111 1101 0100 ---------- 0110 0101
Natijada (0110 0101 (2) yoki 65 (16)) hash funktsiyasining qiymati bo'ladi.
Biroq, bunday xash funktsiyasidan kriptografik maqsadlarda, masalan, elektron imzoni yaratish uchun foydalanib bo'lmaydi, chunki imzolangan xabar tarkibini chex summasining qiymatini o'zgartirmasdan o'zgartirish juda oson.
Shuning uchun ko'rib chiqilayotgan hash funktsiyasi kriptografik dasturlar uchun mos emas. Kriptografiyada, hash funktsiyasi bir xil qiymatga ega ikkita teskari tasvirni yaratish qiyin bo'lsa, shuningdek, agar funktsiyaning chiqishi kirishga aniq bog'liq bo'lmasa, xesh funktsiyasi yaxshi deb hisoblanadi.
Kriptografik xesh funktsiyalari uchun asosiy talablarni aniqlaymiz:
hash funktsiyasi har qanday hajmdagi xabarga tegishli bo'lishi kerak;
funktsiya qiymatini hisoblash etarlicha tez bo'lishi kerak;
xesh funktsiyasining ma'lum bir qiymati bilan, mos keladigan M o'lchamini topish qiyin (deyarli imkonsiz) bo'lishi kerak;
ma'lum bo'lgan M xabari bilan, asl xabar bilan bir xil hash qiymatga ega boshqa M 'xabarni topish qiyin bo'lishi kerak;
xuddi shu hash qiymatiga ega bo'lgan tasodifiy turli xil xabarlarning har qanday juftligini topish qiyin bo'lishi kerak.
Yuqoridagi barcha talablarga javob beradigan hash funktsiyasini yaratish oson ish emas. Shuni ham yodda tutish kerakki, funktsiyaning kiritilishi o'zboshimchalik bilan olingan ma'lumotlarni oladi va xesh natijasi turli o'lchamdagi ma'lumotlar uchun bir xil bo'lmasligi kerak.
Hozirgi vaqtda amalda, hash funktsiyalari bu blokirovka bo'yicha kirish xabarlari blokini qayta ishlaydigan va kiruvchi xabarning har bir M i bloki uchun h hesh qiymatini shaklning bog'liqligiga qarab hisoblab chiqadigan funktsiyalardir.
h i \u003d H (M i, h i-1),
bu erda h i-1 - oldingi kirish ma'lumotlari bloki uchun hesh funktsiyasini hisoblashda olingan natija.
Natijada h n hash funktsiyasining chiqishi kirish xabarining barcha n bloklari funktsiyasidir.
Hash funktsiyasini yaratish uchun blokli shifr algoritmlaridan foydalanish
Siz hash funktsiyasi sifatida blokdan foydalanishingiz mumkin. Agar ishlatilgan blok algoritmi kriptografik jihatdan bardoshli bo'lsa, unda hash funktsiyasi ishonchli bo'ladi.
Hash kodni olish uchun blok algoritmidan foydalanishning eng oddiy usuli - xabarni CBC rejimida shifrlash. Bunday holda, xabar uzunligi shifrlash algoritmi blokining uzunligiga teng bo'lgan bloklar ketma-ketligi sifatida taqdim etiladi. Agar kerak bo'lsa, kerakli uzunlikdagi blokni olish uchun oxirgi blok o'ngdagi nol bilan to'ldirilgan. Hash qiymati so'nggi shifrlangan matn bloki bo'ladi. Agar ishonchli blokli shifr algoritmi ishlatilgan bo'lsa, hosil qilingan hash qiymati quyidagi xususiyatlarga ega bo'ladi:
Do'stlaringiz bilan baham: |
