일반화 생일 계산을 감안할 때 해시 길이

Question

은 우리가 다음 우리가 주어진 것으로 가정 해 봅시다 :

• 해시의 길이
• 위 알고, 이제 충돌

을 얻는 기회 주어진 기회 비율을 얻는 데 필요한 "샘플"수를 얻으려면 어떻게해야합니까? 우리는 생일 역설의 Simplified formula을 촬영하면

Answer 1

우리가 얻을 : 그래서

probability = k^2/2N 

:

sqr(probability*2*n) = k 

것은 우리는 N = 2^lenghtHash

작은 테스트를 알고있는 경우 : 해시 = 16 비트 : N = 65536 확률 = 50 % = 0.5

sqr (0.5 * 2 * 65536) = 256 samples 간체 수식으로 시작할 때와 100 % 정확하지는 않지만 큰 해시 및 라거 샘플 세트의 경우 매우 가깝습니다.

수식에 대한 링크는 here입니다.