to . Note that in every pass through step 3, the equation holds true. When step 3 has been executed times, then, contains the answer that was sought. In summary, this algorithm basically counts up by ones until reaches , doing a multiply by and a modulo operation each time it adds one (to ensure the results stay small). The example , , and is presented again. The algorithm passes through step 3 thirteen times: The final answer for is therefore 445, as in the first method. Like the first method, this requires multiplications to complete. However, since the numbers used in these calculations are much smaller than the numbers used in the first algorithm's calculations, the computation time decreases by a factor of at least in this method. In pseudocode, this method can be performed the following way: function modular_pow(base, exponent, modulus) is if modulus = 1 then return 0 c := 1 for e_prime = 0 to exponent-1 do c := (c * base) mod modulus return c Right-to-left binary method A third method drastically reduces the number of operations to perform modular exponentiation, while keeping the same memory footprint as in the previous method. It is a combination of the previous method and a more general principle called exponentiation by squaring (also known as binary exponentiation). First, it is required that the exponent be converted to binary notation. That is, can be written as: In such notation, the length of is bits. can take the value 0 or 1 for any such that . By definition, . The value can then be written as: The solution is therefore: Pseudocode The following is an example in pseudocode based on Applied Cryptography by Bruce Schneier. The inputs base, exponent, and modulus correspond to , , and in the equations given above. function modular_pow(base, exponent, modulus) is if modulus = 1 then return 0 Assert :: (modulus - 1) * (modulus - 1) does not overflow base result := 1 base := base mod modulus while exponent > 0 do if (exponent mod 2 == 1) then result := (result * base) mod modulus exponent := exponent >> 1 base := (base * base) mod modulus return result Note that upon entering the loop for the first time, the code variable base is equivalent to . However, the repeated squaring in the third line of code ensures that at the