Source: cirosantilli/computational-complexity-of-modular-exponentiation

= Computational complexity of modular exponentiation

https://math.stackexchange.com/questions/2382011/computational-complexity-of-modular-exponentiation-from-rosens-discrete-mathem mentions:
$$
b^n mod m
$$
can be calculated in:
$$
log(m)^2 log(n)
$$
Remember that $log(m)$ and $log(n)$ are the lengths in bits of $m$ and $n$, so in terms of the length in bits $M$ and $N$ we'd get:
$$
M^2 N
$$

Back to article page