How to calculate 2 to the power of a large number modulo another large number?

Question

M = 115792089237316195423570985008687907853269984665640564039457584007908834671663

2^{96514807760119017459957299373576180339312098253841362800539826362414936958669} % M = ?

Is it possible to calculate this in Python? Or are there other methods?

You want three-argument `pow`. See https://docs.python.org/3/library/functions.html#pow — Mark Dickinson, Dec 08 '19 at 13:44
Does this answer your question? [pow or \*\* for very large number in Python](https://stackoverflow.com/questions/23759098/pow-or-for-very-large-number-in-python) — Mark Dickinson, Dec 08 '19 at 14:48
do you know how big `96514807760119017459957299373576180339312098253841362800539826362414936958669` is? To loop only 2⁶⁴ times you need ~292 years, suppose you can loop 2 billion times a second. That number is far larger than 2⁶⁴ so you can't get the [modular exponentiation](https://en.wikipedia.org/wiki/Modular_exponentiation) in the lifetime of the universe. You can't also calculate the real power because there are only ~10⁸⁰ particles in the universe which means you don't have enough particles for the memory) — phuclv, Dec 08 '19 at 17:23
duplicates: [calculate mod using pow function python](https://stackoverflow.com/q/32738637/995714), [How to find 2 to the power of an insanely big number modulo 10^9](https://stackoverflow.com/q/52844686/995714), [Behavior of Python ** and % operators with big numbers](https://stackoverflow.com/q/7014512/995714), [Mod function fails in python for large numbers](https://stackoverflow.com/q/34384400/995714) — phuclv, Dec 08 '19 at 17:26
Does this answer your question? [Behavior of Python \*\* and % operators with big numbers](https://stackoverflow.com/questions/7014512/behavior-of-python-and-operators-with-big-numbers) — phuclv, Dec 08 '19 at 17:28
Note that all the previous similar questions refer to quite impenetrable code and long winding articles. The short answer is Mark Dickinson's comment to use the three-argument `pow`. — JohanC, Dec 08 '19 at 22:04

score 1 · Accepted Answer · answered Dec 08 '19 at 20:19

To calculate the result, the three-argument pow does this efficiently, as mentioned by @MarkDickinson in the comments.

A simplified explanation of how this works:

to calculate 2**N mod M, first find K = 2**(N//2) mod M
if N was even, 2**N mod M = K * K mod M
if N was odd, 2**N mod M = K * K * 2 mod M That way, there is no need to calculate huge numbers. In reality, pow uses more tricks, is more general and doesn't need recursion.

Here is some demonstration code:

def pow_mod(B, E, M):
    if E == 0:
        return 1
    elif E == 1:
        return B % M
    else:
        root = pow_mod(B, E // 2, M)
        if E % 2 == 0:
            return (root * root) % M
        else:
            return (root * root * B) % M

M = 115792089237316195423570985008687907853269984665640564039457584007908834671663
E = 96514807760119017459957299373576180339312098253841362800539826362414936958669

print(pow_mod(2, E, M))
print(pow(2, E, M))

How to calculate 2 to the power of a large number modulo another large number?

1 Answers1