离散对数

如果 是一个与 互质的任意整数 且 是 原根 , 那么在数字 0, 1, 2, ..., 中存在, 其中 是 欧拉函数, 恰好一个 数字 使得

数字 随后被称为 以 为底模 的离散对数，并记作

术语“离散对数”最常用于密码学，尽管术语“广义乘法阶”有时也被使用（Schneier 1996，第 501 页）。在数论中，通常使用术语“指标”代替（Gauss 1801；Nagell 1951，第 112 页）。

例如，数字 7 是 的一个正 原根（事实上，41 的原根集合由 6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35 给出），并且由于 , 数字 15 以 7 为底（模 41）的乘法阶为 3（Nagell 1951，第 112 页）。广义乘法阶在 Wolfram 语言中实现为MultiplicativeOrder[g, n, a1]，或更一般地为MultiplicativeOrder[g, n, a1, a2, ...]。

数学天才查理在电视剧犯罪剧集 NUMB3RS 第二季的剧集“In Plain Sight”中提到了离散对数。