211
правок
Изменения
м
Нет описания правки
:Вычислим вероятность того, что хотя бы раз корень был угадан.
:<tex>P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) = 1 - (1 - \frac d p)^m \le 1 - (1 - \frac d {3dm})^m \le \frac 1 3</tex>.
:В последнем переходе мы воспользовались [http://ru.wikipedia.org/wiki/Ряд_Тейлора формулой Тейлора] для логарифма и экспоненты, а также тем, что <tex>m>0</tex>.
Таким образом, построенный нами ''Verifier'' корректен, а значит лемма доказана.
