308
правок
Изменения
Нет описания правки
|definition=
Пусть <tex> H </tex> {{---}} универсальное семейство хеш-функций.
Говорят что оно обладает свойством '''попарной независимости''', если для при фиксированных <tex> x, y</tex> <tex> (0 \le x, y \le m-1)</tex> для каждой пары ключей <tex> k, l \in U, (k\ne l) </tex> количество хеш-функций <tex> h \in H </tex>, для которых <tex> h(k) = x </tex> и <tex> h(l) = y </tex> не превышает <tex dpi = "180"> \frac{|H|}{m^2} </tex>.
}}
==Построение универсального множества хеш-функций==
{{Теорема
|statement=
Семейство хеш функций, описанное выше, также является попарно независимым.
|proof=
Для функции <tex>h_{a,b}</tex> получаем
<tex>x \equiv (ak+b)</tex> <tex>mod</tex> <tex>p</tex> <tex>mod</tex> <tex>m</tex>
<tex>y \equiv (al+b)</tex> <tex>mod</tex> <tex>p</tex> <tex>mod</tex> <tex>m</tex>
что можно записать в таком виде:
<tex>x \equiv ak+b+im</tex> <tex>\pmod p</tex>
<tex>y \equiv al+b+jm</tex> <tex>\pmod p</tex>,
где <tex> 0 \le i, j < \frac{p}{m} </tex>.
Стоит отметить, что эту систему считаем верной если '''при каких-либо''' <tex>i</tex> и <tex>j</tex> входящие в неё равенства будут верными.
Выразим отсюда <tex>a</tex> и <tex>b</tex>. Вычтя из первого уравнения второе получим
<tex>x - y \equiv a(k - l)</tex> <tex>mod</tex> <tex>p</tex> <tex>\pmod m</tex>
Теперь сначала первое домножим на <tex>l</tex>, и второе на <tex>k</tex>; вычитая получим
<tex>lx - ky \equiv b(l - k)</tex> <tex>mod</tex> <tex>p</tex> <tex>\pmod m</tex>
}}
==Источники==
