completion of every loop, the variable base is equivalent to , where is the number of times the loop has been iterated. (This makes the next working bit of the binary exponent exponent, where the least-significant bit is exponent0). The first line of code simply carries out the multiplication in . If is zero, no code executes since this effectively multiplies the running total by one. If instead is one, the variable base (containing the value of the original base) is simply multiplied in. In this example, the base is raised to the exponent . The exponent is 1101 in binary. There are four binary digits, so the loop executes four times, with values , and . First, initialize the result to 1 and preserve the value of in the variable : . Step 1) bit 1 is 1, so set ; set . Step 2) bit 2 is 0, so do not reset ; set . Step 3) bit 3 is 1, so set ; set . Step 4) bit 4 is 1, so set ; This is the last step so we don't need to square . We are done: is now . Here is the above calculation, where we compute to the power , performed modulo 497. Initialize: and . Step 1) bit 1 is 1, so set ; set . Step 2) bit 2 is 0, so do not reset ; set . Step 3) bit 3 is 1, so set ; set . Step 4) bit 4 is 1, so set ; We are done: is now , the same result obtained in the previous algorithms. The running time of this algorithm is exponent. When working with large values of exponent, this offers a substantial speed benefit over the previous two algorithms, whose time is exponent. For example, if the exponent was 220 = 1048576, this algorithm would have 20 steps instead of 1048576 steps. Implementation in Lua function modPow(b, e, m) if m == 1 then return 0 else local r = 1 b = b % m while e > 0 do if e % 2 == 1 then r = (r*b) % m end b = (b*b) % m e = e >> 1 --use 'e = math.floor(e / 2)' on Lua 5.2 or older end return r end end Left-to-right binary method We can also use the bits of the exponent