Xesh funktsiyasi nima? Kriptografik xesh funktsiyalari

1 - (1 - 1 / n) k

Shunday qilib, biz buni topdik m bit hash kodini faqat tanlang 2m-1   hash-kodlarga mos kelish ehtimoli 0,5 dan katta bo'lishi uchun xabarlar.

Endi quyidagi muammoni ko'rib chiqing: belgilang P (n, k)   to'plamdagi ehtimollik k   har biri olishi mumkin bo'lgan elementlar n   bir xil qiymatga ega bo'lgan kamida ikkita bo'lishi kerak. Nima teng bo'lishi kerak k ga P (n, k) kattaroq bo'lar edi 0,5 ?

Elementlarni tanlab olishning turli xil usullari soni, shunday qilib olish mumkin emas

n (n-1) ... (n-k + 1) \u003d n! / (n-k)!

Elementlarni tanlashning mumkin bo'lgan usullarining umumiy soni n k

Takroriy nusxalarning mavjud emasligi ehtimoli tengdir n! / (n-k)! n k

Takroriy nusxalarning mavjudligi ehtimoli tengdir