简介：
原根是数论中一个非常重要的概念，它在密码学中有着很广泛的应用。原根从直观上非常好理解，数g对与p是原根，则(g^i)%p的结果互不相同，其中，i ∈ [1, p-1], g ∈ [2, p-1]。原根与整数的阶的关系非常密切，下面先从整数的阶讲起。 整数的阶：
根据欧拉定理（这篇博客的最后有讲到），如果 n 为正整数且 a 是一个与n互质的整数，那么aφ(n)≡1(mod n)。因此，至少存在一个正整数满足同余方程ax≡1(mod n)。
1、定义：
设 a 与 n 是互质的正整数，使得ax≡1(mod n) 成立的最小正整数 x 称为a模n的阶，记为ordna 。
2、定理(1)：
如果 a 与 n 是互质的整数且n>0，那么正整数 x 是同余式 ax≡1(mod n) 的一个解当且仅当ordna|x 。
由定理(1)，我们可以得到一个推论：
推论(1)：
如果 a 与 n 是互质的整数且n>0，那么ordna|φ(n)
3、定理(2)：
如果 a 与 n 是互质的整数且n>0，那么正整数 ai=aj(mod n)，当且仅当 i=j(mod ordna)，其中i， j为非负整数。 原根：
1、定义：
如果 a 与 n 是互质的整数且n>0，那么当 ordna=φ(n)时，称a为模n的原根。
2、性质：
1) 所有的素数都有原根。
2) 不是所有的整数都有原根。
3、定理(3)：
如果 a 与 n 是互质的整数且n>0，则如果a是模n的一个原根，那么整数a, a2, … , aφ(n)构成模n的既约剩余系。
既约剩余类，即简化剩余类，是指在每个模n的值与n互质的剩余类中，各取一数组成的集合。
这个定理说明了我们在简介中说道的关于原根的一个基本性质，即ai两两互不相同。
4、定理(4)：
当正整数m有原根时，有φ(φ(m))个原根。 求素数的原根：
因为整数a是原根，即 a 模 n 的阶数为 φ(n) 的整数，所以我们可以通过判断小于