原根

原根，是一个数学符号。设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。

一个数m如果有原根，则其原根个数为phi(phi(m))。特别地，对素数有phi(p)=p-1。

假设g是奇素数p的一个原根，则\(g^1,g^2,...,g^{p-1}\)在模p意义下两两不同，且结果恰好为1~p-1，由此可以定义“离散对数”，与连续数学中的对数有异曲同工之妙。

离散对数又叫做“指标”，有指标法则：I(ab)≡I(a)+I(b) (mod p-1)；I(a^k)≡k*I(a) (mod p-1)，由此可以把乘法转化为加法。