冪剰余

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

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

例えば、の場合、はをで割った余りであり、冪剰余はとなる。

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

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

定義整数とについて、を法とするの -冪剰余とは、剰余群における剰余類　の -冪、つまり

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

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

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

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

と定義する。

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

例として、の場合、を計算することを考える。

はであり、これをで割ると、剰余のはであることがわかる。

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

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

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

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

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

たとえば、53 mod 13 を計算するときに、（53 = 52 × 5 であるから）次のように計算できる。まず、52 mod 13 = 25 mod 13 = 12 を計算する。次に、(12 × 5) mod 13 = 60 mod 13 = 8 として、結果が得られる。

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

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

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

という行は、ちょっとした最適化であり、前の手法にも適用可能である。

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

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

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

公開鍵暗号における応用上述のように、を法としたの -冪剰余を求めるには、高々回の加算、乗算、剰余算が必要である。加算、乗算、剰余算はそれぞれ被演算数の桁数の多項式時間で計算できる。特に、上述のように乗算を行うたびに剰余演算を行えば、被演算数を常に未満に保つことができる。よって、を法としたの -冪剰余は、入力サイズの多項式時間で計算できる。

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

参考文献

Źródło i licencja