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

c++, math

Solution

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 2n 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 2n.

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 2N:

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 232 - 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 2677332 mod 111111111 == 1 using the arbitrary precision calculator `bc`.

It's very fast. It computed 22323860 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.

Problem

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; } ```

Original source