冪剰余

冪剰余（べきじょうよ、英: Modular exponentiation）とは、冪乗の剰余のことである。数論的に重要な概念であるとともに、計算機科学、特に暗号理論の分野で重要な応用を持つ。冪乗剰余とも呼ばれる。正の整数 b （底）の e 乗（冪指数）を正の整数 m （法）で割った余りを、「m を法とした b の e 冪剰余」と呼ぶ。つまり、冪剰余を求めるとは、次の c を計算することに他ならない。: <math>c \\equiv b^e \\pmod m</math>例えば、b = 5, e = 3、m = 13 の場合、c は <math>5^3</math> を 13 で割った余りであるので、冪剰余は 8 となる。冪指数 e = 2, 3 に対する e-冪剰余は通常それぞれ、平方剰余、立方剰余と呼ばれる。冪剰余は指数 e が負の場合も定義できる。その場合、m を法として b の逆数となる d について、: <math>b^{e} \\pmod m := d^ \\pmod m</math>と定義する。冪剰余 c を求める計算は、たとえ巨大な数であっても難しくはない。一方、b、c、m を与えられたとき、指数 e を求めることは難しい。このような一方向性関数的性質から、冪剰余は暗号での利用の研究が進んでいる。