두 요소가 해시 된 경우 충돌이없는 확률을 계산합니다. h (x) = (x^2 + 1) mod3

Question

두 요소를 삽입 한 후 충돌이 발생하지 않을 확률을 어떻게 계산할 수 있습니까? 대답은 4/9이지만 4/9라고 생각하지 않습니다.

Answer 1

저는 이것이 적절한 질문이라고 확신하지 않지만 여기에 답이 나와 있습니다. 결코 합법적 인 수학적 증거는 아니지만 작동합니다.

함수 h (x) = (x^2 + 1) mod3에 대해 몇 가지 샘플 값을 입력 해 보겠습니다.

H (1) = (1 + 1) mod3 = 2mod3 = 2
H (2) = (4 + 1) mod3 = 5mod3 = 2
H (3) = (9 + 1) mod3 = 10mod3 = 1

H (4) = 17mod3 = 2
H (5) = 26mod3 = 2
H (6) = 37mod3 =이 패턴 인해의 본성 계속 1

기능 (제곱 및 1 추가). 우리는 두 가지 요소를 삽입하면

그래서, 우리는 2로 평가하는 우리의 기능에 대한 입력의 (2/3) 기회, 그리고 그것이 1.

로 평가 것이라는 (1/3) 기회를 우리가 충돌을 가질 확률은 두 입력이 모두 2로 계산 될 확률과 1로 평가 될 확률입니다. 이것은 다음과 같이 계산됩니다 :

(2/3) (2/3) + (1/3) (1/3) = 4/9 + 1/9 = 5/9

따라서 두 입력이 충돌하지 않을 확률은 1 - (5/9)

01입니다.

또는 4/9

Answer 2

그 패턴이 모든 동등성 클래스 mod 3 (즉 {0, 1, 2})을 고려하는 이유에 대한 약간의 배경 지식이 있습니다.

그렇다면 분배 동등성에 의해 x mod 3 = 0 다음 x^2 mod 3 = (x mod 3)(x mod 3) mod 3 = (0 * 0) mod 3 = 0, x^2 + 1 mod 3 = 1

그렇다면, x mod 3 = 1x^2 mod 3 = (x mod 3)(x mod 3) mod 3 = (1 * 1) mod 3 = 1 만약 x^2 + 1 mod 3 = 2

x^2 + 1 mod 3 = 2

그것은 여전히 ​​100 % 정식, 그리고 그것은, 그래서 다음 x mod 3 = 2x^2 mod 3 = (x mod 3)(x mod 3) mod 3 = (2 * 2) mod 3 = 1하는 경우 고갈에 의한 멍청한 예가 될 수 있지만이 패턴이 자연수 조합 {0}에 대해 유지되는 이유를 알 수 있습니다. 스택에 수학 형식을 더 잘 알고 싶습니다. 메타를 칠 시간이라고 가정 해 봅시다. :)