锐客网

  1. 首页 > 生活百科 > it技术 > >

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

IT技术起随


你可以自己通过一些输入来运行代码，并且看看是否能得到想要的结果，当你使用eval_poly_at的时候，给出你期望得到的答案 。例如：
fft.fft([3,1,4,1,5,9,2,6], 337, 85, inv=True) [46, 169, 29, 149, 126, 262, 140, 93]f = poly_utils.PrimeField(337)[f.eval_poly_at([46, 169, 29, 149, 126, 262, 140, 93], f.exp(85, i)) for i in range(8)] [3, 1, 4, 1, 5, 9, 2, 6]
傅里叶变换会把[x[0] …. x[n-1]]作为输入，并且它的目标是输出x[0] + x[1] + … + x[n-1]作为首个元素，x[0] + x[1] * 2 + … + x[n-1] * w**(n-1)作为第二个元素，等等；快速傅里叶变换可以通过把数据分为两半，来完成这个，在两边都进行FFT，然后将结果结合在一起 。
上图就是信息如何进行FFT运算的解释 。请注意FFT是如何进行两次数据复制，并且进行粘合，直到你得到一个元素 。
现在，我们把所有部分组合起来，看看整件事情是如何：def mk_mimc_proof(inp, steps, round_constants) ， 它生成运行 MIMC 函数的执行结果的证明，其中给定的输入为步骤数 。首先，是一些 assert 函数：
# Calculate the set of x coordinates xs = get_power_cycle(root_of_unity, modulus) column = [] for i in range(len(xs)//4): x_poly = f.lagrange_interp_4( [xs[i+len(xs)*j//4] for j in range(4)], [values[i+len(values)*j//4] for j in range(4)], ) column.append(f.eval_poly_at(x_poly, special_x))
扩展因子是我们将要拉伸的计算轨迹（执行 MIMC 函数的“中间值”的集合） 。
m2 = merkelize(column) # Pseudo-randomly select y indices to sample # (m2[1] is the Merkle root of the column) ys = get_pseudorandom_indices(m2[1], len(column), 40) # Compute the Merkle branches for the values in the polynomial and the column branches = [] for y in ys: branches.append([mk_branch(m2, y)] + [mk_branch(m, y + (len(xs) // 4) * j) for j in range(4)])
我们需要步数乘以扩展因子最多为 2^32，因为当 k32 时，我们没有 2^k 次的单位根 。
computational_trace_polynomial = inv_fft(computational_trace, modulus, subroot) p_evaluations = fft(computational_trace_polynomial, modulus, root_of_unity)
我们首个计算会是得出计算轨迹；也就是说，所有的计算中间值，从输入到输出 。
assert steps = 2**32 // extension_factor assert is_a_power_of_2(steps) and is_a_power_of_2(len(round_constants)) assert len(round_constants)steps
然后，我们会从将计算轨迹转换为多项式，在单位根 g （其中，g^steps = 1）的连续幂的轨迹上“放下”连续值，然后我们对更大的集合——即单位根 g2 的连续幂，其中 g2^steps * 8 = 1（注意 g2^8 = g）的多项式求值 。
# Generate the computational trace computational_trace = [inp] for i in range(steps-1): computational_trace.append((computational_trace[-1]**3 + round_constants[i % len(round_constants)]) % modulus) output = computational_trace[-1]
黑色： g1 的幂 。紫色： g2 的幂 。橙色：1 。你可以将连续的单位根看作一个按这种方式排列的圆圈 。我们沿着 g1的幂“放置”计算轨迹，然后扩展它来计算在中间值处（即 g2 的幂）的相同多项式的值 。
我们可以将MIMC的循环常数转换为多项式 。因为这些循环常数链是非常通常发生地（在我们的测试中 ， 每64个步骤都会进行），最终证明他们形成了64阶的多项式，而且外面可以很容易计算出它的表达式，以及扩展式：
skips2 = steps // len(round_constants) constants_mini_polynomial = fft(round_constants, modulus, f.exp(subroot, skips2), inv=True) constants_polynomial = [0 if i % skips2 else constants_mini_polynomial[i//skips2] for i in range(steps)] constants_mini_extension = fft(constants_mini_polynomial, modulus, f.exp(root_of_unity, skips2))
假设其中有8192个步骤，并且有64个循环常数 。这是我们想要做的：我们正在进行FFT，从而计算循环常数来作为g1128 的功能 。然后我们在之间加入很多零 ， 来完成g1本身的功能 。因为g1128 大约每64步进行循环 ， 我们知道g1这个功能也会同样 。我们只计算这个扩展中的512个步骤，因为我们知道这个扩展会在每512步之后重复 。现在，我们按照斐波那契案例中那样 ， 计算C(P(x)) ， 除了这次是计算 ， 需要注意 ， 我们不在计算使用系数形式的多项式；而是根据高次单位根的连续幂来对多项式进行求值 。

推荐阅读


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

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