离散对数

维基百科,自由的百科全书
跳转至: 导航搜索

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

定義[编辑]

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

Ind_{l} x \equiv k \pmod{\phi (m)},此處的Ind_{l} xx以整數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)}

參見[编辑]