打开主菜单
未解決的计算机科学問題是否存在离散对数问题的多项式时间经典算法? Question mark2.svg

整數中,離散對數英语:Discrete logarithm)是一種基於同餘運算和原根的一種對數運算。而在實數中對數的定義 logb a 是指對於給定的 ab,有一個數 x,使得bx = a。相同地在任何群 G中可為所有整數 k定義一個冪數為 bk,而離散對數 logb a是指使得 bk = a的整數 k。 離散對數在一些特殊情況下可以快速計算。然而,通常沒有具非常效率的方法來計算它們。公鑰密碼學中幾個重要算法的基礎,是假設尋找離散對數的問題解,在仔細選擇過的群中,並不存在有效率的求解算法。

定義编辑

當模 有原根時,設 為模 的一個原根,則當 時:

 ,此處的  以整數 為底,模 時的離散對數值

性質编辑

離散對數和一般的對數有著相類似的性質:

  •  
  •  

參見编辑