211
правок
Изменения
м
Нет описания правки
:Так как на последнем шаге ''Verifier'' сверяет истинное значение с полученным от ''Prover'', слово будет допущено только в том случае, когда ''Prover'' смог прислать верное значение, что в свою очередь возможно лишь если на одном из предыдущих шагов был верно угадан корень полинома.
:
:Посчитаем вероятность того, что ''Verifier'' хотя бы раз угадал корень.
:<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>.