因此有一些数论的应用，我们需要做大数的模，我们可以选择模。有两个组可以得到巨大的优化-费马和梅森。
所以我们把N位序列称为块N通常不是单词大小的倍数。
对于fermat，我们有m=2^n+1，所以2^n=-1 mod m，所以我们取红利的块，交替加和减。
对于mersenne，我们有m=2^n-1，所以2^n=1 mod m，所以我们对红利的块求和。
无论是哪种情况，我们最终都可能得到一个占2块的数字。如果需要，我们可以再次应用该算法，最后做一个通用的模算法。
由于交替加减法，费马将使结果平均较小负的结果在计算上并不昂贵，你只需跟踪符号并在最后的模步骤中修复它。但我认为bignum减法比bignum加法慢一点。
mersenne对所有块求和，因此结果稍微大一点，但这可以通过算法的第二次迭代来解决，几乎不需要额外的成本。
最后，哪个更快？
Schönhage–Strassen uses Fermat.除了表现之外，还有其他一些因素使费马比梅森表现得更好，或者可能只是直线上升得更快。
最佳答案
如果你需要一个素数模，你要根据大小的方便性来决定。
例如，2^31-1在64位体系结构上通常很方便，因为它非常适合32位，其中两个的乘积适合64位字，可以是有符号的，也可以是无符号的。
在32位体系结构上，2^16+1具有类似的优势当然，它不太适合16位，但是如果你把0当作一个特例，那么在32位的单词中把它们相乘还是很容易的。
关于algorithm - Fermat和Mersenne作为模量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46025736/