c++ - 如何在不到 1 秒的时间内计算 2^x mod n = 1

Question

我想编写计算 2^x mod n = 1 的程序，我们有 n 是一个 integer 但是，我们应该计算x。我写了代码，但我的代码在 big n 下运行太慢。你能给我一个不到 1 秒的好方法来解决这个问题吗？
这是我的代码:

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    long long int n,cntr=1,cheak;
    cin >> n;
    while (1)
    {
        if (n % 2 == 0)
        {
            break;
        }
        cheak=pow(2, cntr);
        if (cheak % n == 1)
            break;
        cntr++;
    }
    cout << cntr << endl;
} 

Answer 1

对您的当前方法提出的一些修改建议: ^{_{注意:下面是更好的方法!}}

• 更改您的 long long int至 unsigned long long int .这会给你多一点。
• 更改 while (1)至 while (cntr < 64) . unsigned long long的大小可能只有 64 位。 (保证至少为 64 位，但不能大于 64 位。)但是，您随后需要检查循环是否成功。
• 更改 cheak计算 2ⁿ 为 1ull << cntr .确保确保包含ull后缀，表示这是一个 unsigned long long .

<<运算符将位向左移动。将所有位向左移动 1 会使数字的整数值加倍，假设没有位“移出”值的左侧。所以，1 << n将计算 2ⁿ。

后缀ull表示整数常量是 unsigned long long .如果省略此后缀，1将被视为整数，超过 31 的移位值将不会执行您想要的操作。

---

但是，以上所有内容都只是对您当前方法的改进。理解这些改进以更好地理解语言是值得的。然而，他们并没有着眼于大局。

Modular multiplication允许您找到 (A * B) mod C as ( (A mod C) * (B mod C) ) mod C。这对我们有什么帮助？

我们可以重写整个算法，只限制N和 X到机器整数的精度，而不是 2^N:

int main()
{
    unsigned int modulus;
    unsigned int raised = 2;
    int power = 1;

    std::cin >> modulus;

    if (modulus % 2 == 1)
    {
        while (raised % modulus != 1)
        {
            raised = ((unsigned long long)raised * 2) % modulus;
            power++;
        }

        std::cout << power << std::endl;
    } else
    {
        std::cout << "modulus must be odd" << std::endl;
    }
}

投向unsigned long long以上允许 modulus与 2³² - 1 一样大，假设 unsigned int是32位，没有计算溢出。

通过这种方法，即使对于非常大的输入，我也能够非常快速地找到答案。例如，111111111返回 667332 .我使用任意精度计算器 bc 验证了 2⁶⁷⁷³³² mod 111111111 == 1 .

速度非常快。它在我的计算机上用不到 0.07 秒计算了 2^2323860 mod 4294967293 == 1。

---

结语:这突出了编程中的一个重要原则:实际上，这是一个数学问题而不是编程问题。寻找有效的解决方案需要对问题领域的了解比对 C++ 的了解更多。一旦我们确定了正确的数学方法，实际的 C++ 代码就变得微不足道了。

它经常是这样的，无论是数学还是其他算法方面。而且，当您得知离散数学 是我们许 multimap 形和集合算法的来源时，您应该不会感到惊讶。编程语言本身只是全局的一小部分。