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