锐客网

  1. 首页 > 睿知 > it技术 > >

Python定义素数函数 python定义函数输出素数( 五 )

IT技术起随


c_of_p需要满足Q(x) = C(P(x), P(g1*x)，K(x)) = P(g1*x) – P(x)**3 – K(x)；目标是对于任何我们放入计算轨道的x（除了最后一步，因为在最后一步之后，就没有步骤），计算轨迹中的下个数值就和之前的相等，再加上循环常量 。与第1部分中的斐波那契示例不同，其中如果某个计算步骤是在k向量，下个就会是k+1向量，我们把低次单位根（ g1 ）的连续幂放下计算轨迹，所以如果某个计算步骤是在x = g1i，下个步骤就会在g1i+1 = g1i * g1 = x * g1 。因此 ， 对于低阶单位根（ g1 ）的每一个幂，我们希望最终会是P(x*g1) = P(x)**3 + K(x)，或者P(x*g1) – P(x)**3 – K(x) = Q(x) = 0 。因此 ， Q(x) 会在低次单位根 g 的所有连续幂上等于零（除了最后一个） 。
# Create the composed polynomial such that # C(P(x), P(g1*x), K(x)) = P(g1*x) - P(x)**3 - K(x) c_of_p_evaluations = [(p_evaluations[(i+extension_factor)%precision] - f.exp(p_evaluations[i], 3) - constants_mini_extension[i % len(constants_mini_extension)]) % modulus for i in range(precision)] print('Computed C(P, K) polynomial')
有个代数定理证明，如果Q(x)在所有这些x坐标，都等于零，那么最小多项式的乘积就会在所有这些x坐标等于零：Z(x) = (x – x_1) * (x – x_2) * … * (x – x_n) 。通过证明在任何单个的坐标，Q(x)是等于零，我们想要证明这个很难，因为验证这样的证明比运行原始计算需要耗费更长的时间，我们会使用一个间接的方式来证明Q(x)是Z(x)的乘积 。并且我们会怎么做呢？通过证明D(x) = Q(x) / Z(x)，并且使用FRI来证明它其实是个多项式，而不是个分数 。
我们选择低次单位根和高次单位根的特定排列，因为事实证明 ， 计算Z(x)，而且除以Z(x)也十分简单：Z 的表达式是两项的一部分 。
需要注意地是 ， 直接计算Z的分子和分母 ， 然后使用批量模逆的方法将除以Z转换为乘法，随后通过 Z(X) 的逆来逐点乘以 Q(x) 的值 。需要注意，对于低次单位根的幂 ， 除了最后一个，都可以得到Z(x) = 0，所以这个计算包含其逆计算就会中断 。这是非常不幸的，虽然我们会通过简单地修改随机检查和FRI算法来堵住这个漏洞，所以就算我们计算错误，也没关系 。
因为Z(x)可以简洁地表达，我们也可以获得另个好处：验证者对于任何特别的x ， 可以快速计算Z(x)，而且还不需要任何提前计算 。对于证明者来说，我们可以接受证明者必须处理大小等于步数的多项式，但我们不想让验证者做同样的事情，因为我们希望验证过程足够简洁 。
# Compute D(x) = Q(x) / Z(x) # Z(x) = (x^steps - 1) / (x - x_atlast_step) z_num_evaluations = [xs[(i * steps) % precision] - 1 for i in range(precision)] z_num_inv = f.multi_inv(z_num_evaluations) z_den_evaluations = [xs[i] - last_step_position for i in range(precision)] d_evaluations = [cp * zd * zni % modulus for cp, zd, zni in zip(c_of_p_evaluations, z_den_evaluations, z_num_inv)] print('Computed D polynomial')
在几个随机点上，进行概念检测D(x) * Z(x) = Q(x)，从而可以验证转账约束，每个计算步骤是之前步骤的有效结果 。但是我们也想验证边界约束，其中计算的输入和输出就是证明者所说的那样 。只是要求证明者提供P(1), D(1), P(last_step)还有D(last_step)的数值 ， 这些都是很脆弱的；没有证明，那些数值都是在同个多项式 。所以 ， 我们使用类似的多项式除法技巧：
# Compute interpolant of ((1, input), (x_atlast_step, output)) interpolant = f.lagrange_interp_2([1, last_step_position], [inp, output]) i_evaluations = [f.eval_poly_at(interpolant, x) for x in xs] zeropoly2 = f.mul_polys([-1, 1], [-last_step_position, 1]) inv_z2_evaluations = f.multi_inv([f.eval_poly_at(quotient, x) for x in xs]) # B = (P - I) / Z2 b_evaluations = [((p - i) * invq) % modulus for p, i, invq in zip(p_evaluations, i_evaluations, inv_z2_evaluations)] print('Computed B polynomial')

推荐阅读


上一篇：狗狗跑步拍摄用什么，狗狗跑步机制作图

下一篇：html5存储方式csdn，html5的web存储对象