ฟังก์ชันแฮช ความชัดเจน และเอนโทรปี

เรื่องนี้มีคำตอบอยู่แล้ว ที่นี่ สำหรับการทำซ้ำ 1 ครั้งและ ที่นี่ สำหรับการวนซ้ำหลายครั้ง แต่เนื่องจากคำตอบหลังนำเสนออาร์กิวเมนต์ฮิวริสติก ฉันจะออกจากบทแทรกที่ 4 ของ กราฟการทำงานและการประยุกต์ใช้ในการโจมตีทั่วไปบนโครงสร้างแฮชแบบวนซ้ำ ซึ่งให้การประมาณที่ดีตามทฤษฎีบทที่ 2 ของ สถิติการทำแผนที่แบบสุ่ม, และ (3.10) จาก บนความสูงของต้นไม้:

บทแทรก 4. อนุญาต $f$ เป็นแผนที่สุ่มใน $\mathcal{F}_N$. แสดงว่า $N = 2^n$. สำหรับ $k \le 2^{n/2}$ความคาดหวังของจำนวนโหนดภาพที่วนซ้ำ k-th ในกราฟการทำงานของ $f$ เป็น $$ (1 - \tau_k)\cdot N \ประมาณ \left(\frac{2}{k} - \frac{2}{3}\frac{\log k}{k^2} - \frac{c}{ k^2} - \dots \right) \cdot N\,. $$ มันแสดงให้เห็นว่า $\lim_{k \to \infty} k\cdot (1 - \tau_k) = 2$. ดังนั้น, $$ \lim_{N \to \infty, k \to \infty, k \le \sqrt{N}}(1 - \tau_k)\cdot N \ประมาณ 2^{n - \log_2 k + 1}\,, $$ ที่ไหน $\tau_k$ ตอบสนองการเกิดขึ้นอีก $\tau_0 = 0, \tau_{k+1} = e^{-1+\tau_k}$, และ $ค$ เป็นค่าคงที่แน่นอน

ดังนั้น แม้ว่าจะมีการสูญเสียเอนโทรปีบางส่วนเนื่องจากการวนซ้ำของฟังก์ชันสุ่ม การสูญเสียนี้จะเพิ่มขึ้นในทางลอการิทึมตามจำนวนการวนซ้ำเท่านั้น ที่จะสูญเสียพูดว่า $32$ บิตของเอนโทรปี คุณต้องวนซ้ำแฮช $2^{32}$ ครั้ง. สำหรับความยาวเอาท์พุตขนาดใหญ่ เช่น $256$ บิต การสูญเสียประเภทนี้เล็กน้อยสำหรับวัตถุประสงค์ในทางปฏิบัติเกือบทั้งหมด