Dificultad para entender algunos pasos en la prueba: "La clase $ \ mathscr {h} _ {p, m} $ de las funciones de hash es universal"

Question

Estaba pasando por el texto Introducción a los algoritmos de Cormen ET. Alabama. donde encontré el siguiente extracto con respecto a dicha prueba y los pasos en los que sentí dificultades están marcados con $ \ dagger $ y $ \ daga \ daga $ respectivamente.

diseñando una clase universal de funciones hash

$ P $ es un número primo lo suficientemente grande como para que todas las teclas posibles $ k $ se encuentran en El rango $ 0 $ a $ p - 1 $ , inclusive. Deje que $ z_p $ denote el conjunto $ \ {0, 1, ..., p - 1} $ , y Let $ z_p ^ * $ denota el conjunto $ \ {1, 2, ..., p - 1 \} $ . Porque sobre el supuesto de que el tamaño del universo de las llaves es mayor que el número de tragamonedas $ m $ en la tabla hash, Tenemos $ p> m $ .

Ahora definimos la función hash $ h_ {a, b} $ para cualquier $ a \ in z_p ^ * $ y cualquier $ b \ en z_p $ :

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

La familia de todas estas funciones de hash:

$$ \ mathscr {h} _ {p, m}={h_ {a, b}: A \ in z_p ^ *, b \ in z_p \} $ $

---

Teorema: la clase $ \ mathscr {h} _ {p, m} $ de las funciones de hash es universal.

---

Prueba:

Considere dos teclas distintas $ k $ y $ l $ de $ z_p $ , por lo que $ k \ neq l $ . Para una función de hash dada $ h_ {a, b} $ dejamos

$$ r= (AK + B) \ MOD P $$ ,

$$ S= (Al + B) \ MOD P $$ .

Primero notamos que $ r \ neq s $ . ¿Por qué? Observe que

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

Se deduce que $ г \ neq s $ porque $ p $ es primo y ambos $ A $ y $ (k - l) $ son Modulo de nozero $ P $ , por lo que su producto también debe ser Modulo de nozero $ P $

Por lo tanto, durante el cálculo de cualquier $ H_ {A, B} $ en $ \ mathscr {h} _ {P, M} $ , entradas distintas $ k $ y $ l $ mapa para Valores distintos $ r $ y $ s $ módulo $ p $ ; Todavía no hay colisiones en el "Nivel de mod P". Además, cada uno de los posibles $ P (p - 1) $ opciones para el par $ ( a, b) $ con $ \ neq 0 $ produce un par diferente resultante $ (r, s ) $ con $ r \ neq s $ , ya que podemos resolver para $ a $ y $ b $ Dado $ r $ y $ s $ $ ^ \ daga $ :

$$ A= ((R - S) ((K - L) ^ {- 1} \ mod p)) \ mod p $$ , < / p>

$$ B= (R - AK) \ MOD P $$ ,

donde $ ((k - l) ^ {- 1} \ mod p) $ denota el único inverso multiplicativo, modulo P, de $ k - l $ . Dado que solo hay $ P (p - 1) $ Posibles pares $ (r, s) $ con $ Г \ NEQ S $ , hay una correspondencia uno a uno entre los pares $ (a, b) $ < / span> con $ a \ neq 0 $ y pares $ (r, s) $ con $ r \ neq s $ . Por lo tanto, para cualquier par de entradas proporcionadas $ k $ y $ l $ , si escogemos $ (a, b) $ uniformemente al azar de $ z_p ^ * \ veces z_p $ , el par resultante $ (r, s) $ es igualmente probable que sea un par de valores distintos del módulo p.

Luego sigue que la probabilidad de que las teclas distintas $ k $ A

nd $ l $ chislide es igual a la probabilidad de que $ r \ equIv s (\ mod m) $ Cuando $ r $ y $ s $ se eligen aleatoriamente como valores distintos modulo $ P $ . para un valor dado de $ r $ , del $ p - 1 $ Posibles valores restantes para $ s $ , el número de valores $ s $ tal que $ S \ NEQ R $ y $ s \ Equiv r (\ mod m) $ es como máximo $ ^ {\ daga \ daga} $

$$ \ LCEIL P / M \ RCEIL - 1 <((P + M - 1) / M) - 1 $$ $$= (P-1) / M $$ .

La probabilidad de que $ s $ cheado con $ r $ cuando se reduce el módulo $ m $ está en la mayoría $ ((p - l) / m) / (p - 1)= 1 / m $ .

Por lo tanto, para cualquier par de valores distintos $ k, l \ in z_p $ ,

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

para que $ \ mathscr {h} _ {p, m} $ es de hecho universal.

---

DUDAS:

No pude entender las siguientes afirmaciones en la prueba:

$ \ dagger $ : cada uno de los posibles $ P (p - 1) $ Opciones para el par $ (a, b) $ con $ \ neq 0 $ produce un diferente par $ (r, s) $ con $ r \ neq s $ , ya que podemos resolver $ A $ y $ b $ Dado $ r $ < / span> y $ s $

¿Por qué ", podemos resolver para $ a $ y $ b $ dado $ R $ y $ s $ " $ \ implica $ "Cada uno de los posibles $ P (p - 1) $ opciones para el par $ (a, b) $ con $ \ neq 0 $ produce un par diferente resultante $ (r, s) $ con $ Г \ NEQ S $ "

