密码学数学基础（四）指数与原根

四、指数与原根

4.1 指数、原根、及其性质

定义4.1：设$m\ge 1$，$(a,m)=1$。使$a^d\equiv 1(\mathrm{mod}m)$成立的最小的正整数$d$称为$a$对模$m$的指数（阶），记作${\delta }_m(a)$。当${\delta }_m(a)=\phi (m)$时，称$a$是模$m$的原根。

下面讨论指数的性质，在此之前先给出两组例子，可以结合例子理解定理。

例4.1：

• $m=13$

$a$	1	2	3	4	5	6	7	8	9	10	11	12
${\delta }_{13}(a)$	1	12	3	6	4	12	12	4	3	6	12	2

• $m=2^4$

$a$	1	3	5	7	9	11	13	15
$$	1	4	4	2	2	4	4	2

定理4.1：以下四条性质都假设$$，$$。

• $$模$$两两不同余；

• 对任意整数$$，如果$$，则$$。特别地，$$；

• 若$$，则$$；

• $$。

证明：

• 采用反证，假设存在$$使得$$，则$$，显然$$，这与指数的最小性矛盾，故原命题成立；

• 标准证明略。因为$$已经是满足等式的最小的$$了，其他的$$肯定是$$的倍数。特别地，由欧拉定理有$$，因此当$$时有$$；

• 由第2条性质，易知成立；

• 设$$，因为$$是$$的逆，根据逆的定义有$$，所以 $$ 假设还存在$$使得$$成立，则反过来有 $$ 这与$$的定义矛盾，因此$$也是$$的指数。

定理4.2：设$$是正整数，则有 $$

证明：记$$，$$，$$。

• 由题可知$$，$$，由定理4.1第2条可得$$，所以 $$ 又因为$$，因此$$；

• 另一方面，$$，所以$$，因此$$。

综上$$。

根据上述定理，可以得到定理4.3～4.5三条推论。

定理4.3：当$$时，$$。

定理4.3即定理4.2的特殊情况，该结论十分重要。

定理4.4：在模$$的一个既约剩余系中，至少有$$个数对模$$的指数等于$$。

证明：根据定理4.3，本定理就是要找有多少个$$满足$$，显然它等于模$$的既约剩余类的数量，即$$。之所以是至少，是因为$$不一定能生成模$$的剩余系中所有的元素，可能还有$$（$$）使得$$，可以结合例4.1的第2个例子理解。

定理4.5（原根个数）：若$$为模$$的原根，则模$$的原根个数为$$，并且 $$ 即为所有原根的集合。

证明：将定理4.4中的$$替换为$$即可得到原根个数为$$。此处没有至少，是因为$$的指数为$$，根据定理4.1第1条，$$能生成模$$的剩余系中所有的元素，因此不存在$$（$$）使得$$。注意该定理的前提是模$$有原根$$，像例4.1的第二个例子是没有原根的，因此不适用该定理。

定理4.6：$$的充要条件是$$。

证明：先用两个例子理解一下，例4.1的第一个例子$$。

• $$，它们的指数不互素，显然有$$，因此$$，所以$$，易知$$；
• $$，它们的指数互素，同理有$$，所以$$，$$只有乘$$才是$$的倍数，因此$$。

应该能从上面的例子找到一点感觉，下面正式开始证明。

设$$，$$，$$，$$。

• 充分性：由$$，可得$$，根据题意有$$，因此$$，同理可得$$，所以$$。另一方面，$$，所以$$。综上$$。
• 必要性：因为$$，所以$$，由$$可得$$；另外显然$$。所以$$，即$$。

接下来的几个定理与下一节的证明密切相关。

定理4.1第2条给出$$，当模为$$的幂时，代入有$$，下面的定理4.7说明了该结论可以进一步强化。

定理4.7：$$。

证明：该定理等价于：对于任意一个奇数$$，有 $$ 设$$，使用归纳法：

• 当$$时，$$，成立；

• 假设当$$（$$）时定理成立，即 $$

• 当$$时，有 $$ 定理也成立，得证。

该定理同时也说明了：模$$（$$）无原根。

定理4.8：

• 若$$，则$$；
• 若$$，则$$。

证明：

• 由$$可得$$，因此$$；
• 记$$，由第1条有$$，$$，所以$$。另一方面，$$，由$$可得$$，因此$$。综上$$。

上述定理可以推广成如下更一般的形式。

定理4.9：若$$，其中$$是两两不同的奇素数，则$$，其中 $$ 称为卡迈克尔（Carmichael）函数。

证明：推广定理4.8第2条可得 $$ 根据定理4.7有$$，另外$$，所以 $$

4.2 原根的存在和判定定理

定理4.10（原根存在定理）：模$$有原根的充要条件是$$，其中$$是奇素数，$$。

必要性证明：

转换为证明它的逆否命题：如果$$，则模$$没有原根。

当$$时，可以分为以下两种情况：

• $$（$$）：定理4.7已证；

• $$（$$或$$）：将$$代入卡迈克尔函数$$可得 $$ 每一项至少能提出公因数$$，因此$$。结合定理4.9的$$，可得$$，即模$$没有原根。

