A dificuldade em compreender alguns passos na prova:"A classe $\mathscr{H}_{p,m}$ de funções de hash é universal"

Question

Eu estava passando o texto de Introdução a Algoritmos de Cormen et.al.onde me deparei com o seguinte trecho sobre a referida prova e etapas onde eu sentia dificuldade são marcados com $\dagger$ e $\dagger\dagger$ respectivamente.

A concepção de uma classe universal de funções de hash

$p$ é um número primo grande o suficiente para que todos os possíveis chave $k$ é no intervalo $0$ para $p — 1$, inclusive.Deixe $Z_p$ denotar o conjunto $\{0, 1,..., p — 1\}$, e deixe $Z_p^*$ denotar o conjunto $\{1, 2,..., p — 1\}$.Por causa da suposição de que o tamanho do universo de chaves é maior do que o número de slots $m$ na tabela de hash, temos $p > m$.

Vamos agora definir a função de hash $h_{a,b}$ para qualquer $a \in Z_p^*$ e qualquer $b \in Z_p$ :

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

A família de todas as funções de hash:

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

---

Teorema:A classe $\mathscr{H}_{p,m}$ de funções de hash é universal.

---

Prova:

Considere duas chaves diferentes $k$ e $l$ a partir de $Z_p$, assim que $k eq l$.Para uma dada função de hash $h_{a,b}$ nós vamos

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

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

Primeiro, note que $r eq s$.Por quê?Observar que

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

Segue-se que $г eq s$ porque $p$ é o primeiro-e tanto $a$ e $(k — l)$ são diferentes de zero módulo $p$, e assim o seu produto também deve ser diferente de zero módulo $p$

Portanto, durante a computação de qualquer $h_{a,b}$ no $\mathscr{H}_{p,m}$, distintas entradas $k$ e $l$ mapa de valores distintos $r$ e $s$ módulo $p$;não há colisões ainda no "mod p nível." Além disso, cada um dos possíveis $p(p — 1)$ escolhas para o par $(a, b)$ com $а eq 0$ produz um diferente, resultando par $(r, s)$ com $r eq s$, desde que nós podemos resolver para $a$ e $b$ dado $r$ e $s$$^\dagger$:

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

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

onde $((k — l)^{-1} \mod p)$ denota a única inverso multiplicativo, o modulo p, de $k — l$.Uma vez que existem apenas $p(p — 1)$ pares possíveis $(r, s)$ com $г eq s$, há um um-para-um a correspondência entre os pares $(a, b)$ com $a eq 0$ e pares $(r, s)$ com $r eq s$.Assim, para um dado par de entradas $k$ e $l$, se nós escolhemos $(a, b)$ uniformemente ao acaso a partir de $Z_p^* \vezes Z_p$, o resultado par $(r, s)$ é igualmente provável de ser qualquer par de valores distintos modulo p.

Ele então segue-se que a probabilidade de que chaves diferentes $k$ e $l$ colidir é igual à probabilidade de que de r $\equiv s (\mod m)$ quando $r$ e $s$ são escolhidos aleatoriamente como distintos valores de módulo $p$. Para um dado valor de $r$, do $p — 1$ possíveis valores restantes para a $s$, o número de valores $s$ de tal forma que $s eq r$ e $s \equiv r (\mod m)$ é, no máximo,$^{\dagger\dagger}$

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

A probabilidade de que $s$ colide com $r$ quando reduzido módulo $m$ é, no máximo, $((p - l)/m)/(p - 1) = 1/m$.

Portanto, para qualquer par de valores distintos $k,l \em Z_p$,

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

de modo que $\mathscr{H}_{p,m}$ é de fato universal.

---

Dúvidas:

Eu não conseguia entender as instruções a seguir na prova:

$\dagger$ :Cada um dos possíveis $p(p — 1)$ escolhas para o par $(a, b)$ com $а eq 0$ produz um diferente, resultando par $(r, s)$ com $r eq s$, desde que nós podemos resolver para $a$ e $b$ dado $r$ e $s$

