Introduction

If you need to compute base ** exponent mod modulus where the exponent and modulus have millions of digits, there is no magic shortcut that makes the problem trivial. The practical answer is to use modular exponentiation with a high-performance big integer library, because the real speed comes from efficient multiplication, reduction, and memory management rather than a clever one-line trick.

Why the Naive Method Is Impossible

The worst approach is to compute base ** exponent first and then take the remainder. The intermediate number would be astronomically large, so both memory use and runtime explode immediately.

Modular exponentiation avoids that by reducing after every multiplication:

1def modexp(base, exponent, modulus):
2    result = 1
3    base %= modulus
4
5    while exponent > 0:
6        if exponent & 1:
7            result = (result * base) % modulus
8        base = (base * base) % modulus
9        exponent >>= 1
10
11    return result

This square-and-multiply algorithm is the core idea used by serious implementations. It never lets intermediate values grow beyond what is needed for the modulus.

Use a Real Big Integer Implementation

For large values, do not write your own arithmetic unless you are doing research. Use a library that already implements:

• fast multiplication algorithms
• modular reduction tuned for huge integers
• sliding-window exponentiation
• memory-efficient representation of large numbers

In Python, the built-in three-argument pow is already optimized:

1base = 7
2exponent = 123456789
3modulus = 1000000007
4
5print(pow(base, exponent, modulus))

For very large inputs in lower-level systems, libraries such as GMP are the standard choice.

Example With GMP

If you care about maximum speed in C or C++, use a library designed for arbitrary-precision arithmetic instead of hand-written loops.

1#include <gmp.h>
2
3int main(void) {
4    mpz_t base, exponent, modulus, result;
5    mpz_inits(base, exponent, modulus, result, NULL);
6
7    mpz_set_str(base, "7", 10);
8    mpz_set_str(exponent, "123456789", 10);
9    mpz_set_str(modulus, "1000000007", 10);
10
11    mpz_powm(result, base, exponent, modulus);
12    gmp_printf("%Zd\n", result);
13
14    mpz_clears(base, exponent, modulus, result, NULL);
15    return 0;
16}

mpz_powm is not just convenient; it is exactly the kind of heavily optimized routine you want when the numbers become enormous.

What Actually Makes It Fast

Fast modular exponentiation for huge integers usually combines several techniques:

• square-and-multiply or a sliding-window variant
• Montgomery or similar modular reduction methods
• asymptotically faster multiplication for large operands
• careful reuse of temporary buffers

The algorithm still does a large amount of work. "Fast" here means "as fast as current arithmetic methods allow", not "instantaneous for million-digit inputs".

Can You Reduce the Exponent First

Sometimes people try to reduce the exponent using Euler's theorem or Carmichael's function. That can help, but only under specific conditions. In particular, you need number-theoretic information about the modulus, and for a large arbitrary modulus that information may be as hard to obtain as the original hard problem.

So the safe general answer is:

• do not assume you can reduce the exponent dramatically
• use the direct modular exponentiation routine unless you have a proven mathematical shortcut for your specific modulus

In cryptographic settings, careless reduction assumptions can make the answer wrong.

Input Size Still Matters

If the exponent and modulus each have several million digits, even excellent libraries will need substantial CPU time and memory. At that scale, performance depends on:

• how large the base is
• whether the modulus is odd or has special structure
• the multiplication algorithms chosen by the library
• the available hardware and memory bandwidth

This is why benchmark results vary so much between languages and machines. The asymptotic method matters, but the implementation details matter too.

Common Pitfalls

The first mistake is trying to compute the full power before taking the modulus. That fails almost immediately for any genuinely large exponent.

Another mistake is writing a custom implementation when a mature big integer library is available. The built-in or library version is almost always faster and more reliable.

People also overestimate theorem-based shortcuts. Exponent reduction only works when its prerequisites are satisfied, and for arbitrary million-digit moduli those prerequisites may be unavailable.

Finally, do not assume that "several million digits" means interactive speed. Even the best algorithm still has to process huge integers many times, so the right expectation is "feasible with strong arithmetic libraries", not "free".

Summary

• Use modular exponentiation, not direct exponentiation followed by %.
• Prefer optimized big integer routines such as Python pow or GMP mpz_powm.
• Real speed comes from efficient multiplication and modular reduction algorithms.
• Exponent reduction tricks are not general-purpose shortcuts.
• For multi-million-digit inputs, the problem is still expensive even with the best tools.