原根的定义

首先引入数论中阶的定义

  • 设$a\in Z, m\in N^+$，若$gcd(a,m)=1$，则称使得$a^n\equiv 1(\mod m)$成立的最小正整数$n$为$a$对膜$m$的阶

接下来是原根的定义

  • 设$a\in Z, m\in N^+$，若$gcd(a,m)=1$，且$a$膜$m$的阶为$\varphi(m)$，则$a$为膜$m$的原根

原根的求解

一般求解

定理1：若$m\notin {2,4}\bigcup{p^\alpha,2p^\alpha}$（其中p为奇素数，α为整数），则膜m不存在原根

由该定理，我们可以先求素数表，然后预处理出每个数是否有原根

定理2：膜m的原根数量级别为$O(m^{0.25})$

定理3：若膜m存在原根，则其有$\varphi(\varphi(m))$个原根

假设我们已求得膜$m$的最小原根$g$，那么膜$m$的所有原根就是${g^k \ |\ gcd(k,\varphi(m)=1)}$
所以我们可以直接从小到大枚举每个数判断其是否为膜m的原根
先得到膜m的最小原根g，再求g的幂次方以求得所有原根

为判断g是否为膜m的原根，在引入一个定理

定理4：设$a\in Z, m\in N^+$，若$gcd(a,m)=1$且$a^k\equiv 1(\mod m)$，则$k|\varphi(m)$

易知若$g$是膜$m$的原根，则对所有$k<\varphi(m)$均有$g^k \mod m \not= 1$
结合定理4，我们只需要检查$\varphi(m)$的真因数d，若存在$g^d\equiv 1(\mod m)$则g不是原根

进一步的，我们只需要对$\varphi(m)$质因数分解，检查所有$d=\frac{\varphi(m)}{p_i}$即可

特殊情况的快速求解

一些加密算法可能只需要任意素数及其原根，这种情况下可以有快速生成的方法

首先选取随机素数 $q$ 满足 $p=2q+1$ 也是素数
然后随机选择数$g\in[2,p-2]$，判断是否有 $g^2\mod p=1$ 或 $g^q\mod p=1$，若二者中满足任意一个，则说明$g$不是$p$的原根，重新随机选取

指标函数/离散对数

首先引入简化剩余系的定义

在与模m互素的全体剩余类中，从每个类各任取一个数组成的集合，称为模m的一个简化剩余系

易知模m的既约剩余系中的元素的个数为$\varphi(m)$

而原根有如下定理

记$g$对膜$m$的阶为$\delta$，则$g^0,g^1,…,g^{\delta-1}$在膜m意义下互不相同

由该定理可得推论

若g为模m的原根，则${g^0,g^1,g^2,……g^{φ(m)-1}}$组成模m的一个简化剩余系

定义指标函数$I(x)$满足$g^{I(x)}\equiv x \pmod m$
那么有$I(g^x \mod m)=x$

该函数也称为离散对数，他和对数函数有很多相同性质
$I(xy)=I(x)+I(y)$
$I(x^a)=aI(x)$

由此可以解决一些需要在膜意义下进行对数运算的问题
例如求解同余方程 $x^A\equiv B(\mod C)$，其中C为素数（假设离散对数已知，实际中可用BSGS求解）

首先求得$B$的离散对数$I(B)$，由定义知其满足 $g^{I(B)}\equiv B(\mod C)$
又由原根定义有 $g^{\varphi(C)}=g^{C-1}\equiv 1(\mod C)$

因此有 $g^{I(B)+(C-1)y}\equiv B(\mod C)$
将该式带入原方程得 $x^A\equiv g^{I(B)+(C-1)y} (\mod C)$
两边同时取以g为底膜C意义下的离散对数得 $A I(x)\equiv I(B)+(C-1)y (\mod \varphi(C))$

当y取不同值时，可求出不同的$I(x)$，计算$x=g^{I(x)}\mod C$即可求得x
易知x共有$gcd(A,C-1)$个不同解