I understand nearly everything about cryptology, but runtime and bit operations. I have following problem:
How many bit operations are necessary to calculate a^n mod m for constant m and a.
I have found a lot about this topic, but only for optimised algorithms and without explanations. Could somebody help?
A single grade school multiply, takes at least $2y^2$ individual operations where $y$ is the length of the number in the base you are using. it usually produces a number with roughly twice as many bits roughly. This quadruples the square of $y$, so the total number of operations for raising to the $n$-th power is very roughly going to be: $$2\cdot{4^{n-1}-1\over 3}y^2$$ EDIT: forgot this is modular arithmetic, so it will take less in the sense that the length of the value is limited. Then you account for the fact that mod $m$ is mod $2^x$ and then add a certain value from above that point a certain number of times.