How to Calculate 2^x mod n = 1 in less than 1 second

Question

I want to write the program that Calculate 2^x mod n = 1 we have n is an integer but, we should calculate x.I wrote the code but my code work too slow in big n.Can you suggest me a good way that work less than 1 second to solve this problem.
here is my code:

#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

Some suggested modifications to your current approach:       ^{_{Note: a better approach follows!}}

• Change your long long int to unsigned long long int. This will give you one more bit.
• Change while (1) to while (cntr < 64). The size of unsigned long long is likely only 64 bits. (It's guaranteed to be at least 64 bits, but not larger than that.) You would then need to check whether your loop succeeded, however.
• Change cheak to calculate 2ⁿ as 1ull << cntr. Make sure to include the ull suffix, which says this is an unsigned long long.

The << operator shifts bits to the left. Shifting all the bits to the left by 1 doubles the integer value of the number, assuming no bits "shifted away" off the left of the value. So, 1 << n will compute 2ⁿ.

The suffix ull indicates an integer constant is an unsigned long long. If you omit this suffix, 1 will be treated as an integer, and shift values above 31 will not do what you want.

---

However, all of the above are merely refinements on your current approach. It's worth understanding those refinements to better understand the language. They don't, however, look at the bigger picture.

Modular multiplication allows you to find (A * B) mod C as ( (A mod C) * (B mod C) ) mod C. How does that help us here?

We can rewrite the entire algorithm in a way that only limits N and X to the precision of the machine integers, and not 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;
    }
}

The cast to unsigned long long above allows modulus to be as large as 2³² - 1, assuming unsigned int is 32 bits, without the computation overflowing.

With this approach, I was able to very quickly find answers even for very large inputs. For example, 111111111 returns 667332. I verified 2⁶⁷⁷³³² mod 111111111 == 1 using the arbitrary precision calculator bc.

It's very fast. It computed 2^2323860 mod 4294967293 == 1 in less than 0.07 seconds on my computer.

---

Epilog: This highlights an important principle in programming: Really, this was a math problem more than a programming problem. Finding an efficient solution required knowing more about the problem domain than it did knowing about C++. The actual C++ code was trivial once we identified the correct mathematical approach.

It often goes this way, whether it's the mathematics or some other algorithmic aspect. And, it shouldn't surprise you to learn that discrete mathematics is where many of our graph and set algorithms come from. The programming language itself is a small piece of the big picture.

Answer 2

For each k between 1 and ceil(sqrt(n)), compute 2^k mod n and 2^(k ceil(sqrt(n))) mod n. Then compute the modular inverse of each 2^k. Sort all of the inverse(2^k)s into an array foo and the 2^(k ceil(sqrt(n))s into an array bar. There will be at least one value in common between the two arrays; find it. Say inverse(2^a) = 2^(b ceil(sqrt(n))). Then 2^(a + b ceil(sqrt(n))) = 1 (mod n).