211
правок
Изменения
м
Нет описания правки
:Так как на последнем шаге ''Verifier'' сверяет истинное значение с полученным от ''Prover'', слово будет допущено только в том случае, когда ''Prover'' смог прислать верное значение, что в свою очередь возможно лишь если на одном из предыдущих шагов был верно угадан корень полинома.
:
:<tex>P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \le \frac d p \sum \limits_{i=0}^{m-1} (1 - \frac d p)^i = 1 - (1 - \frac d p)^m \le 1 - (1 - \frac d {3dm})^m = 1 - (1 - \frac 1 {3m})^m \le \frac 1 3</tex>.
Таким образом, построенный нами ''Verifier'' корректен, а значит лемма доказана.
