MSVC编译器针对Kid-RSA暴力破解代码的异常优化行为问询

核心问题答案 #

1. 你的理解完全正确
   因为d是持续递增的，计算(c*d)%n完全可以通过递推累加实现：假设第k次迭代的d=k，结果为r_k=(c*k)%n，那么第k+1次的结果r_{k+1}=(r_k + c)%n。这种方式彻底避免了开销巨大的128位乘法操作，你实际测试的性能提升（13分钟→5分钟）也直接验证了这个优化的有效性。

2. 两条指令确实无用
   在你切换到累加取模的逻辑后，mov rax, r8和add r8, r9没有参与到核心的r = (r + c) %n计算流程中，属于编译器优化不彻底遗留的冗余代码，对功能和性能都没有贡献，可以安全忽略或通过调整代码让编译器消除它们。

额外补充 #

最初使用__umulh、_udiv128实现128位乘除的方案，每次迭代都要执行完整的大整数乘法+取模，运算量远高于累加取模。而你利用d递增的特性做递推优化，是针对这个暴力破解场景非常精准的性能优化手段。

内容的提问来源于stack exchange，提问作者Costantino Grana