증명의 몇 가지 단계를 이해하기 어려움:"해시 함수의 $\mathscr{H}_{p,m}$ 클래스는 보편적입니다."

Question

나는 Cormen et.의 알고리즘 소개 텍스트를 검토하고 있었습니다.알.해당 증명과 관련하여 다음 발췌문을 발견했으며, 어려움을 느꼈던 단계는 로 표시되었습니다. $\단검$ 그리고 $\단검\단검$ 각기.

해시 함수의 범용 클래스 설계

$p$ 가능한 모든 키가 들어갈 수 있을 만큼 충분히 큰 소수입니다. $k$ 범위 내에 있습니다 $0$ 에게 $p — 1$, 포함한.허락하다 $Z_p$ 세트를 표시하다 $\{0, 1,..., p — 1\}$, 그리고 $Z_p^*$ 세트를 표시하다 $\{1, 2,..., p — 1\}$.키 우주의 크기가 슬롯 수보다 크다는 가정 때문에 $m$ 해시 테이블에는 $p > m$.

이제 해시 함수를 정의합니다. $h_{a,b}$ 어떠한 것도 $a \in Z_p^*$ 그리고 어떤 $b \in Z_p$ :

$h_{a,b} = ((a.k + b) \mod p) \mod m $.

이러한 모든 해시 함수 계열은 다음과 같습니다.

$$\mathscr{H}_{p,m}=\{h_{a,b}:a \in Z_p^* , b \in Z_p\}$$

---

정리:클래스 $\mathscr{H}_{p,m}$ 해시 함수는 보편적입니다.

---

증거:

두 개의 서로 다른 키를 고려하십시오. $k$ 그리고 $l$ ~에서 $Z_p$, 하도록 하다 $k eq l$.특정 해시 함수에 대해 $h_{a,b}$ 우리는

$$r = (ak + b) \mod p$$ ,

$$s = (al + b) \mod p $$.

우리는 먼저 $r eqs$.왜?그것을 관찰하십시오

$$r — s = a(k — l) (\mod p)$$ .

그것은 다음과 같습니다 $г eq s$ 왜냐하면 $p$ 은 소수이고 둘 다 $a$ 그리고 $(k — l)$ 0이 아닌 모듈로입니다 $p$, 따라서 그들의 곱은 모듈로가 0이 아니어야 합니다. $p$

그러므로 어떤 계산을 하는 동안 $h_{a,b}$ ~에 $\mathscr{H}_{p,m}$, 별개의 입력 $k$ 그리고 $l$ 고유한 값에 매핑 $r$ 그리고 $s$ 모듈로 $p$;"mod p 수준"에서는 아직 충돌이 없습니다. 게다가 각각의 가능한 $p(p — 1)$ 쌍을 위한 선택 $(a, b)$ ~와 함께 $а eq 0$ 다른 결과 쌍을 생성합니다. $(r, s)$ ~와 함께 $r eq s$, 우리는 다음을 해결할 수 있기 때문에 $a$ 그리고 $b$ 주어진 $r$ 그리고 $s$$^\단검$:

$$a = ((r — s)((k — l)^{-1}\mod p)) \mod p $$,

$$b = (r — ak) \mod p$$ ,

어디 $((k — l)^{-1} \mod p)$ 의 고유한 곱셈 역원인 모듈로 p를 나타냅니다. $k - l$.만 있기 때문에 $p(p — 1)$ 가능한 쌍 $(r, s)$ ~와 함께 $г eq s$, 쌍 사이에는 일대일 대응이 있습니다 $(a, b)$ ~와 함께 $a eq 0$ 그리고 쌍 $(r, s)$ ~와 함께 $r eq s$.따라서 주어진 입력 쌍에 대해 $k$ 그리고 $l$, 우리가 선택한다면 $(a, b)$ 균일하게 무작위로 $Z_p^* imes Z_p$, 결과 쌍 $(r, s)$ p 모듈로의 고유한 값 쌍일 가능성은 동일합니다.

그런 다음 서로 다른 키가 나올 확률은 다음과 같습니다. $k$ 그리고 $l$ 충돌할 확률은 다음과 같습니다. $r \equiv s (\mod m)$ 언제 $r$ 그리고 $s$ 모듈로 고유 값으로 무작위로 선택됩니다. $p$. 주어진 값에 대해 $r$,의 $p — 1$ 가능한 나머지 값 $s$, 값의 개수 $s$ 그렇게 $s eq r$ 그리고 $s \equiv r (\mod m)$ 기껏해야$^{\단검\단검}$

$$\lceil p/m ceil - 1 < ((p + m - 1)/m) - 1$$ $$ =(p-1)/m$$.

확률은 $s$ 와 충돌하다 $r$ 모듈로를 줄이면 $m$ 기껏해야 $((p - l)/m)/(p - 1) = 1/m$.

따라서 임의의 고유한 값 쌍에 대해 $k,l \in Z_p$,

$$Pr\{h_{a,b}(k)=h_{a,b}(l)\}\leq 1/m$$

~하도록 하다 $\mathscr{H}_{p,m}$ 실제로 보편적입니다.

---

의심:

나는 증명에서 다음 진술을 이해할 수 없었습니다.

$\단검$ :각각의 가능한 $p(p — 1)$ 쌍을 위한 선택 $(a, b)$ ~와 함께 $а eq 0$ 다른 결과 쌍을 생성합니다. $(r, s)$ ~와 함께 $r eq s$, 우리는 다음을 해결할 수 있기 때문에 $a$ 그리고 $b$ 주어진 $r$ 그리고 $s$

