211
правок
Изменения
Нет описания правки
Приступим к описанию ''Verifier'''а.
'''Шаг 0 ''' Запросим у ''Prover'''а такое простое число <tex>p</tex>, что <tex>max(2^m+1, k_p) \le p \le 2 \cdot max(2^m+1, k_p)</tex>.
Проверим простоту <tex>p</tex> и условие <tex>max(2^m+1, k_p) \le p \le 2 \cdot max(2^m+1, k_p)</tex> (константу <tex>k_p</tex> определим позднее). Как мы [[Класс P#Примеры задач и языков из P|знаем]], <tex>Primes \in \mathrm{P}</tex>, следовательно на эти операции у ''Verifier'''а уйдёт полиномиальное от размера входа время.
Попросим ''Prover'' 'а прислать ''Verifier'' 'у формулу <tex>A_0(x_1)= \sum\limits_{x_2 = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A(x_1, x_2, ..., x_m)</tex>.
Заметим, что размер формулы <tex>A_0(x_1)</tex> будет полином от длины входа ''Verifier'' 'а, так как <tex>A_0(x_1)</tex> полином от одной переменной степени не выше, чем <tex>d</tex>, а значит его можно представить в виде <tex>A_0(x) = \sum\limits_{i = 0}^{d} C_i \cdot x ^ i</tex> .
Проверим следующее утверждение: <tex>A_0(0) + A_0(1) = k</tex> (здесь и далее под словом «проверим» будем подразумевать следующее: если утверждение верно, ''Verifier'' продолжает свою работу, иначе он прекращает свою работу и возвращет '''false''').
'''Шаг i''' Пусть <tex>r_i = random(p)</tex>. Отправим <tex>r_i</tex> программе ''Prover''. Пусть <tex>A_i(x_{i+1}) = \sum\limits_{x_{i+2} = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A(r_1,\ldots, r_i, x_{i+1}, ..., x_m)</tex>. Попросим ''Prover'' 'а прислать ''Verifier'' 'у формулу <tex>A_i(x_{i+1})</tex>.Проверим следующее утверждение: <tex>A_i(0) + A_i(1) = A_{i-1}(r_i)</tex>. '''Шаг m''' Пусть <tex>r_m = random(p)</tex>. Отправим <tex>r_m</tex> программе ''Prover''. Попросим программу ''Prover'' прислать ''Verifier'' 'у значение <tex>A_m()= A(r_1, r_2, ..., r_m)</tex>. Проверим следующее утверждение: <tex>A_n() = A_{m-1}(r_m)</tex>.А также сами подставим <tex>r_1, r_2, ..., r_m</tex> в <tex>A(x_1, x_2, ..., x_m)</tex> и проверим правильность присланного значения <tex>A_m()</tex>.
Возвращаем '''true'''.
}}
