355
правок
Изменения
м
→Построение универсального множества хеш-функций
<tex>s=(al+b)\mod p</tex>.
<tex>r\ne s</tex>, так как <tex>r-s\equiv a(k-l)(\!\!\!\mod p)</tex>, а <tex>p</tex> {{---}} простое число, <tex>a</tex> и <tex>(k-l)</tex> не равны нулю по модулю <tex>p</tex>. Значит, произведение <tex>r</tex> и <tex>s</tex> также отлично от нуля по модулю <tex>p</tex>. Таким, образом, коллизии "по модулю <tex>p</tex>" отсутствуют. Более того, каждая из <tex>p(p-1)</tex> возможных пар <tex>(a,b):a\ne0</tex>, приводят к различным парам <tex>(r,s):r\ne s</tex>. Чтобы доказать это, достаточно рассмотреть возможность однозначного определения <tex>a</tex> и <tex>b</tex> по заданным <tex>r</tex> и <tex>s</tex>:
<tex>a=\left((r-s)((k-l)^{-1}\mod p)\right)\mod p,\ b=(r-ak)\mod p</tex>.
Поскольку имеется только <tex>p(p-1)</tex> возможных пар <tex>(r,s):r\ne s</tex>, то имеется взаимнооднозначное соответствие между парами <tex>(a,b):a\ne0</tex> и парами <tex>(r,s):r\ne s</tex>. Таким образом, для любых <tex>k,l</tex> при равномерном случайном выборе пары <tex>(a,b)</tex> из <tex>Z_p^*\times Z_p</tex>, получаемая в результате пара <tex>(r,s)</tex> может быть с равной вероятностью любой из пар с отличающимися значениями по модулю <tex>p</tex>.
Отсюда следует, что вероятность того, что различные ключи <tex>k,l</tex> приводят к коллизии, равна вероятности того, что <tex>r\equiv s(\!\!\!\mod m)</tex> при произвольном выборе отличающихся по модулю <tex>p</tex> значений <tex>r</tex> и <tex>s</tex>. Для данного <tex>r</tex> имеется <tex>p-1</tex> возможное значение <tex>s</tex>. При этом число значений <tex>s:s\ne r</tex> и <tex>s\equiv r(\!\!\!\mod p)</tex>, не превышает
