Бюрократы, editor, Администраторы
422
правки
Изменения
Нет описания правки
:<tex>\ldots</tex>
:'''Шаг m'''
:Допустим до шага <tex>m</tex> мы ни разу не угадали корень <tex>r_i</tex>, то есть ''Prover'' каждый обманывал Так как на последнем шаге ''Verifier''. Так как на последнем шаге сверяем сверяет истинное значение с присланным полученным от ''Prover'' 'ом, то ''Verifier'' не допустит слово. Значит будет допущено только в том случае, когда ''VerifierProver'' могу допустить слово только смог прислать верное значение, что в свою очередь возможно лишь если на каком-то шаге одном из предыдущих шагов был верно угадан кореньполинома.
:
:<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>.
