355
правок
Изменения
м
→Построение универсального множества хеш-функций
<tex dpi = "150">\left\lceil \frac{p}{m}\right\rceil-1\le\frac{p+m-1}{m}-1=\frac{p-1}{m}</tex>.
Вероятность того, что <tex>s</tex> приводит к коллизии с <tex>r</tex> при приведении по модулю <tex>m</tex>, не превышает <tex dpi = "150">\frac{p-1}{m}(p-1)=\cdot\frac{1}{p-1}=\frac{1}{m}</tex>.
Значит, <tex dpi = "150">\forall k\ne l\in Z_p\ P(h_{a,b}(k)=h_{a,b}(l))\le\frac{1}{m}</tex>, что означает, что множество хеш-функций <tex>H_{p,m}</tex> является универсальным.
