¿Cómo demostrar la independencia por pares de una familia de funciones hash?

Question

Quiero demostrar la independencia por pares de una familia de funciones hash, pero no sé por dónde empezar.

Dada la familia de funciones hash:

H con h(x) = a * x + b (mod M).

( Digamos que h: U -> V, entonces: M es un primo y M >= IUI )

Entonces, ¿cómo demuestro que la familia es independiente por pares? La definición es: La probabilidad de que h(u1) = v1 Y h(u2) = v2 es 1/M^2.

Me imagino que la solución tiene algo que ver con el anillo de módulos, pero no sé cómo llegar a él.

¿Puede alguien ayudarme?

Muchas gracias de antemano.

Answer 1

Bueno, tenemos $h(x) = a x + b \pmod{M}$ .

Como M es primo, se deduce de Teorema de Lagrange que $a x + b$ tiene como máximo una solución módulo $m$ . Por lo tanto, para un $a$ y $b$ Cada uno de ellos $x$ se asignará a un número diferente en el rango $[0 ... M-1]$ y, por lo tanto, la probabilidad de un $x$ para igualar un elemento específico en este rango es $1/M$ . La lógica es la misma para $y$ . Por lo tanto, la probabilidad de que $x$ es igual a un valor específico $i$ y $y$ es igual a otro valor específico $j$ ( $i$ puede ser igual a $j$ ) en el rango $[0 ... M-1] = \frac{1}{M} \cdot \frac{1}{M} = \frac{1}{M^2}$ que es lo que hay que mostrar.

Espero que esto ayude.