離散對數
外觀
此條目沒有列出任何參考或來源。 (2016年12月25日) |
未解決的計算機科學問題:是否存在離散對數問題的多項式時間經典算法?
在整數中,離散對數(英語:Discrete logarithm)是一種基於同餘運算和原根的一種對數運算。而在實數中對數的定義 是指對於給定的 和 ,有一個數 ,使得。相同地在任何群 G中可為所有整數 定義一個冪數為 ,而離散對數 是指使得 的整數 。 離散對數在一些特殊情況下可以快速計算。然而,通常沒有具非常效率的方法來計算它們。公鑰密碼學中幾個重要算法的基礎,是假設尋找離散對數的問題解,在仔細選擇過的群中,並不存在有效率的求解算法。
定義
[編輯]當模有原根時,設為模的一個原根,則當時:
,此處的為以整數為底,模時的離散對數值
性質
[編輯]離散對數和一般的對數有着相類似的性質:
參見
[編輯]這是一篇關於數學的小作品。您可以透過編輯或修訂擴充其內容。 |