公開鍵暗号方式は非常に大きな素数を必要とする方式が多く,パソコンの性能の発達とともに必要とされる素数の桁数も増しており,離散対数問題もそのうちの一つに使われている. 1976 年に, Deffee と Hellman によって公開鍵暗号が発見されたとき、有限体上の指数計算により暗号鍵を配送する公開鍵配送方式( Deffee ‐ Hellman 鍵配送方式)が提案された.離散対数問題は古くから知られた難問であったが,この提案以来,離散対数問題という問題が一躍注目を集めるようになり,離散対数問題に基づく公開鍵暗号や認証方式は数多く提案されている. さて,離散対数とは,素数 p を定めたとき、Z *_ ( p ) における原始元 g に対して、 y ^ ( x ) = mod p ならば、x = log _ ( y ) y と記して、yのgに対する離散対数という.つまり、離散対数問題とは,( p ,g ,y )が与えられたとき,x = log _ ( g ) y を求める問題である. 離散対数を求めるアルゴリズムは,次の 2 種類に大別することができる.
1 .Z *_ ( p ) 上の離散対数の計算時間が,Z *_ ( p ) の位数 p – 1 の最大素因数のサイズN に依存するアルゴリズムで,その計算時間は O ( 2 ^( N ) N )となる.つまり,N に関して指数時間オーダの実行時間となる. 2 .指数計算法と呼ばれる手法で,Z *_ ( p ) 上の離散対数の計算時間が,p のサイズの準指数時間オーダの実行時間 L _ ( p ) [ a,c ] となるものである.