如何計算在ķ（秒）在ķ(s)v_k(s)在二次算術程序中？

在論文Pinocchio: Nearly Practical Verifiable Computation中，有一些多項式 $ v_k(x) $ , $ w_k(x) $ 和 $ y_k(x) $ 代表那裡電路的結構。但是，如第 3 頁中的“具體範例”中的描述， $ v_k(x) $ 是表格項目，如 $ v_1(r_5) = 0 $ 和 $ v_1(r_6) = 1 $ ， 在哪裡 $ r_5 $ 和 $ r_6 $ 是構造的目標多項式的根 $ t(n) $ .

但是教科書的形式是什麼 $ v_1(x) $ 喜歡 $ a_0 + a_1x + a_2x^2 + \dots $ ? 如何計算 $ v_1(s) $ 和 $ g^{v_1(s)} $ ， 如果 $ s $ 不是目標多項式的根 $ t(x) $ ?

從算術電路構造 QAP 多項式的規範算法不會產生標準形式的多項式 ( $ a_0 + a_1x + \dots $ )，但作為一組 $ (x,f(x)) $ 點。為了計算 $ f(s) $ 對於任意 $ s $ ，根據協議的要求，您必須執行一些插值算法來從所有點重建多項式。（這確實是 Pinocchio 的主要缺陷之一，因為插值是一項非常昂貴的操作並且佔用大部分執行時間，即使它不是加密操作。）

引用自：https://crypto.stackexchange.com/questions/30796