離散対数と離散対数問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/14 16:12 UTC 版)
「楕円曲線暗号」の記事における「離散対数と離散対数問題」の解説
ある楕円曲線上の点 G {\displaystyle G} から、 2 G , 3 G , 4 G , … {\displaystyle 2G,3G,4G,\ldots } を計算していくと、次々と異なる（楕円曲線上の）点が得られ、いずれは無限遠点 n G = O {\displaystyle nG=O} が得られる。（その後は、 ( n + 1 ) G = G , ( n + 2 ) G = 2 G , ( n + 3 ) G = 3 G , … {\displaystyle (n+1)G=G,(n+2)G=2G,(n+3)G=3G,\ldots } と繰り返される。）このように G {\displaystyle G} からスカラー倍算によって得られる点の集合を ⟨ G ⟩ = { G , 2 G , 3 G , … , O } {\displaystyle \langle G\rangle =\{G,2G,3G,\ldots ,O\}} と書くことにすると、 ⟨ G ⟩ {\displaystyle \langle G\rangle } は巡回群となる。巡回群の位数は n {\displaystyle n} であり、 ⟨ G ⟩ {\displaystyle \langle G\rangle } を生成する元 G {\displaystyle G} はベースポイントとも呼ばれる。 巡回群 ⟨ G ⟩ {\displaystyle \langle G\rangle } の任意の要素（楕円曲線上の点） X {\displaystyle X} に対し、 X = a G {\displaystyle X=aG} を満たす a {\displaystyle a} が { 0 , 1 , … , n − 1 } {\displaystyle \{0,1,\ldots ,n-1\}} の中に常にただ一つ存在する。このような a {\displaystyle a} を X {\displaystyle X} の離散対数と呼ぶ。また、 ⟨ G ⟩ {\displaystyle \langle G\rangle } から無作為に選らばれた X {\displaystyle X} を与えられ、その離散対数を求めよという問題を、楕円曲線上の離散対数問題 と呼ぶ。 また、 ⟨ G ⟩ {\displaystyle \langle G\rangle } から無作為に選ばれた二つの点 X = a G , Y = b G {\displaystyle X=aG,Y=bG} を与えられ、 a b G {\displaystyle abG} を求めよという問題を、楕円曲線上のディフィー・ヘルマン問題 と呼ぶ。 最もポピュラーな離散対数問題は、 p , g {\displaystyle p,g} と y = g x mod p {\displaystyle y=g^{x}{\bmod {p}}} から x {\displaystyle x} を求めよ、という問題であり、 g ∈ Z p ∗ ( = Z / p Z ) × {\displaystyle g\in Z_{p}^{*}(=Z/pZ)^{\times }} から生成される乗法群の上で定義されている。これに対して、楕円曲線は加法群であるため、 Y = a P {\displaystyle Y=aP} を満たす a {\displaystyle a} を離散対数と呼ぶ。 巡回群の位数 n {\displaystyle n} が小さければ、離散対数問題やディフィー・ヘルマン問題が容易に解けてしまうため、位数が巨大な素数になるようなベースポイント（と楕円曲線）が使用される。
※この「離散対数と離散対数問題」の解説は、「楕円曲線暗号」の解説の一部です。
「離散対数と離散対数問題」を含む「楕円曲線暗号」の記事については、「楕円曲線暗号」の概要を参照ください。
- 離散対数と離散対数問題のページへのリンク
