原根（Primitive Root）是与整数阶有关的一个数论概念。其定义为：设m\u003e1，(a,m)=1，t是使at≡1(mod m)成立的最小正整数，则称t为a关于模m的阶数，若a关于模m的阶数是φ(m)，就称a为模m的一个原根。

原根的历史可追溯至18世纪数论问题的研究。1785年，阿德利昂·玛利·埃·勒让德（Legendre）在给出二次互反律的同时还给出了模的原根的构造。1801年，高斯（Carl Friedrich Gauss）在他的著作《算术研究》中，证明了一个原根的性质，即正整数中只有，，和存在原根。20世纪50年代开始，一些学者对原根的上下限进行了讨论，中原地区数论专家王元证明了模的最小原根的结果为。1962年，伯吉斯（Burgess）得到了和王元同样的结果，且说明了所隐含的常数仅取决于。而对于原根的上限，1981年，格罗斯瓦尔德（Emil Grosswald）进行了猜测：如果，则，其结果被其他学者做出了验证和进一步探索。

原根具有一些基本性质，如，如果模有原根，则它恰有个原根。它可以用于数论中著名定理——费马小定理的证明。消去法可以用于求解原根，但是计算过程较为复杂。此外，原根在现实世界中应用广泛，如密码学中，它是实现Diffie-Hellman密钥交换协议的一个核心参数，直接影响协议的安全性。

根据欧拉定理，当，时，，因此在的正方幂，，，中，必有正整数存在，使得，于是给出：

阶数、原根：设，，是使成立的最小正整数，则称为关于模的阶数；若关于模的阶数是，则称为模的一个原根。

原根的历史可追溯至18世纪数论问题的研究。1785年，勒让德（Legendre）在给出二次互反律的同时还给出了模的原根的构造。1801年，高斯（Carl friedrich Gauss）在他的著作《算术研究》中证明了一个原根的性质，即正整数中只有，，和存在原根。1927年，埃米尔·阿廷（Artin, E.）猜测：如果一个正整数非平方数，则存在无穷多个素数以为原根。特别地，他猜想 等都是无限多个素数的原根，这个猜想迄今仍未获得证明。

后来，一些学者对原根的上下限进行了讨论。20世纪50年代，中原地区数论专家王元证明了模的最小原根。李·弗里德兰德（Fridlander）和萨利（Salié）分别独立证明了存在一个正常数，使得对于多个无穷素数，。1962年，伯吉斯（Burgess）得到了和王元同样的结果，且说明了所隐含的常数仅取决于。而对于原根的上限，1981年，格罗斯瓦尔德（Emil Grosswald）进行了猜测：如果，则，其结果被其他学者做出了验证和进一步探索。

例1（模9的原根）：设整数，这时，则有

成表如下表：

因此，和是模的原根。

例2（模8无原根）：但是，并不是每个整数都有原根。考虑模，小于而与互素的整数为，即全体奇数。由此可知。如果是偶数，那么，因此，即所有的偶数都不可能是模的原根。如果是奇数，那么可证，因此所有奇数也不可能是模的原根，所以模没有原根。

定义：若一个模的剩余类中的数与互素，则称之为一个与模互素的剩余类，这样的剩余类共有类，从每一个类中取出一个数作为代表，所得到的个数就称为模的一个简化剩余系。或者说，在模的一个完全剩余系中，与互素的数的全体称为模的一个简化剩余系。

原根与简化剩余系：设是模的一个原根，若通过模的最小非负完全剩余系，则是通过模的一个简化剩余系。

（1）给定任意模，原根不一定是存在的，实际上，只有在是四者之一时原根才存在。即，模有原根的充分必要条件是，其中是奇素数，。

推论1：设是奇素数，则模的原根存在。

推论2：设是模的一个原根，则或者是模的原根。

推论3：设是一个奇素数，则对任意正整数，模的原根存在。

推论4：设，是模的一个原根，则与中的奇数是模的一个原根。

（2）若整数，的所有不同素因数是，则是模的原根的充分必要条件是。

（3）若模有原根的存在，则恰有个对模不同余的原根，它们由集合中的数给出。

（1）如果模有原根，则它恰有个原根。

定理：若为素数，，则。

原根证法：因为素数恒有原根，所以当时，有，即。

