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

Question

我想写一个程序,计算2^x mod n = 1我们有n一个integer但是,我们应该计算x.我写了代码,但是我的代码在大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位,但不大于此.)然后,您需要检查循环是否成功.
• 更改cheak为计算2 ⁿ为1ull << cntr.请务必以包括ull后缀,它说这是一个unsigned long long.

该<<运营商转移位到左侧.将所有位向左移位1会使数字的整数值加倍,假设没有位从值的左侧"移开".所以,1 << n计算2 ⁿ.

后缀ull表示整数常量是unsigned long long.如果省略此后缀,1将被视为整数,并且高于31的移位值将无法执行您想要的操作.

但是,以上所有内容仅仅是对您当前方法的改进.值得理解这些改进以更好地理解语言.但是,他们并没有看到更大的图景.

模块化乘法允许你找到(A*B)mod C为((A mod C)*(B mod C))mod C.这对我们有什么帮助？

我们可以重写整个算法的方式,唯一的限制N和X对机器整数的精度,而不是2 ^Ñ:

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.我使用任意精度计算器验证了2 ⁶⁷⁷³³² mod 111111111 == 1 bc.

它非常快.它在我的电脑上在不到0.07秒的时间内计算出2 ^2323860 mod 4294967293 == 1.

Epilog:这突出了编程中的一个重要原则:实际上,这是一个数学问题而不是编程问题.找到一个有效的解决方案需要了解有关问题域的更多信息,而不是了解C++.一旦我们确定了正确的数学方法,实际的C++代码就是微不足道的.

它通常是这样的,无论是数学还是其他算法方面.并且,你应该不会惊讶地发现离散数学就是我们的许多图形和集合算法的来源.编程语言本身就是大局的一小部分.