Difficulté à comprendre quelques étapes de la preuve :"La classe $\mathscr{H}_{p,m}$ des fonctions de hachage est universelle"

Question

Je parcourais le texte Introduction aux algorithmes de Cormen et.Al.où je suis tombé sur l'extrait suivant concernant ladite preuve et les étapes où j'ai ressenti des difficultés sont marquées de $\dague$ et $\dague\dague$ respectivement.

Concevoir une classe universelle de fonctions de hachage

$p$ est un nombre premier suffisamment grand pour que toutes les clés possibles $k$ est dans la gamme $0$ à $p — 1$, inclus.Laisser $Z_p$ désigne l'ensemble $\{0, 1,..., p — 1\}$, et laisse $Z_p^*$ désigne l'ensemble $\{1, 2,..., p — 1\}$.En raison de l’hypothèse selon laquelle la taille de l’univers des clés est supérieure au nombre d’emplacements millions de dollars dans la table de hachage, nous avons $p > m$.

Nous définissons maintenant la fonction de hachage $h_{a,b}$ pour toute $a \in Z_p^*$ et n'importe quel $b \dans Z_p$ :

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

La famille de toutes ces fonctions de hachage :

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

---

Théorème:La classe $\mathscr{H}_{p,m}$ des fonctions de hachage est universelle.

---

Preuve:

Considérons deux clés distinctes $k$ et $l$ depuis $Z_p$, de sorte que $k eq l$.Pour une fonction de hachage donnée $h_{a,b}$ nous laissons

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

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

Notons d'abord que $r eq s$.Pourquoi?Observe ceci

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

Il s'ensuit que $г eq s$ parce que $p$ est premier et les deux $un$ et $(k — l)$ sont différents de zéro modulo $p$, et donc leur produit doit également être différent de zéro modulo $p$

Par conséquent, lors du calcul de tout $h_{a,b}$ dans $\mathscr{H}_{p,m}$, entrées distinctes $k$ et $l$ mapper à des valeurs distinctes $r$ et $s$ module $p$;il n'y a pas encore de collisions au "niveau mod p". De plus, chacun des possibles $p(p — 1)$ choix pour le couple $(a,b)$ avec $а eq 0$ donne une paire résultante différente $(r,s)$ avec $r eq s$, puisque nous pouvons résoudre pour $un$ et $b$ donné $r$ et $s$$^\dague$:

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

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

où $((k — l)^{-1} \mod p)$ désigne l'unique inverse multiplicatif, modulo p, de $k — l$.Puisqu'il n'y a que $p(p — 1)$ paires possibles $(r,s)$ avec $г eq s$, il existe une correspondance biunivoque entre les paires $(a,b)$ avec $a eq 0$ et des paires $(r,s)$ avec $r eq s$.Ainsi, pour toute paire d’entrées donnée $k$ et $l$, si nous choisissons $(a,b)$ uniformément au hasard de $Z_p^* \fois Z_p$, la paire résultante $(r,s)$ est également susceptible d'être n'importe quelle paire de valeurs distinctes modulo p.

Il s’ensuit alors que la probabilité que des clés distinctes $k$ et $l$ collision est égale à la probabilité que $r \equiv s (\mod m)$ quand $r$ et $s$ sont choisies aléatoirement comme valeurs distinctes modulo $p$. Pour une valeur donnée de $r$, de la $p — 1$ valeurs restantes possibles pour $s$, le nombre de valeurs $s$ tel que $s eq r$ et $s \equiv r (\mod m)$ est au maximum$^{\dague\dague}$

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

La probabilité que $s$ entre en collision avec $r$ en cas de réduction modulo millions de dollars est au maximum $((p - l)/m)/(p - 1) = 1/m$.

Par conséquent, pour toute paire de valeurs distinctes $k,l \in Z_p$,

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

de sorte que $\mathscr{H}_{p,m}$ est en effet universelle.

---

Les doutes:

Je n'ai pas pu comprendre les déclarations suivantes dans la preuve :

