途中で剰余をとる
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/11 10:07 UTC 版)
次の計算方法は、手順を増やすことになるが、結果としてはこのアルゴリズムのほうが能率が良い。 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 を法とする剰余をとってから乗算をしても、計算結果は変わらない。 たとえば、53 mod 13 を計算するときに、（53 = 52 × 5 であるから）次のように計算できる。 まず、52 mod 13 = 25 mod 13 = 12 を計算する。 次に、(12 × 5) mod 13 = 60 mod 13 = 8 として、結果が得られる。 これによって、剰余算の回数が1回から O(log(e)) 回に増えるが、乗算および剰余算の計算コストは被演算数の桁数によるので、結果としてはこのアルゴリズムのほうが能率が良い。また一般に、m がその計算機環境における1語の桁数の半分以下に収まる場合 (a mod m) × (b mod m) の結果が必ず1語に収まるので、Bignum を一切使わない能率の良い計算が可能である。 次の例は、基本としてこの手法を利用し、さらに指数法則の b2x = (b2)x を活用したコードであり、ほぼ C# または C++ のコードとなっている。クラス Bignum は任意の巨大な整数を表現できるものとする。引数 b は底、e は指数、m は法である。記号 "%" は、剰余演算 (mod) を示す。 Bignum modpow(Bignum b, Bignum e, Bignum m) { Bignum result = 1; while (e > 0) { if ((e & 1) == 1) result = (result * b) % m; e >>= 1; b = (b * b) % m; } return result;} このコードは、Schneier (1995, p. 244)にあるものに基づいており、一つの while ループで冪剰余の計算に必要な全ての作業を行っている。 例として、b = 4, e = 13, m = 497 をこの手法で計算する。e を2進数で表記すると 1101 になる。e が2進数では4桁なので、ループは4回しか回らない。 ループに最初に入ったとき、各変数の値は b = 4, e = 1101（2進数）, result = 1 である。e の右端のビットは 1 なので、result は (1 × 4) % 497 つまり 4 となる。e は右にシフトされて 110（2進数）となり、b は (4 × 4) % 497 すなわち 16 になる。 繰返しの2回目では、e の右端ビットは 0 なので result は 4 のままとなる。e は右にシフトされて 11（2進数）となり、b は (16 × 16) % 497 つまり 256 となる。 繰返しの3回目では、e の右端ビットは 1 なので result は (4 × 256) % 497 すなわち 30 となる。e は右にシフトされて 1（2進数）となり、b は (256 × 256) % 497 つまり 429 となる。 繰返しの4回目では、e の右端ビットは 1 なので result は (30 × 429) % 497 すなわち 445 となる。e は右にシフトされて 0 となり、b は (429 × 429) % 497 つまり 151 となる。 e が 0 になるとループは終了し、結果として 445 が得られる。これは前述のアルゴリズムの結果とも一致する。
※この「途中で剰余をとる」の解説は、「冪剰余」の解説の一部です。
「途中で剰余をとる」を含む「冪剰余」の記事については、「冪剰余」の概要を参照ください。
- 途中で剰余をとるのページへのリンク
