Steps to reproduce how I came to believe this:

>>> 2 ** 4324567

Keyboard interrupt the above if you get tired of waiting since the comparitive operation takes less than a second while the above takes like 20.

>>> 2 ** 4324567 % 55

You'll notice the one with the modulous operation is way quicker. The only way this could be possible is if it uses something like the chinese remainder theorem right? What's weird is that if the exponent (being what 2 is to the power of) is a calculated value (like 2 * 2162283 or e where e = 2 * 2162283) it doesn't do this it seems. Can someone explain what's going on here?

CodePudding user response：

The Chinese Remainder Theorem is not used here, and not useful here either. If you want to do modular exponentiation, use 3-argument pow: pow(2, 4324567, 55).

The second line runs much faster because almost all of the work in the first line is actually in constructing the string representation of the result, not in performing the exponentiation. The second line produces a much smaller number which is much quicker to stringify.

CodePudding user response：

The time to do the exponentiation here:

>>> 2 ** 4324567

is actually brief, which you can verify by doing, e.g.,

>>> x = 2 ** 4324567

instead. The vast bulk of the time in the original is actually consumed by converting the internal 4-million bit binary integer into a decimal string for display.

That's expensive. Converting between base-2 and base-10 representations generally takes time quadratic in the number of bits (or digits).

Which is also why the one with the modulus operation appears quicker: there are only 2 decimal digits to display. That goes fast.

However, if you're going to do modular exponentiation, use the 3-argument version of pow() instead. That can be unboundedly more efficient than computing a giant power first and only then doing a modulus operation.