55
правок
Изменения
Нет описания правки
{{Теорема
|statement=
Множество хеш функций <tex>H_{p,m}=\{h_{a,b}:a\in Z_p^*,b\in Z_p\}</tex>, где <tex>h_{a,b}(k)=((ak+b)\mod bmod p)\mod bmod m</tex>, <tex>Z_p^*=\{1,2,...\dots,p-1\}</tex>, <tex>Z_p=\{0,1,...\dots,p-1\}</tex>, <tex>p</tex> {{---}} простое число, является универсальным.
|proof=
Рассмотрим <tex>k,l\in Z_p:k\ne l</tex>. Пусть для данной хеш-функции <tex>h_{a,b}</tex>
<tex>r=(ak+b)\mod bmod p</tex>,
<tex>s=(al+b)\mod bmod p</tex>.
<tex>r\ne s</tex>, так как <tex>r-s\equiv a(k-l)\pmod 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)</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 bmod p)\right)\mod bmod p,\ b=(r-ak)\mod bmod p</tex>.
Поскольку имеется только <tex>p(p-1)</tex> возможных пар <tex>(r,s):r\ne s</tex>, то имеется взаимнооднозначное соответствие между парами <tex>(a,b)</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>.
}}
==Источникиинформации==
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2005. — с. 294. — ISBN 5-8459-0857-4
[[Категория: Дискретная математика и алгоритмы]][[Категория:Хеширование]]
