冪剰余
さらなる最適化
Pythonで右向きバイナリ法（指数の左端ビットから順に見ていく方法）を使った例である。
import mathdef bits(integer): #Gets number of bits in integer
   result = 0
   while integer:
      integer >>= 1
      result += 1
   return resultdef power(base, exponent, modulo=None): #Allows fast exponentation with and without moduli
   result = 1
   if not modulo:
      iteration = bits(exponent)
      while iteration >= 0:
         result *= result
         if (exponent >> iteration) & 1:
            result *= base
         iteration -= 1
   else:
         firstModulus = base % modulo
         iteration = bits(exponent)
         while iteration >= 0:
            result = (result * result) % modulo
            if (exponent >> iteration) & 1:
               result = (result * firstModulus) % modulo
            iteration -= 1
   return result
この方法では、初期化後は変数 result（とループ変数の iteration）だけが変化していき、他の変数は変化しないという利点がある。このことからハードウェアによる暗号処理の実装を高速かつ安価に実装できる。
firstModulus = base % modulo という行は、ちょっとした最適化であり、前の手法にも適用可能である。
これらのバイナリ法では、指数の2進数表現の各ビットごとに自乗の計算が必要であり、そのビットが1であるときだけ乗算も行う。
右向きバイナリ法では、乗算回数をさらに減らす bit windowing optimization や sliding window optimization がある。
また、剰余を求める計算（%）の高速化として、モンゴメリ乗算がある。
公開鍵暗号における応用
上述のように、m を法とした b の e-冪剰余を求めるには、高々 O(log(e)) 回の加算、乗算、剰余算が必要である。
加算、乗算、剰余算はそれぞれ被演算数の桁数の多項式時間で計算できる。特に、上述のように乗算を行うたびに剰余演算を行えば、被演算数を常に m 未満に保つことができる。よって、m を法とした b の e-冪剰余は、入力サイズ log(b) + log(e) + log(m) の多項式時間で計算できる。
一方、m, b, c から c = bᵉ mod m なる e を求める問題は離散対数問題といわれ、効率的な、つまり入力サイズの多項式時間のアルゴリズムは発見されていない。公開鍵暗号のうちある種のものは、この一方向性を利用して設計されている。