Fermat vs Mersenne as modulus

Question

所以有一些數字理論應用，我們需要用大數模來做模數，我們可以選擇模數。有兩個組可以得到巨大的優化 - 費馬和梅森。

所以我們稱一個N位序列爲一個塊。 N通常不是字大小的倍數。對於費馬，我們有M = 2^N + 1，所以2^N = -1 mod M，所以我們取大數的分紅和交替加減。

對於梅森，我們有M = 2^N-1，所以2^N = 1 mod M，所以我們對股息的大小進行求和。

在任何一種情況下，我們最終都會得到一個包含2個塊的數字。如果需要，我們可以再次應用這個算法，最後做一個通用的模算法。

由於加減交替，費馬會使結果的平均值更小。否定的結果不是計算成本高昂，你只需跟蹤標誌並在最後的模步中修復它。但我認爲bignum減法比bignum增加要慢一些。

Mersenne對所有塊進行求和，所以結果稍大，但可以在不增加額外成本的情況下通過算法的第二次迭代來修復。

那麼到底哪個更快？

---

Schönhage–Strassen uses Fermat.有可能比其他的性能等因素，使費爾馬比梅森更好 - 或許這只是直線上升更快。

Answer 1

如果您需要質數模數，您將根據大小的便利性做出決定。

例如，2^31-1是經常在64位體系結構方便的，因爲它適合相當緊密地成32位和與它們中的兩個產品裝配到一個64位字，符號或無符號。

在32位體系結構上，2^16 + 1具有類似的優點。當然，它不適合16位，但如果你把0作爲一個特殊情況，那麼把它們乘以32位字仍然很容易。