離散對數

此條目沒有列出任何參考或來源。 (2016年12月25日) 維基百科所有的內容都應該可供查證。請協助補充可靠來源以改善這篇條目。無法查證的內容可能會因為異議提出而被移除。

未解決的計算機科學問題：是否存在離散對數問題的多項式時間經典算法？

在整數中，離散對數（英語：Discrete logarithm）是一種基於同餘運算和原根的一種對數運算。而在實數中對數的定義 ${\displaystyle \log _{b}a}$ 是指對於給定的 ${\displaystyle a}$ 和 ${\displaystyle b}$，有一個數 ${\displaystyle x}$，使得${\displaystyle b^{x}=a}$。相同地在任何群 G中可為所有整數 ${\displaystyle k}$ 定義一個冪數為 ${\displaystyle b^{k}}$，而離散對數 ${\displaystyle \log _{b}a}$ 是指使得 ${\displaystyle b^{k}=a}$ 的整數 ${\displaystyle k}$ 。 離散對數在一些特殊情況下可以快速計算。然而，通常沒有具非常效率的方法來計算它們。公鑰密碼學中幾個重要算法的基礎，是假設尋找離散對數的問題解，在仔細���擇過的群中，並不存在有效率的求解算法。

當模${\displaystyle m}$有原根時，設${\displaystyle l}$為模${\displaystyle m}$的一個原根，則當${\displaystyle x\equiv l^{k}{\pmod {m}}}$時：

${\displaystyle Ind_{l}x\equiv k{\pmod {m}}}$，此處的${\displaystyle Ind_{l}x}$為${\displaystyle x}$以整數${\displaystyle l}$為底，模${\displaystyle m}$時的離散對數值

離散對數和一般的對數有着相類似的性質：

• ${\displaystyle Ind_{l}xy\equiv Ind_{l}x+Ind_{l}y{\pmod {\phi (m)}}}$
• ${\displaystyle Ind_{l}x^{y}\equiv yInd_{l}x{\pmod {\phi (m)}}}$

• 原根
• 對數

這是一篇關於數學的小作品。您可以透過編輯或修訂擴充其內容。 閱 論 編