왜, "우리는 다음 문제를 해결할 수 있습니다. $a$ 그리고 $b$ 주어진 $r$ 그리고 $s$" $\암시$ "각각 가능한 $p(p — 1)$ 쌍을 위한 선택 $(a, b)$ ~와 함께 $а eq 0$ 다른 결과 쌍을 생성합니다. $(r, s)$ ~와 함께 $г eq s$"

---

$\단검\단검$ : 주어진 값에 대해 $r$,의 $p — 1$ 가능한 나머지 값 $s$, 값의 개수 $s$ 그렇게 $s eq r$ 그리고 $s \equiv r (\mod m)$ 기껏해야 $\lceil p/m ceil - 1 $ .

우리는 용어를 어떻게 얻습니까? $\lceil p/m ceil - 1 $ ?

Answer 1

우리는 만약에 $k_1 eq k_2\in\mathbb{Z}_p$ 그 다음에

$\Pr\limits_{(a,b)\in\mathbb{Z}_p^* imes\mathbb{Z}_p}[ak_1+b\equiv ak_2+b \pmod m]\le\frac{1} {m}$.

덧셈과 곱셈이 모두 수행되는 경우 $\mathbb{Z}_p$.

우리는 다음을 보여주는 것으로 시작합니다. $a\sim U(Z_p^*)$ 그리고 $b\심U(Z_p)$ 그럼 모두를 위해 $k_1 eq k_2\in \mathbb{Z}_p$, $(ak_1+b,ak_2+b)$ 에 균일하게 분포되어 있습니다. $ {(x, y) in mathbb {z} _p^2 | x neq y } $ (즉. $h(k_1)$ 그리고 $h(k_2)$ 무작위성은 선택에 달려 있습니다. $h$).이것은 모든 사람에게 즉각적입니다. $(c_1,c_2)\in\mathbb{Z}_p^2$ ~와 함께 $c_1 eq c_2$, 다음과 같은 선형 방정식 시스템:

$ \begin{정렬*} & ak_1+b=c_1 \\ & ak_2+b=c_2 \end{정렬*} $

변수에 대한 고유한 솔루션이 있습니다. $(a,b)\in Z_p^* imes\mathbb{Z}_p$.첫 번째 수율에서 두 번째 방정식을 빼면 $a(k_1-k_2)=c_1-c_2$, 부터 $k_1-k_2$ 0이 아닌 경우 양변에 역수를 곱하면 다음을 얻을 수 있습니다. $a=(k_1-k_2)^{-1}(c_1-c_2)$.만약에 $c_1 eq c_2$, 이면 이는 0이 아닌 해입니다. $a$, 그리고 우리는 추출할 수 있습니다 $b$ 두 방정식 중 하나에서.따라서 각 쌍에 대해 $(c_1,c_2)$ ~와 함께 $c_1 eq c_2$ 독특하다 $(a,b)\in Z_p^* imes\mathbb{Z}_p$ 그렇게 $\big(h_{a,b}(k_1),h_{a,b}(k_2)\big)=(c_1,c_2)$.이것으로 첫 번째 질문이 해결되었습니다.

이제 나누세요 $\mathbb{Z}_p$ ~ 안으로 $\lceil p/m ceil$ 버킷, $b_1,...,b_{l=\lceil p/m ceil}$ 다음과 같이: $b_1=\{0,1,...,m-1\}, b_2=\{m,m+1,...,2m-1\}$,...,$b_l=\{m\lfloor p/m floor, m\lceil p/m ceil+1,...,p-1\}$.마지막 버킷을 제외한 각 버킷의 크기는 다음과 같습니다. $m$, 동일한 버킷에 있는 두 요소는 모듈로로 동일하지 않습니다. $m$.우리는 서로 다른 쌍의 수가 다음과 같다고 결론을 내립니다. $ {(x, y) in mathbb {z} _p^2 | x neq y } $ 이는 모듈로와 동일합니다. $m$ 기껏해야 $p(\lceil p/m ceil-1)$, 첫 번째 요소를 선택한 후에는 $\lceil p/m ceil-1$ 요소 중에서 선택할 수 있습니다(다른 버킷을 선택해야 하며 각 버킷은 최대 하나의 후보를 제공합니다).그것을 기억해 $\big(h_{a,b}(k_1),h_{a,b}(k_2)\big)\sim U(\{(x,y)\in\mathbb{Z}_p^2| x\ 네크 y\})$, 최종적으로 다음과 같은 결론을 내릴 수 있습니다.

$\Pr\limits_{(a,b)\in\mathbb{Z}_p^* imes\mathbb{Z}_p}\left[h_{a,b}(k_1)=h_{a,b}( k_2)\pmod m ight]=\frac{p(\lceil p/m ceil-1)}{p(p-1)}\le \frac{1}{m}$

허용한다는 점에 유의하세요. $a$ 가치를 취하다 $0$ 우리의 분석을 더 쉽게 만들어 줄 뿐입니다. $\big(h(k_1),h(k_2)\big)$ 공동으로 균일하다 $\mathbb{Z}_p^2$, 그러나 다음과 같은 추가 확률이 있습니다. $\frac{1}{p}$ 저것 $a=0$ 우리의 해시는 모듈로와 동일합니다 $m$, 따라서 이 경우 우리는 다음 사항에 만족해야 합니다. $O(\frac{1}{m})$ 충돌 확률에 묶여 있습니다.