por isso , "nós podemos resolver para $a$ e $b$ dado $r$ e $s$" $\implica$ "Cada um dos possíveis $p(p — 1)$ escolhas para o par $(a, b)$ com $а eq 0$ produz um diferente, resultando par $(r, s)$ com $г eq s$"

---

$\dagger\dagger$ : Para um dado valor de $r$, do $p — 1$ possíveis valores restantes para a $s$, o número de valores $s$ de tal forma que $s eq r$ e $s \equiv r (\mod m)$ é, no máximo, $\lceil p/m ceil - 1 $ .

Como fazer com que o prazo $\lceil p/m ceil - 1 $ ?

Answer 1

Queremos mostrar que se $k_1 eq k_2\in\mathbb{Z}_p$ em seguida,

$\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}$.

Onde tanto a adição e a multiplicação são realizadas em $\mathbb{Z}_p$.

Começamos por mostrar que se $a\sim U(Z_p^*)$ e $b\sim U(Z_p)$ em seguida, para todos os $k_1 eq k_2\in \mathbb{Z}_p$, $(ak_1+b,ak_2+b)$ é uniformemente distribuída ao longo de $\{(x,y)\in\mathbb{Z}_p^2| x eq y\}$ (i.é. $h(k_1)$ e $h(k_2)$ são solidariamente uniforme em pares com diferentes entradas, onde a aleatoriedade é sobre a escolha de $h$).Este é imediata a partir do fato de que, para todos os $(c_1,c_2)\in\mathbb{Z}_p^2$ com $c_1 eq c_2$, o seguinte sistema de equações lineares:

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

tem uma única solução sobre as variáveis $(a,b)\em Z_p^* imes\mathbb{Z}_p$.Subtraindo a segunda equação da primeira rendimentos $a(k_1-k_2)=c_1-c_2$, já que $k_1-k_2$ é diferente de zero, podemos multiplicar ambos os lados por seu inverso e obter $a=(k_1-k_2)^{-1}(c_1-c_2)$.Se $c_1 eq c_2$, e , em seguida, esta é uma solução diferente de zero para $a$, e podemos extrair $b$ a partir de qualquer uma das duas equações.Assim, para cada par $(c_1,c_2)$ com $c_1 eq c_2$ há exclusivo $(a,b)\em Z_p^* imes\mathbb{Z}_p$ de tal forma que $\big(h_{a,b}(k_1),h_{a,b}(k_2)\big)=(c_1,c_2)$.Isso se instala a sua primeira pergunta.

Agora, divida $\mathbb{Z}_p$ em $\lceil p/m ceil$ baldes, $b_1,...,b_{l=\lceil p/m ceil}$ como segue: $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\}$.Observe que cada balde, exceto a última é de tamanho $m$, e não há dois elementos no mesmo balde de são equivalentes módulo $m$.Podemos concluir que o número de pares diferentes em $\{(x,y)\in\mathbb{Z}_p^2| x eq y\}$ que são equivalentes módulo $m$ é, no máximo, $p(\lceil p/m ceil-1)$, pois depois de escolher o primeiro elemento, você é deixado com $\lceil p/m ceil-1$ elementos para escolher (você deve pegar um diferente balde e cada balde fornece mais de um candidato).Lembrar que $\big(h_{a,b}(k_1),h_{a,b}(k_2)\big)\sim U(\{(x,y)\in\mathbb{Z}_p^2| x eq y\})$, e , assim, podemos finalmente concluir:

$\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}$

Note que, permitindo o $a$ o valor $0$ só torna a nossa análise mais fácil, pois agora $\big(h(k_1),h(k_2)\big)$ é em conjunto uniforme sobre $\mathbb{Z}_p^2$, mas há uma probabilidade de additionaly $\frac{1}{p}$ que $a=0$ e o nosso hashes será equivalente módulo $m$, então, nesse caso, teremos de contentar-se com uma $O(\frac{1}{m})$ obrigado a probabilidade de colisão.