冪剰余

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

正の整数 テンプレート:Mvar（底）の整数 テンプレート:Mvar 乗（冪指数）を正の整数 テンプレート:Mvar（法）で割った余りを、「テンプレート:Mvar を法とする テンプレート:Mvar の テンプレート:Mvar-冪剰余」と呼ぶ。つまり、冪剰余を求めるとは、次の テンプレート:Mvar を計算することにほかならない。

$c:=b^{e}modm$

例えば、テンプレート:Math の場合、テンプレート:Mvar は テンプレート:Math を テンプレート:Math で割った余りであり、冪剰余は テンプレート:Math となる。

冪指数 テンプレート:Math に対する テンプレート:Mvar-冪剰余は、通常それぞれ平方剰余、立方剰余と呼ばれる。

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

定義

整数 テンプレート:Math と テンプレート:Math について、テンプレート:Mvar を法とする テンプレート:Mvar の テンプレート:Mvar-冪剰余とは、剰余群 テンプレート:Mathにおける剰余類 テンプレート:Math　の テンプレート:Mvar-冪、つまり

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

である。しばしば、剰余類の代わりに代表元 テンプレート:Math をとって、整数として扱う。そのようなとき、特に テンプレート:Math であるような テンプレート:Mvar を代表元として選ぶことが多い。

また、変数 テンプレート:Mvar に関する テンプレート:Mvar を法とする合同式

$c=x^{e}modm$

が解をもつような テンプレート:Mvar を総称して法 テンプレート:Mvar に対する テンプレート:Mvar-冪剰余 (residue of テンプレート:Mvar-th power modulo テンプレート:Mvar) と呼び、解をもたないような テンプレート:Mvar は総じて法 テンプレート:Mvar に関して テンプレート:Mvar-冪非剰余 (non-residue of テンプレート:Mvar-th power modulo テンプレート:Mvar) であるという。

冪剰余は、指数 テンプレート:Mvar が負の場合にも定義できる。その場合、テンプレート:Mvar を法として テンプレート:Mvar の逆数（モジュラ逆数）となる d によって、

$b^{e}modm:=d^{|e|}modm$

と定義する。

計算方法

素朴な手法

冪剰余を求める最も素朴な手法は、まずテンプレート:Math を計算し、その結果を テンプレート:Mvar で割って余りを求める方法である。 冪乗#効率的な演算法にあるように、冪乗の演算には、テンプレート:Math 回の乗算が必要であり、それに加えて1回の剰余演算を施すことによって冪剰余を求めることができる。

例として、テンプレート:Math の場合、テンプレート:Mvar を計算することを考える。

$c:=4^{13}mod497$

テンプレート:Math は テンプレート:Math であり、これを テンプレート:Math で割ると、剰余の テンプレート:Mvar は テンプレート:Math であることがわかる。

テンプレート:Mvar は1桁、テンプレート:Mvar は2桁の数値だが、テンプレート:Math は8桁にもなる。

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

途中で剰余をとる

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

2つの整数式 テンプレート:Mvar と テンプレート:Mvar があるとき、

$(a\times b)modm=((a\text{mod}m)\times (b\text{mod}m))modm$

である。したがって、最後に剰余演算を1回行うのではなく、前の演算結果 テンプレート:Mvar と テンプレート:Mvar のそれぞれについて テンプレート:Mvar を法とする剰余をとってから乗算をしても、計算結果は変わらない。

たとえば、5³ mod 13 を計算するときに、（5³ = 5² × 5 であるから）次のように計算できる。

• まず、5² mod 13 = 25 mod 13 = 12 を計算する。
• 次に、(12 × 5) mod 13 = 60 mod 13 = 8 として、結果が得られる。

これによって、剰余算の回数が1回から テンプレート:Math 回に増えるが、乗算および剰余算の計算コストは被演算数の桁数によるので、結果としてはこのアルゴリズムのほうが能率が良い。また一般に、テンプレート:Mvar がその計算機環境における1語の桁数の半分以下に収まる場合 テンプレート:Math の結果が必ず1語に収まるので、Bignum を一切使わない能率の良い計算が可能である。

次の例は、基本としてこの手法を利用し、さらに指数法則の テンプレート:Math を活用したコードであり、ほぼ 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;
}

このコードは、テンプレート:Harvtxtにあるものに基づいており、一つの 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）だけが変化していき、他の変数は変化しないという利点がある。このことからハードウェアによる暗号処理の実装を高速かつ安価に実装できる。

テンプレート:Math という行は、ちょっとした最適化であり、前の手法にも適用可能である。

これらのバイナリ法では、指数の2進数表現の各ビットごとに自乗の計算が必要であり、そのビットが1であるときだけ乗算も行う。

右向きバイナリ法では、乗算回数をさらに減らす bit windowing optimization や sliding window optimization がある。

また、剰余を求める計算（%）の高速化として、モンゴメリ乗算がある。

公開鍵暗号における応用

上述のように、テンプレート:Mvar を法とした テンプレート:Mvar の テンプレート:Mvar-冪剰余を求めるには、高々 テンプレート:Math 回の加算、乗算、剰余算が必要である。 加算、乗算、剰余算はそれぞれ被演算数の桁数の多項式時間で計算できる。特に、上述のように乗算を行うたびに剰余演算を行えば、被演算数を常に テンプレート:Mvar 未満に保つことができる。よって、テンプレート:Mvar を法とした テンプレート:Mvar の テンプレート:Mvar-冪剰余は、入力サイズ テンプレート:Math の多項式時間で計算できる。

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

参考文献

• テンプレート:Citation

  テンプレート:Cite book

関連項目

• 原始根
• 指数 (初等整数論)
• 平方剰余の相互法則
• 冪剰余の相互法則

外部リンク

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