冪剰余

冪剰余（べきじょうよ、英: modular exponentiation）とは、冪乗の剰余のことである。数論的に重要な概念であるとともに、計算機科学、特に暗号理論の分野での応用が重要である。冪乗剰余とも呼ばれる。 正の整数 b（底）の整数 e 乗（冪指数）を正の整数 m（法）で割った余りを、「m を法とする b の e-冪剰余」と呼ぶ。つまり、冪剰余を求めるとは、次の c を計算することにほかならない。 例えば、b = 5、e = 3、m = 13 の場合、c は 53 を 13 で割った余りであり、冪剰余は 8 となる。 冪指数 e = 2, 3 に対する e-冪剰余は、通常それぞれ平方剰余、立方剰余と呼ばれる。 冪剰余 c を求める計算は、たとえ巨大な数であっても難しくはない。一方、b, c, m が与えられたとき指数 e を求めることを考えると、これは Z/mZ の乗法群における離散対数問題と同値であり、一般に難しい。このような一方向性関数的性質から、冪剰余の暗号での利用についての研究が進んでいる。