翻訳と辞書
Words near each other
・ 離散付値
・ 離散付値環
・ 離散位相
・ 離散位相空間
・ 離散信号
・ 離散凸解析
・ 離散化誤差
・ 離散変量
・ 離散家族
・ 離散対数
離散対数問題
・ 離散数学
・ 離散数理
・ 離散時間フーリエ変換
・ 離散時間信号
・ 離散測度
・ 離散的
・ 離散的スケール不変性
・ 離散確率分布
・ 離散確率変数


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

離散対数問題 : ミニ英和和英辞書
離散対数問題[りさんたいすう]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

離散 : [りさん]
  1. (n,vs) dispersal 2. scattering 
: [つい]
 【名詞】 1. pair 2. couple 3. set 
対数 : [たいすう]
 (n) logarithm
: [すう, かず]
  1. (n,n-suf) number 2. figure 
: [もん]
 【名詞】 1. problem 2. question 
問題 : [もんだい]
 【名詞】 1. problem 2. question 
: [だい]
  1. (n,vs) title 2. subject 3. theme 4. topic 

離散対数問題 ( リダイレクト:離散対数 ) : ウィキペディア日本語版
離散対数[りさんたいすう]
代数学における離散対数(りさんたいすう、)とは、通常の対数群論的な類似物である。
離散対数を計算する問題は整数の因数分解(:en:integer factorization)と以下の点が共通している:
*両方とも難しい(量子コンピュータ以外では効率的に解くアルゴリズムが得られていない)
*片方に対するアルゴリズムはしばしばもう片方にも利用できる
*問題の困難性が暗号系の構築に利用されている
== 例 ==

離散対数を理解するのに、最も簡単なのは素数 ''p'' をとする整数合同類からなる集合 に乗法を考えた既約剰余類群 (Z/''p''Z)× であろう。
この群の元の ''k''-乗を知りたければ、普通の整数と看做して ''k''-乗を求め、それから ''p'' で割った剰余(余り)を求めればよい(これを離散冪乗とよぶこともある)。
例えば (Z/17Z)× を考え、この中で 34 を計算するには、
まず 34 = 81 としてから、81 を 17 で割って余りの 13 を得るので、既約剰余類群 (Z/17Z)× の中で 34 ≡ 13 (mod 17) が成り立つ。
離散対数はちょうどこの逆の操作である。たとえば、''k'' についての方程式(合同式) 3''k'' ≡ 13 (mod 17) を考えると、''k'' = 4 がこの方程式の解になっていることはすでに述べたとおりであるが、これは唯一の解ではない。実際、316 ≡ 1 (mod 17) であるから、''n'' を整数として 34+16 ''n'' ≡ 13 × 1''n'' ≡ 13 (mod 17) であり、この方程式は 4 + 16 ''n'' の形の解を無数にもつ。さらに、3''m'' ≡ 1 (mod 17) を満たす最小の正整数 ''m'' は 16 である(すなわち、16 は (Z/17Z)× における 3 の位数である)から、方程式の解はこの形のものに限られる。以上のことから、この方程式の解は ''k'' ≡ 4 (mod 16) で表せる。
もう少し一般に、''n'' を整数として既約剰余類群 ''G'' = (Z/''n''Z)× が巡回群であると仮定する(そのような ''n'' は 2, 4 および素数冪 ''q'' と 2 ''q'' の形に書けるものに限られる)と、群 ''G'' の位数は φ(''n'') だから位数 φ(''n'') となる元(''n'' を法とする原始根 と呼ばれる)''b'' が存在して、''G'' の各元 ''a'' に対して ''b''''k'' ≡ ''a'' となるような ''k'' は φ(''n'') を法として一意に定まる(このときの離散対数はしばしば指数 と呼ばれる)。先の例では φ(17) = 16 で ''b'' = 3 が (Z/17Z)× を生成する位数 16 の元であり、''a'' = 13 に対して ''k'' mod 16 が一意に定まっていることが確認できる。'Z)× であろう。
この群の元の ''k''-乗を知りたければ、普通の整数と看做して ''k''-乗を求め、それから ''p'' で割った剰余(余り)を求めればよい(これを
離散冪乗とよぶこともある)。
例えば (
Z/17Z)× を考え、この中で 34 を計算するには、
まず 34 = 81 としてから、81 を 17 で割って余りの 13 を得るので、既約剰余類群 (
Z/17Z)× の中で 34 ≡ 13 (mod 17) が成り立つ。
離散対数はちょうどこの逆の操作である。たとえば、''k'' についての方程式(合同式) 3''k'' ≡ 13 (mod 17) を考えると、''k'' = 4 がこの方程式の解になっていることはすでに述べたとおりであるが、これは唯一の解ではない。実際、316 ≡ 1 (mod 17) であるから、''n'' を整数として 34+16 ''n'' ≡ 13 × 1''n'' ≡ 13 (mod 17) であり、この方程式は 4 + 16 ''n'' の形の解を無数にもつ。さらに、3''m'' ≡ 1 (mod 17) を満たす最小の正整数 ''m'' は 16 である(すなわち、16 は (Z/17Z)× における 3 の位数である)から、方程式の解はこの形のものに限られる。以上のことから、この方程式の解は ''k'' ≡ 4 (mod 16) で表せる。
もう少し一般に、''n'' を整数として既約剰余類群 ''G'' = (
Z/''n''Z)× が巡回群であると仮定する(そのような ''n'' は 2, 4 および素数冪 ''q'' と 2 ''q'' の形に書けるものに限られる)と、群 ''G'' の位数は φ(''n'') だから位数 φ(''n'') となる元(''n'' を法とする原始根 と呼ばれる)''b'' が存在して、''G'' の各元 ''a'' に対して ''b''''k'' ≡ ''a'' となるような ''k'' は φ(''n'') を法として一意に定まる(このときの離散対数はしばしば指数 と呼ばれる)。先の例では φ(17) = 16 で ''b'' = 3 が (Z/17Z)× を生成する位数 16 の元であり、''a'' = 13 に対して ''k'' mod 16 が一意に定まっていることが確認できる。
Z)× を生成する位数 16 の元であり、''a'' = 13 に対して ''k'' mod 16 が一意に定まっていることが確認できる。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「離散対数」の詳細全文を読む

英語版ウィキペディアに対照対訳語「 Discrete logarithm 」があります。




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.