冪乗剰余

この記事には参考文献や外部リンクの一覧が含まれていますが、脚注による参照が不十分であるため、情報源が依然不明確です。 適切な位置に脚注を追加して、記事の信頼性向上にご協力ください。（2022年12月）

冪剰余（べきじょうよ、英: modular exponentiation）とは、冪乗の剰余のことである。数論的に重要な概念であるとともに、計算機科学、特に暗号理論の分野での応用が重要である。冪乗剰余とも呼ばれる。

正の整数 b（底）の整数 e 乗（冪指数）を正の整数 m（法）で割った余りを、「m を法とする b の e-冪剰余」と呼ぶ。つまり、冪剰余を求めるとは、次の c を計算することにほかならない。

${\displaystyle c:=b^{e}{\bmod {m}}}$

例えば、b = 5、e = 3、m = 13 の場合、c は 5³ を 13 で割った余りであり、冪剰余は 8 となる。

冪指数 e = 2, 3 に対する e-冪剰余は、通常それぞれ平方剰余、立方剰余と呼ばれる。

冪剰余 c を求める計算は、たとえ巨大な数であっても難しくはない。一方、b, c, m が与えられたとき指数 e を求めることを考えると、これは Z/mZ の乗法群における離散対数問題と同値であり、一般に難しい。このような一方向性関数的性質から、冪剰余の暗号での利用についての研究が進んでいる。

整数 b, e と m (m > 0) について、m を法とする b の e-冪剰余とは、剰余群 Z/mZにおける剰余類 [b]　の e-冪、つまり

${\displaystyle [b]^{e}\in \mathbb {Z} /m\mathbb {Z} }$

である。しばしば、剰余類の代わりに代表元 c ∈ [b]^e をとって、整数として扱う。そのようなとき、特に 0 ≤ c < m であるような c を代表元として選ぶことが多い。

また、変数 x に関する m を法とする合同式

${\displaystyle c=x^{e}{\bmod {m}}}$

が解をもつような c を総称して法 m に対する e-冪剰余 (residue of e-th power modulo m) と呼び、解をもたないような c は総じて法 m に関して e-冪非剰余 (non-residue of e-th power modulo m) であるという。

冪剰余は、指数 e が負の場合にも定義できる。その場合、m を法として b の逆数（モジュラ逆数）となる d によって、

${\displaystyle b^{e}{\bmod {m}}:=d^{|e|}{\bmod {m}}}$

と定義する。

冪剰余を求める最も素朴な手法は、まずb^e を計算し、その結果を m で割って余りを求める方法である。 冪乗#効率的な演算法にあるように、冪乗の演算には、O(log(e)) 回の乗算が必要であり、それに加えて1回の剰余演算を施すことによって冪剰余を求めることができる。

例として、b = 4, e = 13, m = 497 の場合、c を計算することを考える。

${\displaystyle c:=4^{13}{\bmod {497}}}$

4¹³ は 67,108,864 であり、これを 497 で割ると、剰余の c は 445 であることがわかる。

b は1桁、e は2桁の数値だが、b^e は8桁にもなる。

強い暗号では、b は最低でも256桁の2進数（10進数では77桁）である。典型的な例として b = 5 × 10⁷⁶ と e = 17 の場合を考えてみる。この場合、b は77桁であり、e は2桁だが、b^e は（10進で）1304桁にもなる。コンピュータにそのような計算をさせることはもちろん可能だが、性能は期待できない。b や e の桁数が増えるほど、b^e は扱いにくくなる。

次の計算方法は、手順を増やすことになるが、結果としてはこのアルゴリズムのほうが能率が良い。

2つの整数式 a と b があるとき、

${\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)) 回に増えるが、乗算および剰余算の計算コストは被演算数の桁数によるので、結果としてはこのアルゴリズムのほうが能率が良い。また一般に、m がその計算機環境における1語の桁数の半分以下に収まる場合 (a mod m) × (b mod m) の結果が必ず1語に収まるので、Bignum を一切使わない能率の良い計算が可能である。

次の例は、基本としてこの手法を利用し、さらに指数法則の b^2x = (b²)^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 が得られる。これは前述のアルゴリズムの結果とも一致する。

Pythonで右向きバイナリ法（指数の左端ビットから順に見ていく方法）を使った例である。

import math   def bits(integer):  # Gets number of bits in integer     result = 0     while integer:         integer >>= 1         result += 1     return result   def 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^e mod m なる e を求める問題は離散対数問題といわれ、効率的な、つまり入力サイズの多項式時間のアルゴリズムは発見されていない。公開鍵暗号のうちある種のものは、この一方向性を利用して設計されている。

• Schneier, Bruce (1995-10-18), Applied Cryptography: Protocols, Algorithms and Source Code in C (2nd ed.), Wiley, ISBN 0-471-11709-9 

  シュナイアー, ブルース 著、安達眞弓 ほか 訳『暗号技術大全』山形浩生 監訳、ソフトバンクパブリッシング、2003年6月。ISBN 4-7973-1911-9。 

• Fast Modular Exponentiation Java Applet - ミネソタ大学ツインシティー校数学科
• 親子剰余乗算器を用いた左向きアレイ法の実装方式^{[リンク切れ]} 櫻井隆雄（東京大学）