Семейство универсальных попарно независимых хеш-функций — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «==Определение== <tex> H_{n, k} = \{ h | h: 2^n \to 2^k \}</tex> называется семейством универсальных попарно нез…»)
(нет различий)

Версия 22:31, 5 мая 2010

Определение

[math] H_{n, k} = \{ h | h: 2^n \to 2^k \}[/math] называется семейством универсальных попарно независимых хеш-функций, если для [math] \forall x_1, x_2 \in 2^n, x_1 \ne x_2[/math] и [math] \forall y_1, y_2 \in 2^k[/math] и равномерной выборке функции [math] h \in H_{n, k} [/math] будет выполнено [math]P(h(x_1) = y_1 \land h(x_2) = y_2) = \frac{1}{2^{2k}}[/math]

Теорема

Для любых [math]n, k \in N[/math] существует [math]H_{n, k}[/math]

Лемма

Для любого [math]n \in N [/math] существует [math]H_{n, n}[/math], что [math] h_{a, b} = (ax+b)[/math] для любых [math]a, b[/math] в поле [math] \mathbb{F}_{2n}[/math]