求解大数模方程的有效方法

Question

我正在尝试求解以下等式 (x * 0x5DEECE66D + 11) mod 2^47 = 0x310CDAF20000 其中 WolframAlpha is able to solve in a few seconds

我想出了以下 C++ 代码，将模数替换为 &，遗憾的是效率不够高，需要很长时间才能完成：

auto target = 0x310CDAF20000LL;
auto devider = 0x5DEECE66DLL;
auto mask = 1LL << 48 - 1;
auto i = 1LL;

while (1) {
    if ((i * devider + 11) & mask == target) {
        printf("%llx", i);
        break;
    }
    i++;
}

有什么建议吗？

Answer 1

如果 (x * 0x5DEECE66D + 11) mod 2^47 = 0x310CDAF20000 为真，则 (x * 0x5DEECE66D) mod 2^47 = 310CDAF1FFF5 将为真（对于非负数 x 可能取决于 mod 的定义方式）。

将所有内容向左移动 17 位不会改变任何内容。换句话说，如果 (x * 0x5DEECE66D) mod 2^47 = 310CDAF1FFF5 那么 (x * 2EF767336800000) mod 2^64 = 866D78FFFA800000.

对于计算机，对于 64 位（无符号）整数和标准的“截断以适合”，这意味着可以删除 mod。

下一步；如果 (x * 2EF767336800000) mod 2^64 = y 那么 ( (x+1) * 2EF767336800000) mod 2^64 = (y + 2EF767336800000) mod 2^64.

换句话说，从x = 0开始（这里很明显是(x * 2EF767336800000) mod 2^64 = 0）你可以使用“add then AND”来确定x = 1的结果，然后做同样的事情对于 x = 2，然后 ...

这导致：

    auto target = 0x310CDAF20000LL;
    auto devider = 0x5DEECE66DLL;
    auto i = 1LL;

    auto t = (target - 11) << 17;
    auto d = devider << 17;
    uint64_t temp = 0;

    do {
        temp += d;
        i++;
    } while(temp != t);

更进一步就是意识到如果 (x * 2EF767336800000) mod 2^64 = y 那么 ( (x+8) * 2EF767336800000) mod 2^64 = (y + 2EF767336800000 * 8) mod 2^64。这意味着如果您有 8 个起始值（x = 0 到 x = 7），您可以使用 SIMD 并行为 x 执行 8 个值。

Answer 2

从这里开始

25214903917 * x = 53931282661365 (mod 2^47)

根据欧拉定理，

25214903917 ^ phi(2^47) = 1 (mod 2^47)

在这种情况下，欧拉的 totient 很容易计算为 (2^47)/2 = 2^46。所以

25214903917 * 25214903917 ^ (phi(2^47) -1) = 1 (mod 2^47)
25214903917 * 25214903917 ^ (2^46 -1) = 1 (mod 2^47)
25214903917 * (53931282661365 * 25214903917 ^ (2^46 -1)) = 53931282661365 (mod 2^47)
x = 53931282661365 * 25214903917 ^ (2^46 -1) (mod 2^47)

您可以使用平方取幂来计算取幂。代码非常简单（C#）

long desiredResult = 53931282661365;
long q = 25214903917;

long invq = 1;
long tmp = q;
for(int i = 0; i < 46; ++i)
{
    // tmp is q^(2^i)
    invq = (invq * tmp) & 0x7FFFFFFFFFFF;
    tmp = (tmp * tmp) & 0x7FFFFFFFFFFF; 
}
// invq is 105417217348453

long x = (invq * desiredResult) & 0x7FFFFFFFFFFF;
// x is 91896827357865

long test = (q * x) & 0x7FFFFFFFFFFF;
// test is 53931282661365

整个解是n * 2^47 + x，对应WolframAlpha

求解大数模方程的有效方法

Efficient way to solve modulo equation with huge numbers

performance

equation

modulo