离散对数

離散對數是在整數中，一種基於同餘運算和原根的一種對數運算。

定義

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

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

性質

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

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

參見

• 原根
• 對數