模乘的快速算法

Question

我正在尝试实现一个大型素数生成器，生成一个 2048 位长度的素数的平均时间约为 40 秒。我从调用堆栈的分析中看到，大部分时间 (99%) 都被模乘占用了，性能变化很大，改变了这个算法。我正在使用 boost::multiprecision::cpp_int 或类似于 boost::multiprecision::uint1024_t 的类型 uint2048_t。这是我使用的两种算法，第一种（不知道为什么）比第二种快很多。我使用的第一个（仅适用于 boost::multiprecision 整数）是一种非常简单的计算模乘法的算法，顺便说一下，大部分时间都来自模运算。

template <typename T>
T mulMod(const T& x, const T& y, const T& p) {
    using boost::multiprecision::cpp_int;
    cpp_int rv = (cpp_int{x} * cpp_int{y}) % cpp_int{p};
    return T{rv};
}

template <typename T>
T mulMod(T a, T b, const T& p) {
    T rv = 0;
    a %= p;
    while (b > 0) {
        if (b & 1)
            rv = (rv + a) % p;
        a = (a << 1) % p;
        b >>= 1;
    }
    return rv;
}

是否有更快的算法（可能用 C++ 实现）来执行模乘法？

Answer 1

你一开始说要生成素数。但是你没有提到mod乘法和素数之间的联系。

Knuth 第 2 卷有很多 material 关于 bignum 算术和寻找大素数的内容。

一条评论提到蒙哥马利mod元算术。这里有一个linkhttps://en.wikipedia.org/wiki/Montgomery_modular_multiplication

OpenSSL 有 BN (bignum) 包，其中包括蒙哥马利乘法和大质数生成。

Gnu Multi Precision (gmp) 库有类似的例程。

您的第二个 mulMod() 例程可以优化。当它在循环中做modp时，参数不大于2*p 所以 mod 可以像这样完成 if( arg >= p) arg -= p.

模乘的快速算法

Fast Algorithm for Modular Multiplicatiion

c++

algorithm

performance

primes

cryptography