Изменения
Нет описания правки
===Доказательство===
Рассмотрим функцию <tex> h_{a, b} = ((ax+b)\ mod\ p) \ mod\ 2^n</tex> для простого <tex>p \in (2^n; 2^{n+1}]</tex>, любых <tex>a, b \in \mathbb{Z}_p</tex>, <tex>a \ne 0</tex>
Для <tex>r=(ax_1+b)\ mod\ p</tex> и <tex>s=(ax_2+b)\ mod\ p</tex>, где <tex>x_1 \ne x_2 </tex>:
Число таких пар <tex>(r, s)</tex> есть <tex>p(p-1)</tex>
<tex>\frac{1}{p(p-1)} \left(\frac{p}{2^n} \right)^2 \le P(r\ mod\ 2^n = y_1 \land s\ mod\ 2^n=y_2) \le \frac{1}{p(p-1)} \left( \frac{p}{2^n}+1 \right)^2 </tex>
