冪剰余
冪剰余を求める最も素朴な手法は、まずb を計算し、その結果を m で割って余りを求める方法である。 冪乗#効率的な演算法にあるように、冪乗の演算には、O(log(e)) 回の乗算が必要であり、それに加えて1回の剰余演算を施すことによって冪剰余を求めることができる。
例として、b = 4, e = 13, m = 497 の場合、c を計算することを考える。
c := 4 13 mod 497 {\displaystyle c:=4^{13}{\bmod {497}}}
4 は 67,108,864 であり、これを 497 で割ると、剰余の c は 445 であることがわかる。
b は1桁、e は2桁の数値だが、b は8桁にもなる。
強い暗号では、b は最低でも256桁の2進数(10進数では77桁)である。典型的な例として b = 5 × 10 と e = 17 の場合を考えてみる。この場合、b は77桁であり、e は2桁だが、b は(10進で)1304桁にもなる。コンピュータにそのような計算をさせることはもちろん可能だが、性能は期待できない。b や e の桁数が増えるほど、b は扱いにくくなる。
次の計算方法は、手順を増やすことになるが、結果としてはこのアルゴリズムのほうが能率が良い。
2つの整数式 a と b があるとき、
( a × b ) mod m = ( ( a mod m ) × ( b mod m ) ) mod m {\displaystyle (a\times b){\bmod {m}}=((a\ {\mbox{mod}}\ m)\times (b\ {\mbox{mod}}\ m)){\bmod {m}}}
である。したがって、最後に剰余演算を1回行うのではなく、前の演算結果 a と b のそれぞれについて m を法とする剰余をとってから乗算をしても、計算結果は変わらない。
たとえば、5 mod 13 を計算するときに、(5 = 5 × 5 であるから)次のように計算できる。
まず、5 mod 13 = 25 mod 13 = 12 を計算する。
次に、(12 × 5) mod 13 = 60 mod 13 = 8 として、結果が得られる。
これによって、剰余算の回数が1回から O(log(e)) 回に増えるが、乗算および剰余算の計算コストは被演算数の桁数によるので、結果としてはこのアルゴリズムのほうが能率が良い。