冪剰余

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

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

c \equiv b^e \pmod m

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

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

冪剰余は指数 e が負の場合も定義できる。その場合、m を法として b逆数となる d について、

b^{e} \pmod m := d^{-e} \pmod m

と定義する。

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

定義[編集]

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

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

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

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

c \equiv x^e \pmod m

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

計算方法[編集]

直截的手法[編集]

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

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

c \equiv 4^{13} \pmod{497}

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

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

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

途中で剰余をとる[編集]

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

2つの整数 ab があるとき、

(a \cdot b) \pmod{m} \equiv ((a\ (\mbox{mod}\ m)) \cdot (b\ (\mbox{mod}\ m))) \pmod{m}

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

これによって、剰余算の回数が一回から O(log(e)) 回に増えるが、乗算及び剰余算の計算コストは被演算数の桁数によるので、結果としてはこのアルゴリズムのほうが性能が良い。またaが16bit以下の場合32bitコンピュータの扱える数値(±232 -1)以内に収まるというメリットもある。

次の例は、この手法を 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;
}

このコードは、Bruce Schneier の Applied Cryptography, 2e, ISBN 0-471-11709-9 の244ページにあるものに基づいており、1つの 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 になる。
  • ループ繰り返しの二回目では、e の右端ビットは 0 なので result4 のままとなる。e は右シフトされて 11(2進数)となり、b は (16 * 16) % 497 つまり 256 となる。
  • ループ繰り返しの三回目では、e の右端ビットは 1 なので result は (4 * 256) % 497 すなわち 30 となる。e は右シフトされて 1(2進数)となり、b は (256 * 256) % 497 つまり 429 となる。
  • ループ繰り返しの四回目では、e の右端ビットは 1 なので result は (30 * 429) % 497 すなわち 445 となる。e は右シフトされて 0 となり、b は (429 * 429) % 497 つまり 151 となる。

e がゼロになるとループは終了し、結果として 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 = 1L
   if modulo == None:
      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 を法とした be 冪剰余を求めるには、高々 O(log(e)) 回の加算、乗算、剰余算が必要である。 加算、乗算、剰余算はそれぞれ被演算数の桁数の多項式時間で計算できる。特に、上で見たように乗算を行うたびに剰余演算を行えば、被演算数を常に m 以下に保つことができる。よって、m を法とした be 冪剰余は、入力サイズ log(b) + log(e) + log(m) の多項式時間で計算できる。

一方、m, b, c から cbe mod m なる e を求める問題は離散対数問題といわれ、効率的な、つまり入力サイズの多項式時間のアルゴリズムは発見されていない。公開鍵暗号のうちある種のものは、この一方向性を利用して設計されている。

関連項目[編集]

外部リンク[編集]