a^x ≡1(mod n) Ord_n(a)=x什么意思

阶
设n>1,a和n互质，则必有一个x (1≤x ≤n-1)使得： a^x ≡ 1 (mod n )
满足a^x ≡ 1 (mod n ) 的最小整数x , 称为a模n的阶。符号表示为Ord(a)
观察方程 a^x ≡1(mod n) 根据欧拉定理，显然我们可以知道φ(n) 是方程的一个解，但它未必是最小的，所以不一定是阶，而当φ(n) 是a模n的阶时，我们称a为n的一个本原元。
本原元
当a模n的阶为φ(n)，也就是说当且仅当x是φ(n)的倍数，使得a^x ≡1(mod n)成立，此时称a为n的本原元。
举个例子：

这些余数构成了一个模7的完全剩余系1,2,3,4,5,6，也就是对于任意a，都可以找到x0使得:
5^x0 ≡a (mod 7)。
 ElGamal加密算法简介 - 知乎

a^x ≡1(mod n) Ord_n(a)=x什么意思最先出现在Python成神之路。