我的问题是:使用Montgomery模乘(只使用加法和乘法)而不是C模运算符% (它翻译成a % n = a - n*(a / n)并使用除法)会带来更快的执行速度吗?直觉上,我想说答案是:不,因为在个人电脑上的(字大小)除法比(字大小的)乘法要昂贵得多,而蒙哥马利的减少实际上会造成开销。
谢谢你的建议。更新:一方面,根据保罗·奥格尔维(见下面的评论),(a * b) % n需要一个乘法和一个除法。另一方面,Montgomery乘法需要(忽略将操作数转换和转换回Montgomery表示所需的<e