6.1-tasdiq. Agar h xesh funksiya (6.1) qoidaga ko‘ra bir qadamli siquvchi f funksiyaga asosan qurilgan bo‘lsa, u holda f funksiyaning kolliziyaga bardoshliligidan h funksiyaning ham kolliziyaga bardoshliligi kelib chiqadi.
Haqiqatan ham, agarda h funksiya kolliziyaga ega bo‘lsa, u holda biror i-
qadamda f funksiya ham kolliziyaga ega bo‘lishi kerak. Bu erda kolliziyani
konkatenatsiya qilishdan hosil qilingan bir o‘zgaruvchili funksiya deb qaralishi kerak.
Quyida 1) va 2) xossalar orasida o‘zaro bog‘liqlik mavjudligini ko‘rsatiladi:
6.2-tasdiq. Agar xesh funksiya kolliziyaga bardoshli bo‘lsa, u holda u o‘zining xesh qiymatlari teng bo‘lgan ikkita ma’lumotni topishga ham bardoshli bo‘ladi.
Haqiqatan ham, agar berilgan ma’lumotning xesh qiymati bo‘yicha shu xesh qiymatga ega bo‘lgan boshqa ma’lumotni tanlash mumkin bo‘lsa, u holda hosil qilingan ma’lumotlar jufti kolliziyani tashkil qiladi.
6.3 - tasdiq. Kolliziyaga bardoshli xesh funksiya bir tomonlama bo‘lishi shart emas.
Bu tasdiqqa misol sifatida siquvchi bo‘lmagan
f (x) x
funksiyani keltirish
mumkin. Ravshanki bu funksiya kolliziyaga bardoshli, lekin bir tomonlama funksiya emas.
Siquvchi xesh funksiyaga misol sifatida quyidagi shartlar bilan aniqlangan h
funksiya ko‘rilishi mumkin:
h(x) (1, x) , agar x ning uzunligi nbitga teng bo‘lsa;
h(x) (0, g(x)) , agar x ning uzunligi nbitdan katta bo‘lsa.
Bu erda
g(x)
kolliziyaga bardoshli bo‘lgan, siquvchi n bitlik funksiya.
h funksiya kolliziyalarga hamda xesh qiymatlari teng bo‘lgan ikkita ma’lumotni topishga bardoshli funksiya, lekin u bir tomonlama funksiya emas.
Dostları ilə paylaş: |
