查看“︁离散对数”︁的源代码

{{unreferenced|time=2016-12-25T00:14:16+00:00}}

{{unsolved|计算机科学|是否存在离散对数问题的多项式时间经典算法？}}

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

== 定義 ==
當模<math>m</math>有原根時，設<math>l</math>為模<math>m</math>的一個原根，則當<math>x \equiv l^k \pmod{m}</math>時：

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

== 性質 ==
離散對數和一般的對數有著相類似的性質：
*<math>Ind_{l} xy \equiv Ind_{l} x + Ind_{l} y \pmod{\phi (m)}</math>
*<math>Ind_{l} x^y \equiv y Ind_{l} x \pmod{\phi (m)}</math>

== 參見 ==
*[[原根]]
*[[對數]]

{{mathstub}}
[[Category:同余]]
[[Category:二元運算|L]]
[[Category:群论|L]]
[[Category:对数]]
[[Category:计算机科学中未解决的问题]]
[[Category:有限域]]