时间戳

首页 > 解决方案 > 求解具有大量数字的模方程的有效方法

performance - 求解具有大量数字的模方程的有效方法

问题描述

我正在尝试解决WolframAlpha 能够在几秒钟内(x * 0x5DEECE66D + 11) mod 2^47 = 0x310CDAF20000解决的以下方程

我想出了以下琐碎的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++;
}

有什么建议么？

标签： performanceequationmodulo

解决方案

让我们从这里开始

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

推荐阅读