我的问题是:使用Montgomery模乘(只使用加法和乘法)而不是C模运算符% (它翻译成a % n = a - n*(a / n)并使用除法)会带来更快的执行速度吗?另一方面,Montgomery乘法需要(忽略将操作数转换和转换回Montgomery表示所需的运算,因为它们只对每个模n完成一次;二进制移位)3乘法。因此,当乘法运算比除法快两倍时,蒙哥马利的运算速度似乎比%快.
我从调用堆栈的分析中看到,大部分时间(99%)是由模乘占用的,并且该算法的性能变化很大。multiprecision::cpp_int或者类似于boost::multiprecision::uint1024_t的uint2048_t类型,这是我使用的两种算法,第一种(不知道为什么)比第二种快很多第一个(它只适用于boost::multiprecision整数),我使用的是一个非常简单的算法来计算模乘,顺便说一下,在这个算法中,大部分时间都是从模运算中获得的。+ a) % p;
a = (a <<