「冪乗剰余」の版間の差分

削除された内容追加された内容

インライン

2020年7月5日 (日) 22:53時点における版

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

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

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

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

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

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

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

と定義する。

冪剰余 $c$ を求める計算は、たとえ巨大な数であっても難しくはない。一方、 $b, c, m$ が与えられたとき、指数 $e$ を求めることは難しい。このような一方向性関数的性質から、冪剰余の暗号での利用についての研究が進んでいる。

定義

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

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

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

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

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) であるという。

計算方法

直截的手法

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

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

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

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

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

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

途中で剰余をとる

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

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

(a\cdot b){\bmod {m}}=((a\ {\mbox{mod}}\ m)\cdot (b\ {\mbox{mod}}\ m)){\bmod {m}}

である。よって、最後に剰余演算を1回行うのではなく、乗算を行うたびに $m$ を法とした剰余をとっても計算結果は変わらない。

これによって、剰余算の回数が1回から $O(log(e))$ 回に増えるが、乗算および剰余算の計算コストは被演算数の桁数によるので、結果としてはこのアルゴリズムのほうが能率が良い。また一般に、 $m$ がその計算機環境における1語の半分以下に収まる大きさの値の場合 $(a mod m) \times (b mod m)$ の結果が必ず1語に収まるので、Bignum を一切使わない能率の良い計算が可能である。

次の例は、基本としてこの手法を利用し、さらに指数法則の $b 2x = (b 2) x$ を活用したコードであり、ほぼ C# または C++ のコードとなっている。クラス Bignum は任意の巨大な整数を表現できるものとする。引数 b は底、e は指数、m は法である。

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 \times 4) % 497$ つまり4 となる。e は右にシフトされて 110（2進数）となり、b は $(4 \times 4) % 497$ すなわち 16 になる。
繰返しの2回目では、e の右端ビットは 0 なので result は 4 のままとなる。e は右にシフトされて 11（2進数）となり、b は $(16 \times 16) % 497$ つまり 256 となる。
繰返しの3回目では、e の右端ビットは 1 なので result は $(4 \times 256) % 497$ すなわち 30 となる。e は右にシフトされて 1（2進数）となり、b は $(256 \times 256) % 497$ つまり 429 となる。
繰返しの4回目では、e の右端ビットは 1 なので result は $(30 \times 429) % 497$ すなわち 445 となる。e は右にシフトされて 0 となり、b は $(429 \times 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 - ミネソタ大学ツインシティー校数学科
親子剰余乗算器を用いた左向きアレイ法の実装方式櫻井隆雄（東京大学）

@@ 47行目: / 47行目: @@
 次の例は、基本としてこの手法を利用し、さらに指数法則の {{math|b<sup>2x</sup> {{=}} (b<sup>2</sup>)<sup>x</sup>}} を活用したコードであり、ほぼ [[C Sharp|C#]] または [[C++]] のコードとなっている。クラス Bignum は任意の巨大な整数を表現できるものとする。引数 b は底、e は指数、m は法である。
-<source lang="cpp">
+<syntaxhighlight lang="cpp">
 Bignum modpow(Bignum b, Bignum e, Bignum m) {
@@ 60行目: / 60行目: @@
     return result;
 }
+</syntaxhighlight>
-</source>
 このコードは、{{Harvtxt|Schneier|1995|p=244}}にあるものに基づいており、一つの while ループで冪剰余の計算に必要な全ての作業を行っている。
@@ 75行目: / 75行目: @@
 [[Python]]で右向き[[冪乗#効率的な演算法|バイナリ法]]（指数の左端ビットから順に見ていく方法）を使った例である。
-<source lang="python">
+<syntaxhighlight lang="python">
 import math
@@ 102行目: / 102行目: @@
             iteration -= 1
    return result
+</syntaxhighlight>
-</source>
 この方法では、初期化後は変数 result（とループ変数の iteration）だけが変化していき、他の変数は変化しないという利点がある。このことからハードウェアによる暗号処理の実装を高速かつ安価に実装できる。