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).

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://godbolt.org/z/KNX4pi https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method https://en.wikipedia.org/wiki/Modular_exponentiation#Right-t...