308
правок
Изменения
м
→Построение попарно независимого множества хеш-функций
<tex>x \equiv (ak+b)\bmod p \bmod m</tex>
<tex>y \equiv (al+b)</tex> <tex>mod</tex> <tex>\bmod p</tex> <tex>mod</tex> <tex>\bmod m</tex>
Выразим отсюда <tex>a</tex> и <tex>b</tex>. Вычтя из первого уравнения второе, получим:
<tex>x - y = a(k - l)</tex> <tex>mod</tex> <tex>\bmod p</tex> <tex>mod</tex> <tex>\bmod m</tex>
Теперь сначала первое домножим на <tex>l</tex>, и второе на <tex>k</tex>. Вычитаем:
<tex>lx - ky = b(l - k)</tex> <tex>mod</tex> <tex>\bmod p</tex> <tex>mod</tex> <tex>\bmod m</tex>
Запишем иначе:
<tex>x - y \equiv a(k - l)+im</tex> <tex>\pmod p</tex>
<tex>lx - ky \equiv b(l - k)+jm</tex> <tex>\pmod p</tex>,
где <tex dpi = "135"> 0 \le i, j < \lfloor \frac{p}{m} \rfloor </tex>.
<tex>k \ne l</tex>, <tex>p</tex> {{---}} простое, тогда
<tex>a \equiv (k - l)^{-1}(x - y - im)</tex> <tex>\pmod p</tex>
<tex>b \equiv (l - k)^{-1}(lx - ky - jm)</tex> <tex>\pmod p</tex>
Остаётся подытожить наши выкладки.
<tex>P( [x \equiv (ak+b)</tex> <tex>mod</tex> <tex>\bmod p</tex> <tex>mod</tex> <tex>\bmod m]</tex> <tex>\wedge</tex> <tex>[y \equiv (al+b)</tex> <tex>mod</tex> <tex>\bmod p</tex> <tex>mod</tex> <tex>\bmod m])</tex>
<tex>=</tex>
<tex dpi = "130">(\frac{1}{m} + o(\frac{1}{m})) \cdot (\frac{1}{m} + o(\frac{1}{m})) = \frac{1}{m^2} + o(\frac{1}{m^2})</tex>
Переход к третьей строчке объясняется тем, что события, объединённые знаком <tex>\wedge</tex>, независимы(т.к. случайные величины здесь только <tex>a</tex> и <tex>b</tex>; <tex>x, y, k, l</tex> {{---}} фиксированы).
}}
