210
правок
Изменения
м
Нет описания правки
:'''Шаг i'''
:Заметим, что если на каком-то шаге <tex>A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)</tex>, то начиная со следующего шага <tex>P</tex> может посылать правильные <tex>A_j</tex> и в итоге <tex>V</tex> вернёт '''true'''.
:Для некоторого случайно выбранного <tex>r_i</tex> вероятность того, что <tex>A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)</tex>, не превосходит <tex>\dfrac{d}{p}</tex>, так как <tex>r_i</tex> — корень полинома <tex>(A_{i-1} - \tilde{A}_{i-1})(r_i)</tex>, имеющего степень не больше <tex>d</tex>, а, по [https://ru.wikipedia.org/wiki/%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%B0%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D1%8B основной теореме алгебры], полином имеет ровно <tex> d </tex> корней, и <tex> r_i \in \lbrace 0, \ldots, p -1 \rbrace</tex>.
:<tex>\ldots</tex>
:'''Шаг m'''
