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