有限體離散對數之計算

Abstract

1976年Diffie與Hellman兩人首度提出將離散對數問題應用在網路上的金鑰分配。目前已有許多以離散對數問題為基礎的密碼系統。然而一旦離散對數問題被有效地破解，即很容易計算，這些密碼系統就等於完全沒有安全性可言。由此可見離散對數在密碼系統應用上的重要性，也奠定了離散對數在密碼學上的重大價值。 離散對數在數論的領域中已有一段很長的歷史。但直到現在，離散對數問題還是無法有效率的計算出來。目前已有許多破解離散對數問題的隨機式演算法被提出，如Shanks演算法、Pollard演算法、Pohlig-Hellman演算法及較實用的 Index Calculus方法。其中Index Calculus方法被認為最有效率。但在不同的有限體中各有不同的解法。在這篇論文中，除了上述的演算法，另一方面也介紹在有限體 、 ，以及 中的演算法。特別針對 中的Gaussian Integer方法做一番清楚的描述，並提出一個範例以求更清楚的瞭解。

In 1976, Diffie and Hellman first proposed an algorithm that applied the discrete logarithm problem to key distribution on the network. There are numerous cryptosystems based on the discrete logarithm recently. If the discrete logarithm problem is efficiently solved, there will not be any more security for those cryptosystems. The discrete logarithm problem has a long history in the field of number theory. However, we still can not efficiently solve this problem. In this thesis, we introduced the most popular methods for it including Shanks' algorithm, Pollard's algorithm, Pohlig-Hellman algorithm and the most promising index calculus method. Especially the Gaussian integer method for , the details are presented and we proposed an example for a clear understanding.