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

出典:wikipedia