Изменения

=={{Определение|definition==<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>}}

=={{Лемма|statement==Для любого <tex>n \in N </tex> существует <tex>H_{n, n}</tex>|proof= Рассмотрим функцию <tex> h_{a, b} = ((ax+b)\ mod\ p)\ mod\ 2^n</tex> для простого <tex>p \in (2^n; 2^{n+1}]</tex>, любых <tex>a, b \in \mathbb{Z}_p</tex>, <tex>a \ne 0</tex>

===Доказательство===Рассмотрим функцию Для <tex> h_{a, b} r= (axax_1+b)\ mod\ p</tex> в поле и <tex> \mathbb{F}_{2^n}</tex> для простого <tex>p \in [2^n; 2^{ns=(ax_2+1}]</tex>, любых <tex>a, b )\in N</tex>, <tex>a mod\ne 0p</tex>

Для <tex>P(r=(ax_1+b)r_1 \ mod\ p</tex> и <tex>rland s =(ax_2+bs_1)= \ mod\ frac{1}{p^2}</tex>, где <tex>x_1 r_1, s_1 \ne x_2 in [0; p)</tex>:.

Раз <tex> P(h(x_1)=y_1 p \land hin (x_2)=y_2)=P(r\ mod\ 2^n = y_1 \land s\ mod\ ; 2^{n = y_2)+1}]</tex> где <tex>r \ne s </tex>.Число таких пар <tex>(r, s)</tex> есть <tex>p(p-1)</tex>то можно записать следующую оценку:

<tex>\frac{1}{p(p-1)} \left(\frac{p}{2^n} \right)^2 \le P(r\ mod\ 2^n = y_1 \land s\ mod\ 2^n=y_2) \le \frac{1}{p(p-1)} \left( \frac{p}{2^n}+1 \right)^2 </tex> <tex> P(h(x_1)=y_1 \land h(x_2)=y_2) = \frac{1}{2^{2k2n}}</tex>

{{Теорема|statement=Для любых <tex>n, k \in N</tex> существует <tex>H_{n, k}</tex>|proof=Построим <tex>H_{n, k}</tex> следующим образом: