一方向性と離散対数問題
２つの素数からその積を作ることは簡単だが、その積だけを示されて 元になっている２つの素数を求めるのは、原理的に不可能ではないが、 実際問題きわめて手間がかかる。このような関係にある２つの数学的処 理を、一方向性がある、といいます。
手計算レベルの軽い一方向性ということでいえば、例えば1.64950873 の二乗を有効数字９桁で求めるのは、多少の面倒さに目をつぶって実行 すれば、2.72087905という答を得るのはそう大変ではありません。しか し逆に2.72087905の平方根を有効数字９桁で求めるのは、たとえ平方根 の計算方法を知っていても、単なる掛け算よりは大変です。
より一般的にいえば、例えばｆ(ｘ)＝ｘ**3 + ｘ**2 + ｘという関数 （**3は３乗、**2は２乗を表わす）は、ｘがマイナス無限大の時にマイ ナス無限大の値を取り、ｘがプラス無限大の時にプラス無限大の値を取 ります。しかもｘの値により単調に増加する関数です。従ってある実数 が与えられると、ｆ(ｘ)がその値になるような実数ｘは一意に決まるの ですが、実際問題ｆ(ｘ)の値からｘを求めるのは、三次方程式を解くこ とに相当しますから、ｘの値からｆ(ｘ)を求めるよりはるかに大変です。
これらは実数に対する一方向性の例ですが、整数に対する一方向性が 公開鍵暗号の基礎となります。
素因数分解以外の例としては、離散対数問題というのがあります。こ れは、与えられたある素数ｐを法（図６参照）として考えた時、与えら れたある整数ｑとａに対して、ｂ＝ｑ**ａとなるｂを求めるのは簡単だ が、与えられたある整数ｑとｂに対して、ｂ＝ｑ**ａとなるａを求める のは難しい、ということです（実際にはｑは何でも良いという訳ではな い）。法を考えない問題では、ｂ＝ｑ**ａというａはｑを底とするｂの 対数ですので、こういった名前がつけられました。
例を示しましょう。ｐ＝17とします。この時、例えばｑ＝４とすると、 ｑ**４もｑ**８もともに１（ｐを法として）になってしまうので失敗で す。ｑ＝５ならそういったことはないので、ここではｑ＝５とします。 この時、例えばａ＝12と与えられれば、ｑ**ａが４となることは、12回 の掛け算を行えばすぐにわかります（実際には12回の掛け算というより、 例えば３乗したものを４乗すればよい）。しかし逆に、ｑ**ａが４だよ と教えられても、そこからａ＝12というのは、ａが１なら、ａが２なら、 ａが３なら、...とすべてチェックしない限り、わからないのです。
sponsored link
このページ
のTOPへ
