冪乗剰余

冪剰余（べきじょうよ、英: 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$ -冪剰余は、通常それぞれ平方剰余、立方剰余と呼ばれる。

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

定義

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

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

b^{e}{\bmod {m}}:=d^{|e|}{\bmod {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\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) \times (b mod m)$ の結果が必ず1語に収まるので、Bignum を一切使わない能率の良い計算が可能である。

次の例は、基本としてこの手法を利用し、さらに指数法則の $b 2 x = (b 2) 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 - ミネソタ大学ツインシティー校数学科
親子剰余乗算器を用いた左向きアレイ法の実装方式^{[リンク切れ]} 櫻井隆雄（東京大学）

定義