奇怪的优化器行为

Question

我试图用暴力破解Kid-RSA的问题（我知道我们可以使用扩展欧几里得算法）。

问题是示例任务使用 64 位数字，为了获取乘积然后计算模数，我需要乘积的高 64 位。 MSVC 不支持

__int128

，但 x64 汇编支持，因此我使用两个内在函数来访问乘法的高位部分并执行 128 位除法：

#include <stdio.h>
#include <inttypes.h>
#include <intrin.h>

int main()
{
    uint64_t e = 17459243613;            // public key
    uint64_t n = 66624478857659;         // public key
    uint64_t m = 0x7fafffbffcffdfff / e; // m is a random value that will fit 64 bits when multiplied by e  
    uint64_t c = e * m % n;              // encripted m

    for (uint64_t d = 1; d < n; ++d) {
        // r = c * d % n; // Doesn't work!

        // Multiply and divide using 128 bits
        uint64_t r = 0; 
        _udiv128(__umulh(c, d), c * d, n, &r); 

        if (r == m) {
            printf("Solution: %"PRIu64"\n", d);
            break;
        }
    }
}

查看生成的程序集我注意到优化器正在执行一个奇怪的操作（评论是我的）：

; rcx is d (starts from 1), r9 is c, r8 (starts from c)
for_loop:
        mov     rax, rcx       ; d -> rax
        mul     r9             ; rax*c -> rdx:rax
        mov     rax, r8        ; <-- This is the strange operation
        div     r10            ; rdx:rax % n -> rdx
        cmp     rdx, 526990399 ; 
        je      print_solution ; if (rdx == m) goto print_solution
        inc     rcx            ; ++d
        add     r8, r9         ; r8 += c <-- This is together with the other
        cmp     rcx, r10       ;
        jb      for_loop       ; if (d < n) goto for_loop

这让我意识到，如果你将

c

 乘以 

d

 并且 

d

 不断增加，你可以在每次迭代时将当前值增加 

c

，而根本不需要乘法（因为我们正在使用模数） 

n

）。

看起来好像优化器以某种方式意识到了这一点，但未能正确进行优化，并在代码中留下了部分优化，这实际上是无用的：如果没有这两条指令，一切都会完美运行。

您能对此发表评论吗？我的理解正确吗？这两条指令真的没用吗？

旁注：在我的电脑上，需要 13 分钟才能找到解决方案，而使用 r = (r + c) % n;

 则需要 5 分钟。

Answer 1

对我来说，编译器似乎只是发现它可以通过每次迭代增加

c*d

 来计算 

r8

 的下半部分。但它显然没有看到它如何与 

r9

 和 

__umulh

 相互作用。