Изменения
→Доказательство
Для <tex>r=(ax_1+b)\ mod\ p</tex> и <tex>s=(ax_2+b)\ mod\ p</tex>, где <tex>x_1 \ne x_2 </tex>:
<tex> P(h(x_1)r =y_1 r_1 \land h(x_2)s =y_2s_1)=P(r\ mod\ 2frac{1}{p^n = y_1 \land s\ mod\ 2^n = y_2)}</tex>, где <tex>r \ne s </tex>.Число таких пар <tex>(rr_1, s)</tex> есть <tex>p(p-1)</tex> <tex> P(r=s) = s_1 \frac{1}{p(in [0; p-1)}</tex>.
Раз <tex>p \in (2^n; 2^{n+1}]</tex>, то можно записать следующую оценку:
<tex>\frac{1}{p(p-1)^2} \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)^2} \left( \frac{p}{2^n}+1 \right)^2 </tex>
<tex> P(h(x_1)=y_1 \land h(x_2)=y_2) = \frac{1}{2^{2n}}</tex>
