M = 115792089237316195423570985008687907853269984665640564039457584007908834671663
296514807760119017459957299373576180339312098253841362800539826362414936958669 % M = ?
Is it possible to calculate this in Python? Or are there other methods?
1 Answer
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 findK = 2**(N//2) mod M - if
Nwas even,2**N mod M = K * K mod M - if
Nwas odd,2**N mod M = K * K * 2 mod MThat way, there is no need to calculate huge numbers. In reality,powuses 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))
pow. See docs.python.org/3/library/functions.html#pow96514807760119017459957299373576180339312098253841362800539826362414936958669is? 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 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)