原根的求法是对原根的一种刻画，基本思想可表示为：若对模奇素数的阶为，，则不是模的原根。因此要求的原根，先列出模的简化剩余系：

（7.1.1）

首先取，求得对模的阶为，若，则即为的原根。若，则在（7.1.1）消中去各数。在（7.1.1）中剩下的数中再取一数，重复以上方法，直到（7.1.1）中剩下 个数，因为奇素数恰有个原根，因此这个数都是的原根。上述求原根的方法称为消去法。

例题：求模的最小正原根并根据此求出的一个原根，其中是正整数。

解：求解此题需引入下述命题。

命题1：设且的所有不同的素因数为，则是模的原根当且仅当。

首先，有，其次由知不是模的原根。因为

，

根据命题1知是模的原根，从而是模的最小正原根。又因为

，

，

故，说明，可知是的原根。另外由是奇数和原根性质知也是的一原根。

生成模原根最原始的思想就是：通过逐个计算，求出的次数，由此判断是否为原根，这种算法是指数算法，实现效率低。经典的加速方法将完全分解为，通过计算是否成立来生成原根，这个算法能够在一定程度上提高效率，但是最大整数的分解没有多项式算法。1997年，埃里希·巴赫（Erich Bach）利用部分分解的思想给出了依赖于ERH的确定的多项式时间算法。

离散对数：离散对数是一种基于同余运算和原根的一种对数运算。在实数中的一般对数定义为，含义是对于给定的，求出一个数，使得。相似地，在其他任何群中可以定义离散对数使得的整数，其中执行的是群上的幂运算。离散对数在某些特殊情况下可以快速计算，但是一般而言没有具有非常高效率的方法来计算离散对数。在精心选择或是构造的群中，并不存在有效求解离散对数的算法，因此公钥密码学中的几个重要算法，如ElGamal公钥加密算法，是以离散对数的求解困难性保障算法的安全性的。

求离散对数：简单以上的离散对数为例，首先定义素数的本原根：素数的本原根是中的一个元素，其幂可以遍历中的所有元素。若是素数的一个本原根，那么：

集合与完全等价。

对任意整数和素数的本原根，有唯一的幂使得

称该指数是以为底的的模离散对数，记为。

设是大于的整数，，若对模的阶为，则称是模的一个半原根。

设，则模的半原根存在的充要条件是为下列4种情况之一。

（1）（）；

（2）（，为奇质数）；

（3）（，为奇质数）；

（4）（、是两个不同的奇质数，）。

设，用表示在模的一个简化剩余系中，关于模的半原根的个数。由半原根的定义知，与模的简化剩余系的选取无关。

在工程学领域，自动交换光网络（ASON）控制协议采用通用多协议标签交换（GMPLS）控制协议族，其路由部分主要为开放式最短路径优先（OSPF）协议。针对OSPF协议的安全模式，可采取一种基于DES算法改进的加密机制，通过优化S盒的设计，使其次序随密钥而变化，抵抗破译时的差分密码分析，达到进一步增强DES算法加密强度的目的。通过初始置换矩阵的精心设计，利用原根理论来实现密钥的动态生成算法，同时使得f函数和密钥相关，最终可以更加安全地进行网络信息的传送。

原根和指数在密码学中应用很多，较为经典的包括了Diffie-Hellman密钥交换协议、ElGamal加密、DSA数字签名等。Diffie-Hellman密钥交换是一个可以使通信双方在不可信信道上建立共享密钥，并使之应用于后继对称密钥加密通信系统的一种密码协议。而本原根是实现Diffie-Hellman密钥交换协议的一个核心参数，它直接影响协议的安全性。对于大素数，通过快速确定本原根，可以节约运算成本，加强保密通信的性能。

在计算机科学中，随着网络技术的迅速发展，图像成为互联网上表达和传输信息的一种重要载体，其安全性问题日益受到人们的关注，数字图像的置乱和隐藏成为信息安全技术中的一个研究热点。一种图像置乱算法采用线性同余伪随机数发生器技术，根据RGB图像像素值的特性，可以计算出LCG迭代公式中的值及其原根，通过实验可以得出置乱的最小正周期。研究表明，该算法置乱效果显著，可以作为图像隐藏的预处理和后期处理的一种良好方法。