---

$ \ daga \ daga $ : para un valor dado de $ r $ , de la $ p - 1 $ posibles valores restantes para $ s $ , el número de valores $ s $ tal que $ s \ neq r $ y $ s \ Equiv R (\ MOD M) $ está en la mayoría $ \ lceil p / m \ rceil - 1 $ .

¿Cómo obtenemos el término $ \ lceil p / m \ rceil - 1 $ ?

Answer 1

Queremos demostrar que si $ k_1 \ neq k_2 \ in \ mathbb {z} _p $ luego

$ \ pr \ limits _ {(a, b) \ in \ mathbb {z} _p ^ * \ times \ mathbb {z} _p} [AK_1 + B \ Equiv AK_2 + b \ pmod m] \ le \ frac {1} {m} $ .

Donde tanto la adición y la multiplicación están preformados en $ \ mathbb {z} _p $ .

Comenzamos mostrando que si $ A \ SIM U (Z_P ^ *) $ y $ b \ sim u u (Z_p) $ luego para todos $ k_1 \ neq k_2 \ in \ mathbb {z} _p $ , $ (AK_1 + B, AK_2 + B) $ se distribuye uniformemente sobre $ \ {(x, y) \ in \ mathbb {z} _p ^ 2 | x \ neq y \} $ (es decir, $ h (k_1) $ y $ h (k_2) $ son uniformes conjuntamente en parejas con diferentes entradas, donde la aleatoriedad está sobre la elección de $ h $ ). Esto es inmediato del hecho de que para todos los $ (c_1, c_2) \ in \ mathbb {z} _p ^ 2 $ con $ C_1 \ NEQ C_2 $ , el siguiente sistema de ecuaciones lineales:

$ \ comienzan {align *} & AK_1 + B= C_1 \\ & ak_2 + b= c_2 \ End {align *} $

tiene una solución única a través de las variables $ (a, b) \ in z_p ^ * \ veces \ mathbb {z} _p $ . Restando la segunda ecuación de los primeros rendimientos $ a (k_1-k_2)= c_1-c_2 $ , desde $ k_1-k_2 $ es distinto de cero Podemos multiplicar ambos lados por sus inversos y obtener $ a= (k_1-k_2) ^ {- 1} (c_1-c_2) $ . Si $ c_1 \ neq c_2 $ , entonces esta es una solución distintiva para $ a $ , y podemos Extraer $ b $ de cualquiera de las dos ecuaciones. Por lo tanto, para cada par $ (c_1, c_2) $ con $ c_1 \ neq c_2 $ Hay únicos $ (a, b) \ en z_p ^ * \ times \ mathbb {z} _p $ tal que $ \ big ( h_ {a, b} (k_1), h_ {a, b} (k_2) \ big)= (c_1, c_2) $ . Esto resuelve su primera pregunta.

ahora, divida $ \ mathbb {z} _p $ en $ \ lceil p / m \ rceil $ Cubos, $ b_1, ..., b_ {l=lceil p / m \ rceil} $ de la siguiente manera: $ b_1={0,1, ..., m-1 \}, b_2={m, m + 1, ..., 2m-1 \} $ , ..., < Span Class="Math-contenedor"> $ b_l={m \ lfloor p / m \ rfloor, m \ lceil p / m \ rceil + 1, ..., p-1 \} $ . Tenga en cuenta que cada cubo, excepto el último es de tamaño $ m $ , y no hay dos elementos en el mismo cubo, son módulo equivalente $ m $ . Concluimos que el número de pares diferentes en $ \ {(x, y) \ in \ mathbb {z} _p ^ 2 | X \ NEQ Y \} $ que son un modulo equivalente $ m $ está en la mayoría $ P (\ lceil P / M \ RCEIL-1) $ , ya que después de elegir el primer elemento, se queda con $ \ lceil p / m \ rceil-1 $ Elementos para elegir (debe elegir un cubo diferente y cada bucket proporciona a la mayoría de un candidato). Recordemos que $ \ big (h_ {a, b} (k_1), h_ {a, b} (k_2) \ big) \ sim u (\ {(x, y) \ en \ mathbb {z} _p ^ 2 | x \ neq y \}) $ , por lo que finalmente podemos concluir:

$ \ pr \ limits _ {(a, b) \ in \ mathbb {z} _p ^ * \ times \ mathbb {z} _p} \ izquierda \ izquierda [H_ {a, b} (k_1)= h_ {a, b} (k_2) \ pmod m \ derecha]=frac {p (\ lceil p / m \ rceil-1)} {p (p-1)} \ le \ frac {1} {m} $

Nota que permiten $ a $ para tomar el valor $ 0 $ solo hace que nuestro análisis sea más fácil, ya que Ahora $ \ big (h (k_1), h (k_2) \ big) $ es uniforme conjunta sobre $ \ mathbb { Z} _p ^ 2 $ , pero hay una probabilidad adicional de $ \ frac {1} {p} $ que $ a= 0 $ y nuestros hashes serán módulo equivalente $ m $ , por lo que en este caso tendremos que conformarnos con un $ O (\ frac {1} {m}) $ Bound en la probabilidad de colisión.