Изменения
→Доказательство
Для <tex>r=(ax_1+b)\ mod\ p</tex> и <tex>r=(ax_2+b)\ mod\ p</tex> имеем:
<tex> P(h(x_1)=y_1 \land h(x_2)=y_2)=P(r\ mod\ 2^n = y_1 \land s\ mod\ 2^n = y_2)</tex> где <tex>r \ne s </tex>.Число таких пар <tex>(r \ne , s)</tex> есть <tex>p(p-1)</tex>
Можно записать следующую оценку:
