Hacker News Reader

That sounds like a problem that is not described by "Standard 32-bit or 64-bit multiplication as implemented in hardware".

a^n mod m requires O(log(n)) iterations in the outer loop. If m fits in one machine word, each iteration is O(1). If m is large, each iteration is O((log m)^2).

For the specific case of m = 236 and n = 4096, it requires 12 multiplication and 12 division operations. For n = 4095, I think it actually requires 22 multiplications and 22 divisions. Also, if m is a compile time constant, the divisions can be implemented as multiplications instead, which gives a constant factor speedup.

https://godbolt.org/z/KNX4pi

https://en.wikipedia.org/wiki/Modular_exponentiation#Right-t...

O(1) - constant time. The answer is 29. I just happen to know that.

I think you need an 'n' in there before it is meaningful to ask about the runtime.