离散对数

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

定義

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

$In{d}_{l}x\equiv k(\mathrm{mod}m)$，此處的$In{d}_{l}x$為$x$以整數$l$為底，模$m$時的離散對數值

性質

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

• $In{d}_{l}xy\equiv In{d}_{l}x+In{d}_{l}y(\mathrm{mod}\varphi (m))$
• $In{d}_l{x}^y\equiv yIn{d}_{l}x(\mathrm{mod}\varphi (m))$

參見

• 原根
• 對數