锐客网

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

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

IT技术起随


没有一个真实的方法来使用STARK 。它是一个非常宽泛的加密和数学架构，同时为不同的应用有不同的设置 ， 以及连续的研究来减少证明者和验证者的复杂性，同时提高可用性 。
此文希望大家能够知道 ， 模运算和素数域是如何运行的，
并且和多项式概念，插值和估值进行结合 。
现在，让我们一起来了解吧！
MIMC
下面是STARK的功能展示：
def mimc(inp, steps, round_constants): start_time = time.time() for i in range(steps-1): inp = (inp**3 + round_constants[i % len(round_constants)]) % modulus print("MIMC computed in %.4f sec" % (time.time() - start_time)) return inp
我们选择MIMC作为案例，因为它（i）很容易理解 ， （ii）在真实世界使用的很多 。函数功能见下图：
注意：在很多关于MIMC的讨论中，你可以典型地看出使用了XOR，而不是+；这是因为MIMC可以在二进制情况下使用 ， 其中添加是XOR；这里我们会在素数领域进行 。
在我们的案例中，常数相对而言会是比较小的列表（例如，64位），这会一直连续地进行周期循环（也就说，在k[64]之后） 。MIMC自身可以获得这个特性，因为MIMC可以向后进行计算（从相应的输出获得输入），但是往后计算需要比向前计算多花费100倍的时间（并且没有方向可以同步进行） 。所以你可以将往后计算的功能想象成计算不能同步的工作量证明，并且往前方向计算的功能可以作为验证的过程 。
x - x(2p-1)/3 是x - x3 的反函数；根据费马小定理 ， 这是真实的，尽管这个定理没有费马大定理出名，但是依然对数学的贡献很大 。
我们尝试使用STARK来进行更加有效的验证 ， 而不是让验证者必须在向前方向运行MIMC，在完成向后计算之后，证明者可以在向前方向进行STARK计算 ， 并且验证者可以很简单地验证STARK 。我们希望计算STARK可以比MIMC向前和向后之间的运行速度差别要?。灾っ髡叩氖奔淙匀皇怯谐跏嫉南蚝蠹扑憷粗鞯嫉?。而并不是STARK计算 。STARK的认证会相对较快（在python语言算法中 ， 可以是0.05-0.3秒） ， 不论初始的计算时间有多长 。
所有的计算会在2256 – 351 * 232 + 1个模内完成；我们使用素数模，因为它是小于2256 最大的素数，其中乘法群包含了232 个子集（也就是说，有这样一个数g，从而在完全232次循环之后 ， G素数环的连续幂模绕回到1），而且是按照6k+5的形式 。首个特性是保证FFT和FRI算法的有效版本，其次是保证MIMC实际上可以向后计算（请见上面提到的x - x(2p-1)/3 使用方法） 。
素域操作
我们通过建立方便的等级来进行素域的操作，同时也有多项式的操作 。代码如下 ， 收首先是小数位数：
class PrimeField(): def __init__(self, modulus): # Quick primality test assert pow(2, modulus, modulus) == 2 self.modulus = modulus def add(self, x, y): return (x+y) % self.modulus def sub(self, x, y): return (x-y) % self.modulus def mul(self, x, y): return (x*y) % self.modulus
并且使用扩展欧几里得算法，来计算模块逆转（这和在素域中计算1/x相同）：
# Modular inverse using the extended Euclidean algorithm def inv(self, a): if a == 0: return 0 lm, hm = 1, 0 low, high = a % self.modulus, self.modulus while low1: r = high//low nm, new = hm-lm*r, high-low*r lm, low, hm, high = nm, new, lm, low return lm % self.modulus
上面的算法是相对昂贵的；幸运地是，对于特定的案例，我们需要做很多的模逆计算，有一个数学方法可以让我们来计算很多逆运算，被称为蒙哥马利批量求逆：
使用蒙哥马利批量求逆来计算模逆 ， 其输入为紫色，输出为绿色，乘法门为黑色，红色方块是唯一的模逆 。

推荐阅读


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

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