充分性证明：

充分性证明较为复杂，可参考此处。大致思路为：

• 证明$$时有原根；
• 证明$$时有原根；
• 证明其余情况没有原根。

求原根是一个十分困难的问题，没有一般方法。但在已知模数因式分解的情况下有如下较为简单的判定方法。

定理4.11（原根判定定理）：设$$，其中$$是奇素数，$$的所有不同的素因子为$$。那么$$是模$$的原根的充要条件是 $$

证明：

必要性显然，下面用反证法证明充分性。

假设存在一个$$，满足$$，但不是模$$的原根，则存在$$使得$$。由裴蜀定理，存在一组$$满足$$，则有 $$ 由假设知$$，因此存在$$的素因子$$使得$$，则$$，与假设矛盾，故原命题成立。

例4.2：证明$$是模$$的原根。

解：$$。因为 $$ 所以$$是模$$的原根。

4.3 离散对数、既约剩余系的构造

如果模$$的原根存在，则任一原根可以生成模$$的既约剩余系，因此既约剩余系中的元素一定能表示成原根的某次方。

定义4.2：设$$为模$$的原根，给定$$，如果$$，则存在唯一的$$，$$，使得$$，称$$是$$对模$$的以$$为底的离散对数（或指标），记作$$或$$，当模$$与原根$$很明确时也可以简记为$$或$$。

离散对数有如下性质。

定理4.12：设$$是模$$的原根，$$。

• $$的充要条件是$$；

• $$；

• 设$$是不同于$$的原根，则 $$

说明：

• $$是在模$$的意义下的，因为$$，加上或减去$$没有影响；
• 即对数相加的公式；
• 即对数的换底公式。

下面的定理是关于离散对数与指数的关系的。

定理4.13：设$$是模$$的原根，$$，则 $$ 对每个正除数$$，在模$$的既约剩余系中恰有$$个元素对模$$的指数等于$$。特别地，$$时，恰有$$个原根。

证明：由定理4.2有 $$ 令$$，代入可得公式成立。

先体会一下后面那句话，如例4.1的第1个例子：指数$$时，$$，所以恰有2个元素的指数是$$；$$时，$$，所以恰有2个元素的指数是$$。下面给出证明。

根据定理4.2，元素$$的指数等于$$的充要条件是 $$ 即$$，设$$，两边同时除以$$则上式等价于$$，因此有$$个$$满足上式。

该定理应证了定理4.5。同时也要注意与定理4.4区分，定理4.4没有原根存在的前提，因此只能说至少。

原根存在的情况可以用原根生成既约剩余系，那原根不存在的情况该怎么办呢？比如模$$（$$）。下面的定理直接给出了模$$（$$）的既约剩余系构造方法，知道即可，证明省略。

定理4.14：在模$$，$$的既约剩余系中，如果存在一个元素$$满足$$（事实上这样的$$一定存在，如$$），则 $$ 为模$$的一个既约剩余系。那么任给一个$$，$$，$$可以唯一地表示为 $$ 称$$为$$对模$$的以$$为底的指标组。

最后来看一般既约剩余系的构造。

定理4.15：设模$$，$$是两两不同的奇素数，$$为模$$的原根，则 $$ 构成模$$的一组既约剩余系。其中$$，$$，$$。

上述定理中一些参数的取值没有详细给出，可以结合中国剩余定理理解，知道即可，证明省略。看下面的例子就懂了。

例4.3：求模$$的既约剩余系。

解：求得 $$ 可以验证模$$的原根分别为$$，模$$的原根取$$。因此模$$的既约剩余系为 $$ 其中$$，$$，$$，$$，$$。

4.4 n次剩余

定义4.3：设$$，$$，$$。如果同余方程 $$ 有解，则称$$是模$$的n次剩余；如果无解，就称$$是模$$的n次非剩余。

下面的定理给出了原根存在时n次剩余的充要条件。

定理4.16：设$$，$$，模$$有原根$$，那么同余方程$$有解的充要条件是 $$ 且方程有解时，恰有$$个解。

证明：若$$是方程的解，$$与$$必定互素，则必有$$使得$$，进而$$。由定理4.12第1条可得 $$ 这是一个一次同余方程，由一次同余方程有解的充要条件（定理3.5）可得$$，且解的个数为$$。

需要说明的是，该定理从理论上给出了原根存在时求解同余方程$$的方法，但实际上当模数非常大时，求$$和$$都是非常困难的问题。

例4.4：解同余方程$$。

解：模$$的原根为$$，$$，由上述定理可知同余方程有解，转换为 $$ 该一次同余方程的解为$$和$$，因此原方程的解为$$和$$。

4.5 SageMath

sage: R = Zmod(13)
sage: a = R(4)
sage: a.multiplicative_order()	# 求a的指数
6
sage: primitive_root(13)		# 求模13的原根
2
sage: a.log(2)					# 求以2为底a的离散对数
2
BASH

# 求n次同余方程的一个根
sage: R = Zmod(17)
sage: a = R(13)
sage: a.nth_root(10)
9
BASH