離散對數的起源和發展

在壹般的參考文獻中，認為公鑰密碼體制是W.Diffie和E.Hellman發明的，但鮮為人知的是，Merckle甚至在他們之前的1975年就提出了類似的思想，雖然他的文章發表在1978年。所以公鑰密碼體制的創始人應該是他們三個。當然他們三個只是提出了壹個關於公鑰密碼體制和數字簽名的想法，並沒有真正實現。然而，他們確實實現了壹種新技術，該技術體現了公鑰密碼系統的思想，基於離散對數問題，並在不安全的信道上形成和交換密鑰。

所謂離散對數就是給定壹個正整數x，y，n，求壹個正整數k(如果存在)使得y≡xk(mod n)。目前，人們還沒有找到壹種計算離散對數的快速算法(所謂快速算法是指計算復雜度在多項式範圍內的算法，即O(logn)k，其中k為常數)。雖然有快速計算離散對數的量子算法，但其計算復雜度為O(logn)2+？看，但是現在還沒有量子計算機(實用的量子計算機可能根本造不出來)。