In order to predict how long a computer will take to execute an algorithm, we need a way to predict how long it will take to execute a single multiplication. Now the time per multiplication really should depend on how many digits are involved. For purposes of this class, we shall say therefore that the number of computer steps needed to multiply two numbers is the number of digits in the result of the multiplication. When the multiplication is done in modular arithmetic, the result is always less than the modulus and hence has about the same number of digits as the modulus. Thus our estimate for the number of computer steps required for a mod m multiplication is 1 plus the number of decimal digits in m.
For example, the naive algorithm for calculating 
takes
k-1 multiplications, all mod m. Since each multiplication takes
roughly 
steps, the total number of computer steps is
roughly 
.
The repeated squaring algorithm for the same computational problem
takes a number of multiplications that is at most twice the number of
bits of k minus one. Since the number of bits of k is at most 1
plus the base-2 logarithm of k, the number of multiplications is at
most 
. Each multiplication is done modulo m, and
therefore takes at most computer steps. Thus the
total number of computer steps for this algorithm is roughly
.