|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 冪 ： [べき] (n) (gen) (math) a power ・ 剰 ： [じょう] 【名詞】 1. besides 2. moreover 3. in addition ・ 剰余 ： [じょうよ] 【名詞】 1. surplus 2. balance ・ 余 ： [よ] 1. (n,suf) over 2. more than
冪剰余（べきじょうよ、英: Modular exponentiation）とは、冪乗の剰余のことである。数論的に重要な概念であるとともに、計算機科学、特に暗号理論の分野で重要な応用を持つ。冪乗剰余とも呼ばれる。 正の整数 ''b'' （底）の ''e'' 乗（冪指数）を正の整数 ''m'' （法）で割った余りを、「''m'' を法とした ''b'' の ''e'' 冪剰余」と呼ぶ。つまり、冪剰余を求めるとは、次の ''c'' を計算することに他ならない。 : 例えば、''b'' = 5, ''e'' = 3、''m'' = 13 の場合、''c'' は を 13 で割った余りであるので、冪剰余は 8 となる。 冪指数 ''e'' = 2, 3 に対する ''e''-冪剰余は通常それぞれ、平方剰余、立方剰余と呼ばれる。 冪剰余は指数 ''e'' が負の場合も定義できる。その場合、''m'' を法として ''b'' の逆数となる ''d'' について、 : と定義する。 冪剰余 ''c'' を求める計算は、たとえ巨大な数であっても難しくはない。一方、''b''、''c''、''m'' を与えられたとき、指数 ''e'' を求めることは難しい。このような一方向性関数的性質から、冪剰余は暗号での利用の研究が進んでいる。 == 定義 == 整数 ''b'', ''e'' と ''m'' (''m'' > 0)について、''m'' を法とした ''b'' の ''e'' 冪剰余とは、剰余群 Z/''m''Zにおける剰余類 の ''e''-冪、つまり : である。しばしば、剰余類のかわりに代表元 ''c'' ∈ ''e'' をとって、整数として扱う。そのような時、特に 0 ≤ ''c'' < ''m'' であるような ''c'' を代表元として選ぶことが多い。 また、変数 ''x'' に関する、''m'' を法とする合同式 : が解を持つような ''c'' を総称して法 ''m'' に対する ''e''-冪剰余 (residue of e-th power modulo m) とよび、解を持たないような ''c'' は総じて法 ''m'' に関して ''e''-冪非剰余 (non-residue of e-th power modulo m) であるという。 : である。しばしば、剰余類のかわりに代表元 ''c'' ∈ ''e'' をとって、整数として扱う。そのような時、特に 0 ≤ ''c'' < ''m'' であるような ''c'' を代表元として選ぶことが多い。 また、変数 ''x'' に関する、''m'' を法とする合同式 : が解を持つような ''c'' を総称して法 ''m'' に対する ''e''-冪剰余 (residue of e-th power modulo m) とよび、解を持たないような ''c'' は総じて法 ''m'' に関して ''e''-冪非剰余 (non-residue of e-th power modulo m) であるという。 冪非剰余 (non-residue of e-th power modulo m) であるという。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「冪剰余」の詳細全文を読む スポンサード リンク
|