How To Find 2 To The Power Of An Insanely Big Number Modulo 10^9

I have an excessively big number (1500+) digits and I need to find 2 ** that number modulo 1_000_000_000 so I wrote this python: n = 1 return_value = 2 while n < To_the_power_of

Solution 1:

You already know that the sequence will repeat. You found the cycle of 4 for mod 10; now, just find it for a billion:

mod_billion = set()
pow_2 = 2
billion = 10**9while pow_2 notin mod_billion:
    mod_billion.add(pow_2)
    pow_2 *= 2if pow_2 > billion:
        pow_2 -= billion

print (pow_2, len(mod_billion))

Three seconds later, we get:

512 1562508

Thus, this sequence repeats every 1562508 items. To find your value for your given power:

cycle = 1562508small_power = big_power % cycle
result = (2 ** small_power) % billion

Solution 2:

Your code makes about 10 ** 1500 iterations, which is indeed insanely long. A useful general technique is exponentiation by squaring, which will give you the result in about 4500 iterations.

If you want to follow the path of the @Prune's answer, you should go along the lines of Fermat's Little Theorem, specifically the Euler's generalization. phi(1_000_000_000) is easy to compute, because 10 ** 9 = (2 ** 9) * (5 ** 9), the product of 2 powers of primes.