$\dague$ :Chacun des possibles $p(p — 1)$ choix pour le couple $(a,b)$ avec $а eq 0$ donne une paire résultante différente $(r,s)$ avec $r eq s$, puisque nous pouvons résoudre pour $un$ et $b$ donné $r$ et $s$

pourquoi, "nous pouvons résoudre pour $un$ et $b$ donné $r$ et $s$" $\implique$ "Chacun des possibles $p(p — 1)$ choix pour le couple $(a,b)$ avec $а eq 0$ donne une paire résultante différente $(r,s)$ avec $г eq s$"

---

$\dague\dague$ : Pour une valeur donnée de $r$, de la $p — 1$ valeurs restantes possibles pour $s$, le nombre de valeurs $s$ tel que $s eq r$ et $s \equiv r (\mod m)$ est au maximum $\lceil p/m ceil - 1 $ .

Comment obtient-on le terme $\lceil p/m ceil - 1 $ ?

Answer 1

Nous voulons montrer que si $k_1 eq k_2\in\mathbb{Z}_p$ alors

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

Où l'addition et la multiplication sont effectuées dans $\mathbb{Z}_p$.

Nous commençons par montrer que si $a\sim U(Z_p^*)$ et $b\sim U(Z_p)$ alors pour tout $k_1 eq k_2\in \mathbb{Z}_p$, $(ak_1+b,ak_2+b)$ est uniformément réparti sur $ {(x, y) in mathbb {z} _p ^ 2 | x neq y } $ (c'est à dire. $h(k_1)$ et $h(k_2)$ sont conjointement uniformes sur des paires avec des entrées différentes, où le caractère aléatoire réside dans le choix de $h$).Cela découle du fait que pour tous $(c_1,c_2)\in\mathbb{Z}_p^2$ avec $c_1 eq c_2$, le système d'équations linéaires suivant :

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

a une solution unique sur les variables $(a,b)\in Z_p^* imes\mathbb{Z}_p$.Soustraire la deuxième équation de la première donne $a(k_1-k_2)=c_1-c_2$, depuis $k_1-k_2$ est différent de zéro, nous pouvons multiplier les deux côtés par son inverse et obtenir $a=(k_1-k_2)^{-1}(c_1-c_2)$.Si $c_1 eq c_2$, alors c'est une solution non nulle pour $un$, et nous pouvons extraire $b$ à partir de l’une des deux équations.Ainsi, pour chaque paire $(c_1,c_2)$ avec $c_1 eq c_2$ il y a des uniques $(a,b)\in Z_p^* imes\mathbb{Z}_p$ tel que $\big(h_{a,b}(k_1),h_{a,b}(k_2)\big)=(c_1,c_2)$.Cela règle votre première question.

Maintenant, divisez $\mathbb{Z}_p$ dans $\lceil p/m ceil$ des seaux, $b_1,...,b_{l=\lceil p/m ceil}$ comme suit: $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\}$.Notez que chaque seau sauf le dernier est de taille millions de dollars, et il n'y a pas deux éléments dans le même bucket qui soient équivalents modulo millions de dollars.Nous concluons que le nombre de paires différentes dans $ {(x, y) in mathbb {z} _p ^ 2 | x neq y } $ qui sont équivalents modulo millions de dollars est au maximum $p(\lceil p/m ceil-1)$, puisqu'après avoir choisi le premier élément, il vous reste $\lceil p/m ceil-1$ éléments parmi lesquels choisir (vous devez choisir un compartiment différent et chaque compartiment fournit au plus un candidat).Rappeler que $\big(h_{a,b}(k_1),h_{a,b}(k_2)\big)\sim U(\{(x,y)\in\mathbb{Z}_p^2| x\ néq y\})$, on peut donc enfin conclure :

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

Notez que permettre $un$ prendre la valeur $0$ ne fait que faciliter notre analyse, puisque maintenant $\gros(h(k_1),h(k_2)\grand)$ est conjointement uniforme sur $\mathbb{Z}_p^2$, mais il existe une probabilité supplémentaire de $\frac{1}{p}$ que $a=0$ et nos hachages seront équivalents modulo millions de dollars, donc dans ce cas nous devrons nous contenter d'un $O(\frac{1}{m})$ lié à la probabilité de collision.