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 .