38
правок
Изменения
Нет описания правки
==Определение==
<tex> H_{n, k} = \{ h | h: 2^n \to 2^k \}</tex> называется семейством универсальных попарно независимых хеш-функций, если для <tex> \forall x_1, x_2 \in 2^n, x_1 \ne x_2</tex> и <tex> \forall y_1, y_2 \in 2^k</tex> и равномерной выборки функции <tex> h \in H_{n, k} </tex> будет выполнено <tex>P(h(x_1) = y_1 \land h(x_2) = y_2) = \frac{1}{2^{2k}}</tex>
==Лемма==
Для любого <tex>n \in N </tex> существует <tex>H_{n, n}</tex>, что <tex> h_{a, b} = (ax+b)</tex> для любых <tex>a, b</tex> в поле <tex> \mathbb{F}_{2n}</tex>
==Теорема==
Для любых <tex>n, k \in N</tex> существует <tex>H_{n, k}</tex>
==Лемма=Доказательство=== Построим <tex>H_{n, k}</tex> следующим образом: При <tex>n=k</tex> существование <tex>H_{n, k}</tex> следует из леммы. Для любого При <tex>n < k </tex> получим переменную <tex> x' </tex> обрезав первые <tex>n \in N -k</tex> бит переменной <tex>x</tex>. Тогда для переменной <tex>x'</tex> существует <tex>H_{n, n}</tex>, что а для <tex>x</tex> - соответственно <tex> h_H_{an, bk} = (ax+b)</tex> для любых . При <tex>n > k </tex> получим <tex>aH_{k, bk}</tex> в поле . <tex> \mathbbH_{Fn, k}_</tex> можно получить, обрезав значение хеш-функции из <tex>H_{2nk, k}</tex>, на первые <tex>n-k</tex> бит.
