Does the python interpreter implicitly use the Chinese remainder theorem?

Question

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 modulus 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?

Answer 1

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.

EDIT

I'm not sure exactly when this was added, but at least under Python 3.12.3 str(int) no longer takes quadratic time. x = str(2 ** 4324567) completes in about a second on my box now. However, due to earlier "security fixes", you first have to do sys.set_int_max_str_digits(0), else attempts to convert such a large integer raise an exception.

None of this changes that it's still far better to use 3-argument pow() when appropriate. And if you care a whole lot about speed of converting huge ints to decimal, install the gmpy2 extension, which is generally much faster (typically over a factor of 4) at this task.

Answer 2

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.